骨牌覆盖问题

2015年的个五一过的实在是百无聊赖,今天就来学习一下这个骨牌覆盖问题吧。

学习的过程主要是hihocoder上面的这三道题:

骨牌覆盖问题·一
骨牌覆盖问题·二
骨牌覆盖问题·三

问题一

描述

骨牌,一种古老的玩具。今天我们要研究的是骨牌的覆盖问题:
我们有一个2xN的长条形棋盘,然后用1x2的骨牌去覆盖整个棋盘。对于这个棋盘,一共有多少种不同的覆盖方法呢?
举个例子,对于长度为1到3的棋盘,我们有下面几种覆盖方式:

输入

第1行:1个整数N。表示棋盘长度。1≤N≤100,000,000

输出

第1行:1个整数,表示覆盖方案数 MOD 19999997

解题思路

要解决该类问题,首先想到的就是动态规划。很容易将原问题分解:

当第n列竖向放置时,前n-1列可以任意放置,这种情况下的覆盖方式数等于前n-1列的覆盖方式数。
当前n列是横向放置时(两个),第n-1列肯定也是横向放置的,这种情况下的覆盖方式数等于前n-2列的覆盖方式数。

于是可以得到长度为N时覆盖方法数的通式:f(n) = f(n-1) + f(n-2)
没错!这不就是我们无比熟悉的斐波那契数列嘛!
好了,至少现在我们已经可以有简单粗暴的解法了,不过这明显不是我们的目的。

现在我们需要一种快速计算出结果的方法,这种方法可以用矩阵推导出来。
我们首先需要得到状态状态矩阵M,使其满足[f(n-1), f(n)] x M = [f(n), f(n+1)],也就是[a, b] x M = [b, a+b],很容易我们可以得到M = [0, 1; 1, 1],于是有[0, 1] x Mn = [f(n-1), f(n)]

现在的问题已经转化为了快速求矩阵M的n次幂。下面介绍一种快速幂算法解决该问题:

快速幂

在这里我们可以用二进制分解的方法快速的计算,首先

其中k1,k2,…,kj表示将n表示成二进制数后每一位的数字。
于是我们可以先计算出所有的M1,M2,…,M2j,然后根据n的二进制数各个位是否为1,将对应的Mj相乘,最终得到Mn。该算法被称为“快速幂”,可以在O(logn)复杂度之内计算出n次幂。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#pragma warning(disable:4996)
using namespace std;
#define M 19999997
typedef long long ll;

struct Matrix22 {
ll a11, a12, a21, a22;
Matrix22(ll _a11 = 0, ll _a12 = 1, ll _a21 = 1, ll _a22 = 1)
: a11(_a11 % M), a12(_a12 % M), a21(_a21 % M), a22(_a22 % M) {}
void operator*=(const Matrix22 &r) {
*this = Matrix22(
a11 * r.a11 + a12 * r.a21,
a11 * r.a12 + a12 * r.a22,
a21 * r.a11 + a22 * r.a21,
a21 * r.a12 + a22 * r.a22);
}
};

int main() {
// freopen("..\\input.txt", "r", stdin);
int N; cin >> N;
Matrix22 m, A(1, 0, 0, 1);
for (int t = 0; t < 32; t++) {
if (N & (1 << t)) A *= m;
m *= m;
}
cout << A.a22 << endl;
}

经验总结

为保证数据在做乘法时不会溢出,应使用long long类型来存储计算结果。

问题二

描述

上一周我们研究了2xN的骨牌问题,这一周我们不妨加大一下难度,研究一下3xN的骨牌问题?
所以我们的题目是:对于3xN的棋盘,使用1x2的骨牌去覆盖一共有多少种不同的覆盖方法呢?
首先我们可以肯定,奇数长度一定是没有办法覆盖的;对于偶数长度,比如2,4,我们有下面几种覆盖方式:

输入

第1行:1个整数N。表示棋盘长度。1≤N≤100,000,000

输出

第1行:1个整数,表示覆盖方案数 MOD 12357

解题思路

第二题跟第一题相比,就是棋盘的高度从2变成了3,这时我们还想用第一题的方法来解决,那么此时是否还存在像问题一中那样的转移矩阵呢?答案是肯定的,但是此时我们需要真正弄清楚这个转移矩阵的含义了。

首先我们是列为单位进行的转移推算,那么我们要定义一个其状态的表示方法。这里对于每一列,有三个位置,我们分别用0和1表示其对应位置是否填满,则可以用0到7来表示每一列的全部状态了:

然后我们用动态规划的思想进行问题的分解:假设第i列之前(不包括第i列)的所有列都已经被填满,且第i行的状态为x(x是0到7中的一个数),第i+1行的状态为0(全空),此时我们要对第i+1行进行覆盖,并需要保证在覆盖完成之后:第i列的状态为7(被填满),第i+2行的状态为0(全空),这样才可以继续向后递推。
定义了以上的规则之后,我们来看一下第i+1行的覆盖方法(设i+1列的状态为y):

1. 若x中对应位置状态为0,则必须横向覆盖骨牌,此时完成后对应位置x为1,y也为1。
2. 若x中对应位置状态为1,则i+1行可以:
1) 不覆盖,此时完成后y对应位置为0
2) 竖着覆盖(如果可能),此时完成后y对应位置为1。

根据以上的递推方式进行枚举,则可以得到x到y的状态转移矩阵M,如下:(空位置为0)

可以举个例子来理解上面的矩阵,比如说第i列的状态为3,则在覆盖第i+1列时,第1行肯定是横着覆盖,第2,3行则既可以不覆盖也可以竖着覆盖,所以转移后y的状态即可能是4也可能是7,即转移矩阵对应位置为1。

