题目链接
题意
在一个$4\times n\ (1\leq n\leq10^9)$的矩形里，用$2\times1$的多米诺骨牌来平铺，问铺满的方法有多少种。
法一
考虑递推，设所求方法数为$f(n)$，矩形为4行$n$列，则该矩形必定由列不可分割的小矩形组成，设$4\times n$的列不可分割矩形有$g(n)$个，那么我们有递推关系：
$$f(n)=\sum_{k=1}^{n-1}f(n-k)g(k)$$
易知$g(n)$前几项为$g(1)=1,g(2)=4,g(3)=2,g(4)=3$，继续推导知$n>2$时，奇数项为$2$，偶数项为$3$，而
$$f(n-1)=\sum_{k=1}^{n-2}f(n-k)g(k)$$
两式相减并化简得
$$f(n)=f(n-1)+5f(n-2)+f(n-3)-f(n-4)$$
用矩阵快速幂加速：
$$\begin{pmatrix}f(n)\\ f(n-1)\\ f(n-2)\\ f(n-3)\end{pmatrix}=\begin{pmatrix}1&5&1&-1\\1&0&0&0\\0&1&0&0\\0&0&1&0\end{pmatrix}\begin{pmatrix}f(n-1)\\f(n-2)\\f(n-3)\\f(n-4)\end{pmatrix}$$
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9;
int n, m;
struct mat {
int g[5][5];
mat operator * (const mat &b) const{
mat tmp;
memset(tmp.g, 0, sizeof(tmp.g));
for (int i = 1; i <= 4; ++i)
for (int j = 1; j <= 4; ++j)
for (int k = 1; k <= 4; ++k)
tmp.g[i][j] = (tmp.g[i][j] + g[i][k] * b.g[k][j]) % m;
return tmp;
}
};
int solve(int p) {
mat a, res;
memset(a.g, 0, sizeof(a.g));
memset(res.g, 0, sizeof(res.g));
a.g[1][1] = 1; a.g[1][2] = 5; a.g[1][3] = 1; a.g[1][4] = -1;
a.g[2][1] = a.g[3][2] = a.g[4][3] = 1;
for (int i = 1; i <= 4; ++i) res.g[i][i] = 1;
for (; p; a = a * a, p >>= 1)
if (p & 1) res = a * res;
mat b;
memset(b.g, 0, sizeof(b.g));
b.g[1][1] = 11; b.g[2][1] = 5;
b.g[3][1] = b.g[4][1] = 1;
res = res * b;
return (res.g[1][1] + m) % m;
}
int main()
{
while (scanf("%d%d", &n, &m) && (n | m)) {
if (n == 1) printf("%d\n", 1 % m);
else if (n == 2) printf("%d\n", 5 % m);
else if (n == 3) printf("%d\n", 11 % m);
else printf("%d\n", solve(n - 3));
}
return 0;
}
|
法二
通过状压DP+矩阵加速求解。
如果一个骨牌是横着放的，那么它所在的两个方格都填充1。如果它是竖着放的，那么它所在的两个格子中，上面的那个填0，下面的这个填1。
用pre表示前一行的二进制形式，now表示当前行的二进制形式，c表示当前的列数。通常较小的数作为列，行列有一个稍大时，就需要构造矩阵解决，该题是列为4，所以pre和now的值最多有16种。
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9;
int n, m;
struct mat {
int g[20][20];
mat operator * (const mat &b) const{
mat tmp;
memset(tmp.g, 0, sizeof(tmp.g));
for (int i = 0; i < 16; ++i)
for (int j = 0; j < 16; ++j)
for (int k = 0; k < 16; ++k)
tmp.g[i][j] = (tmp.g[i][j] + g[i][k] * b.g[k][j]) % m;
return tmp;
}
}path;
void dfs(int c, int pre, int now) {
if (c == 4) { ++path.g[pre][now]; return; }
dfs(c + 1, pre<<1 | 1, now<<1); // 不放
dfs(c + 1, pre<<1, now<<1 | 1); // 竖放
if (c < 3) dfs(c + 2, pre<<2 | 3, now<<2 | 3); // 横放
}
int solve() {
mat res, t;
t = path;
memset(res.g, 0, sizeof(res.g));
for (int i = 0; i < 16; ++i) res.g[i][i] = 1;
for (; n; t = t * t, n >>= 1)
if (n & 1) res = res * t;
return (res.g[15][15] + m) % m;
}
int main()
{
memset(path.g, 0, sizeof(path.g));
dfs(0, 0, 0);
while (scanf("%d%d", &n, &m) && (n | m)) {
printf("%d\n", solve());
}
return 0;
}
|