GMOJ4787. 数格子

发表于 | 更新于: | 分类于

Description

你有多少种方法用$2 \times 1$的多米诺骨牌填满$4 \times N$的矩形。
答案会很大，所以你只需输出答案模$M$的值。

Input

读入包括多组测试数据，以两个0结尾，每个测试点测试组数不超过10组。
每组数据包含两个整数，$N$，$M$。

Output

每行输出答案模$M$的值。

Sample Input

1 10000
3 10000
5 10000
0 0

Sample Output

1
11
95

Data Constraint

对于30%的数据，$1 \leq N \leq 8$。
对于80%的数据，$1 \leq N \leq 10 ^ 5$。
对于100%的数据，$1 \leq N \leq 10 ^ 9，1 \leq M \leq 10 ^ 5$。

80%解法

$4 \times N$，一看就是状压DP，设$f[i][j]$第i列状态为j的方案数，J的每一位上0表示对下一位无影响，1表示有影响，可知$ans = f[n][0]$。
可发现$f[i - 1][j]$和$f[i][k]$满足以下条件才可转移：

  1. j & k = 0（j 和 k 不能有某一位同时为1）；
  2. j 和 k 都为0的位数必须为偶数并且连续。

可发现无论 i 为何值，j 状态是否能转移到 k 状态都是确定的，所以可以dfs做出转移矩阵，然后暴力转移，可拿到80分部分分。

100%解法

做出转移矩阵后可发现我们推出来的DP转移式可用矩阵乘法计算，则可以用矩阵快速幂加速。
注意几个可能出错的细节：矩阵乘法只满足乘法结合律，不满足乘法交换律，所以快速幂时注意相乘的顺序。

Code

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
71
#include<cstdio>
#include<iostream>
#define N 16
using namespace std;
int n, m, g[4];
struct arr
{
	long long a[N][N];
}ans, f, p;
void dfs(int l, int k)
{
	if (k >= N) return;
	int flag = 0;
	for (int i = 0; i < 4; i++)
	{
		if ((1 << i & k) && (1 << i & l))
		{
			f.a[k][l] = 0;
			dfs(l, k + 1);
			return;
		}
		if (!(1 << i & k) && !(1 << i & l)) flag++;
		else
			if (flag & 1)
			{
				f.a[k][l] = 0;
				dfs(l, k + 1);
				return;
			}
			else flag = 0;
	}
	if (!(flag & 1)) f.a[k][l] = 1;
	dfs(l, k + 1);
	return;
}
arr ti(arr x, arr y)
{
	arr z;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
		{
			z.a[i][j] = 0;
			for (int k = 0; k < N; k++)
				z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j]) % m;
		}
	return z;
}
arr ksm(arr a, int b)
{
	if (b == 1) return a;
	arr c = ksm(a, b >> 1);
	if (b & 1) return ti(ti(c, c), a);
	else return ti(c, c);
}
int main()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < 4; j++) g[j] = 1 << j & i;
		dfs(i, 0);
		ans.a[i / 4][i % 4] = 0;
	}
	ans.a[0][0] = 1;
	while (1)
	{
		scanf("%d%d", &n, &m);
		if (n == 0 && m == 0) return 0;
		p = ti(ans, ksm(f, n));
		printf("%lld\n", p.a[0][0]);
	}
}