HDU6185 (Covering)[递推，矩阵快速幂]

发表于 | 更新于 | | 阅读次数：

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6185

这题比赛时猜到是矩阵快速幂了，但推公式推了好久没有推出来，比赛结束后看到有一个题解，对于填满n列的情况，只关心第n+1列露出的形状，这些形状可以分为6类，而新的一列一定是从第n+1列的这6种形状转移到第n+2列的这6种形状。这样就可以对这6种形状写出转移矩阵了。

题解链接：https://blog.csdn.net/a664607530/article/details/77619554

情况a为第n行刚好填满且没有突出到第(n + 1)行，即为所求答案，由图不难推出：
a[n] = a[n - 1] + b[n - 1] + c[n - 1] + dx[n - 1] + dy[n - 1]
b[n] = a[n - 1]
c[n] = a[n - 1] + e[n - 1]
dx[n] = a[n - 1] + dy[n - 1]
dy[n] = a[n - 1] + dx[n - 1]
e[n] = c[n - 1]
令d[n] = dx[n] + dy[n]
则 a[n] = a[n - 1] + b[n - 1] + c[n - 1] + d[n - 1]
b[n] = a[n - 1]
c[n] = a[n - 1] + e[n - 1]
d[n] = a[n - 1] * 2 + d[n - 1]
e[n] = c[n - 1]

根据这个构造出矩阵即可

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
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const long long  M = 1000000007LL;
const ll matt[][6] = {
	{0,0,0,0,0,0},
	{0,1,1,1,2,0},
	{0,1,0,0,0,0},
	{0,1,0,0,0,1},
	{0,1,0,0,1,0},
	{0,0,0,1,0,0}
};
const ll seqt[] = {0,1,1,1,2,0};
const ll matat[][6] = {
	{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,0,0,0,0,1}
};
ll mat[6][6];
ll mata[6][6];
ll seq[6];
ll ans[6];
ll n;
void pow_mod(ll y) {
	ll tmp[6][6];
	while(y) {
		if(y&1) {
			memset(tmp,0,sizeof(tmp));
			for(int i=1;i<=5;i++)
				for(int j=1;j<=5;j++)
					for(int k=1;k<=5;k++)
						tmp[i][j] = (tmp[i][j] + (mata[i][k]*mat[k][j])%M)%M;
			memcpy(mata,tmp,sizeof(tmp));
		}
		y>>=1;
		memset(tmp,0,sizeof(tmp));
		for(int i=1;i<=5;i++)
			for(int j=1;j<=5;j++)
				for(int k=1;k<=5;k++)
					tmp[i][j] = (tmp[i][j] + (mat[i][k]*mat[k][j])%M)%M;
		memcpy(mat,tmp,sizeof(tmp));
	}
}
int main() {
	while(~scanf("%I64d",&n)) {
		memcpy(mat,matt,sizeof(matt));
		memcpy(seq,seqt,sizeof(seqt));
		memcpy(mata,matat,sizeof(matat));
		memset(ans,0,sizeof(ans));

		if(n==1) {
			printf("1\n");
			continue;
		}
		pow_mod(n-1);
		for(int j=1;j<=5;j++)
			for(int i=1;i<=5;i++)
				ans[j] = (ans[j] + (seq[i]*mata[i][j])%M)%M;
		printf("%I64d\n",ans[1]);
	}
}