【Poj3233】Matrix_Power_Series

来源和评测点

POJ Monthly–2007.06.03, Huang, Jinsong
Poj3233
Caioj1481

题目

【题目大意】
给定一个n行n列的矩阵A,求A+A^2+A^3+…+A^k的结果,并且输出的每个数都mod m
【输入格式】
第一行含有3个整数n(n≤30),k(k≤10^9) and m(m<10^4)
接下来n行表示输入的矩阵。
【输出格式】
输出结果矩阵
【输入样例】
2 2 4
0 1
1 1
【输出样例】
1 2
2 3

分析

k非常大,暴力显然会T
设P(t)=A+A^2+….+A^t
而P(t*2)=P(t)+A^t/*P(t)
也就是说可以二分求解,一下变成O(logk),非常快

代码

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
//*******************全局定义*******************
struct matrix
{
int row,col;
int p[40][40];
matrix()
{
memset(p,0,sizeof(p));
}
};
//*******************全局变量*******************
int MOD;
//*******************实现*******************
matrix cheng(matrix a,matrix b)
{
matrix c;
int n=a.row,m=a.col,p=b.col;
for(int i=1;i<=n;i++)
for(int j=1;j<=p;j++)
for(int k=1;k<=m;k++)
c.p[i][j]=(c.p[i][j]+(a.p[i][k]*b.p[k][j])%MOD)%MOD;
c.row=n;c.col=p;
return c;
}
matrix jia(matrix a,matrix b)
{
matrix c;c.row=a.row;c.col=a.col;
for(int i=1;i<=c.row;i++)
for(int j=1;j<=c.col;j++)
c.p[i][j]=(a.p[i][j]+b.p[i][j])%MOD;
return c;
}
matrix pre(int fn)
{
matrix c;
for(int i=1;i<=fn;i++) c.p[i][i]=1;
c.row=c.col=fn;
return c;
}
matrix power(matrix a,int e)
{
matrix c=pre(a.row);
while(e>0)
{
if(e%2==1) --e,c=cheng(c,a);//a*c也行
a=cheng(a,a);e/=2;
}
return c;
}
matrix powsum(matrix a,int e)
{
if(e==1) return a;
if(e%2==1) return jia(powsum(a,e-1),power(a,e));
matrix t=powsum(a,e/2);
return jia(t,cheng(power(a,e/2),t));
}
//*******************主函数*******************
int main()
{
int n,k;scanf("%d%d%d",&n,&k,&MOD);
matrix s;s.row=s.col=n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&s.p[i][j]);
matrix ans=powsum(s,k);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
printf("%d ",ans.p[i][j]);
printf("\n");
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-01/Matrix_Power_Series.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%