POJ3233 (Matrix Power Series)[二分，矩阵快速幂]

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

题目链接：http://poj.org/problem?id=3233

题目分析：分析可以得到
k为偶数：sum(k) = (1+A^(k/2)) ( A+A^2+……+A^(k/2)) = (1+A^(k/2)) sum(k/2)
k为奇数：sum(k) = (1+A^((k-1)/2)) * sum(k/2) + A^k
引用自https://blog.csdn.net/tc_to_top/article/details/43878231

看到这题应该考虑到提公因式，或者凑成多项式相乘的形式，进而想到A^1+A^2+…+A^n的题解拆法

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
72
73
74
75
76
77
78
79
80
81
82
83
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int MOD;
int n,k;//
struct M {
	int a[31][31];
	M() {
		memset(a,0,sizeof(a));
	}
	M operator *(const M& y) const {
		M tmp;
		for(int i=1;i<=n;i++) 
			for(int j=1;j<=n;j++) {
				tmp.a[i][j]=0;
				for(int k=1;k<=n;k++) {
					tmp.a[i][j]=((a[i][k]*y.a[k][j])%MOD + tmp.a[i][j])%MOD;
				}
			}
		return tmp;
	}
	M operator +(const M& y) const {
		M tmp;
		for(int i=1;i<=n;i++) 
			for(int j=1;j<=n;j++) {
				tmp.a[i][j]=(a[i][j]+y.a[i][j])%MOD;
			}
		return tmp;
	}
};

M init;
M one;

M pow_mod(M& x,int y) {
	M ans=one;
	for(M i=x;y;y>>=1,i=i*i) 
		if(y&1) ans=ans*i;
	return ans;
}

M f(int x) {
	if(x==1) {
		return init;
	}
	if(x&1) {
		M tmp=pow_mod(init,x);
		tmp=tmp+(one+pow_mod(init,x>>1))*f(x>>1);
		return tmp;
	}
	else {
		M tmp=(one+pow_mod(init,x>>1))*f(x>>1);
		return tmp;
	}
}

int main() {
	scanf("%d%d%d",&n,&k,&MOD);
	for(int i=1;i<=n;i++) one.a[i][i]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) {
			scanf("%d",&(init.a[i][j]));
			init.a[i][j]%=MOD;
		}
	if(n==1) {
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				printf(j==n ? "%d" : "%d ",init.a[i][j]);
			}
			printf("\n");
		}
		return 0;
	}
	M ans=f(k);
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			printf(j==n ? "%d" : "%d ",ans.a[i][j]);
		}
		printf("\n");
	}
	return 0;
}