有了状态转移矩阵,再来看边界条件:在准备覆盖第1列时,默认第0列的状态肯定是7的,所以初始状态矩阵为

1
A = [0, 0, 0, 0, 0, 0, 0, 1]

而最终要求的是将第n列全部覆盖的方法数,若B = Mn x A,B是一个1x8的矩阵,则最终的结果为B的第1行第8列的值。具体实现见代码:

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>
#pragma warning(disable:4996)
using namespace std;
#define MOD 12357
typedef long long ll;

struct Matrix {
int m, n;
vector<vector<ll> > a;
Matrix(int m, int n) : m(m), n(n) {
a = vector<vector<ll> >(m, vector<ll>(n));
}
Matrix(int m, int n, ll *b) : m(m), n(n) {
a = vector<vector<ll> >(m, vector<ll>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = b[i*n+j];
}
}
}

void operator*=(const Matrix &r) {
Matrix res(m, r.n);
for (int row = 0; row < m; row++) {
for (int col = 0; col < r.n; col++) {
for (int k = 0; k < n; k++) {
res.a[row][col] += a[row][k] * r.a[k][col];
res.a[row][col] %= MOD;
}
}
}
*this = res;
}
};

int main() {
ll b[] = { // 转移矩阵
0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 0, 0, 1, 0, 0, 1,
0, 0, 0, 1, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 0, 1,
1, 0, 0, 1, 0, 0, 1, 0,
};
Matrix m(8, 8, b);
ll a[] = { // 初始状态
0, 0, 0, 0, 0, 0, 0, 1,
};
Matrix A(1, 8, a);

// freopen("..\\input.txt", "r", stdin);
int N; cin >> N;
for (int t = 0; t < 32; t++) {
if (N & (1 << t)) A *= m;
m *= m;
}
cout << A.a.back().back() << endl;
}

问题三

描述

前两周里,我们讲解了2xN,3xN骨牌覆盖的问题,并且引入了两种不同的递推方法。
这一次我们再加强一次题目,对于给定的K和N,我们需要去求KxN棋盘的覆盖方案数。
输入

第1行:2个整数N。表示棋盘宽度为k,长度为N。2≤K≤7,1≤N≤100,000,000

输出

第1行:1个整数,表示覆盖方案数 MOD 12357

解题思路

第三题在第二题的基础上再次做了扩展,此时行数K是可变的,而像问题二中那样手动枚举出状态转移矩阵显然是不科学的了,这时就需要我们写代码来求出状态转移矩阵了。

求状态转移矩阵的方法同样是枚举,只不过需要我们写dfs代码来枚举了。与问题二中相同,假设第i-1列的状态为x,第i列的状态为y,则我们要求的状态转移矩阵中对应值应该是从状态x到状态y是否可以成功转移(可以转移为1,不可转移为0)。
值得注意的是,此时的x是转移前第i-1列的状态,y是转移后第i列的状态。而转移前第i列状态应该为0,转移后第i-1列状态应该为7。由此我们可以得到转移方法:

1. 不覆盖:此时需要x对应位置为1,y对应位置为0,列+1
2. 横向覆盖:此时需要x对应位置为0,y对应位置为1,列+1
2. 竖向覆盖:此时需要x和y对应位置以及其下一列的对应位置都为1,列+2

我们可以以状态x=0, y=0开始,从第1列开始枚举,每一列都同时枚举以上三种覆盖方式,当枚举到最后一列时,则表示可以从此时的x转移到y。详见代码。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <vector>
#pragma warning(disable:4996)
using namespace std;
#define MOD 12357
typedef long long ll;

struct Matrix {
int m, n;
vector<vector<ll> > a;

Matrix(int m, int n) : m(m), n(n) {
a = vector<vector<ll> >(m, vector<ll>(n));
}

void operator*=(const Matrix &r) {
Matrix res(m, r.n);
for (int row = 0; row < m; row++) {
for (int col = 0; col < r.n; col++) {
for (int k = 0; k < n; k++) {
res.a[row][col] += a[row][k] * r.a[k][col];
res.a[row][col] %= MOD;
}
}
}
*this = res;
}
};

int K;
// 进入此函数时第i-1列状态为x,第i列状态为y
void dfs(int x, int y, int col, vector<vector<ll> > &d) {
if (col == K) {
d[x][y] = 1;
return;
}
// 我的代码
dfs(x | (1 << col), y, col + 1, d); // 不放置
dfs(x, y | (1 << col), col + 1, d); // 横向放置
if (col + 2 <= K) { // 竖向放置
dfs(x | (3 << col), y | (3 << col), col + 2, d);
}
/* HihoCoder提示中给的代码
dfs((x << 1) + 1, y << 1, col + 1, d); // 不放置
dfs(x << 1, (y << 1) + 1, col + 1, d); // 横向放置
if (col + 2 <= K) { // 竖向放置
dfs((x << 2) + 3, (y << 2) + 3, col + 2, d);
}
*/
}

void getTransMatrix(vector<vector<ll> > &d) {
dfs(0, 0, 0, d);
}

int main() {
// freopen("..\\input.txt", "r", stdin);
cin >> K;
Matrix m(1<<K, 1<<K); // 转移矩阵
getTransMatrix(m.a); // 计算转移矩阵
Matrix A(1, 1<<K); // 初始状态
*(A.a.back().rbegin()) = 1;

int N; cin >> N;
for (int t = 0; t < 32; t++) {
if (N & (1 << t)) A *= m;
m *= m;
}
cout << A.a.back().back() << endl;
}

遗留问题

在HihoCoder的提示中给出的状态转移方法与我给出的有所不同,然而我却不能理解其代码(在以上代码的注释中已给出)。这两种方法在提交后都是AC的,也就是说都是正确的方法。期待大神给出解释。
此问题将在解决后更新。