【Poj3233】Matrix Power Series

来源和评测点

POJ Monthly–2007.06.03, Huang, Jinsong
Poj3233

题目

【题目大意】
给出一个n×n矩阵A和正整数k,
输出S=A+A^2+A^3+…+A^k,元素模m
【输入格式】
多组数据。
第一行正整数n,k和m。
接下来n行包括n个在32,768以内的非负整数
【输出格式】
S
【限定条件】
n≤30
k≤10^9
m<10^4
【输入样例】
2 2 4
0 1
1 1
【输出样例】
1 2
2 3
【样例解释】

刷题记录

30min

分析

请先思考后再展开

代码

请先思考后再展开
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
//*******************主函数******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
//*******************全局常量****************
//*******************全局定义****************
struct martix
{
int row,col;
int m[40][40];
martix()
{
memset(m,0,sizeof(m));
}
};
int MOD;
//*******************实现******************
martix jia(martix a,martix b)
{
martix 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.m[i][j]+=a.m[i][j]+b.m[i][j])%=MOD;
return c;
}
martix cheng(martix a,martix b)
{
martix c;
int n=a.row,m=a.col,p=b.col;
c.row=n;c.col=p;
for(int i=1;i<=n;i++)
for(int j=1;j<=p;j++)
for(int k=1;k<=m;k++)
(c.m[i][j]+=a.m[i][k]*b.m[k][j])%=MOD;
return c;
}
martix power(martix a,int e)
{
martix ans=a;e--;
while(e>0)
{
if(e&1) ans=cheng(ans,a);
a=cheng(a,a);e>>=1;
}
return ans;
}
martix s;
martix sum(int k)
{
if(k==1) return s;
if(k&1) return jia(sum(k-1),power(s,k));
martix t=sum(k/2);
return jia( cheng(t,power(s,k/2)),t );
}
//*******************主函数******************
int main()
{
int n,k;scanf("%d%d%d",&n,&k,&MOD);
s.row=s.col=n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&s.m[i][j]);
s=sum(k);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
printf("%d ",s.m[i][j]);
printf("\n");
}
}

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

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