我是靠谱客的博主 跳跃鼠标,这篇文章主要介绍POJ 3150 矩阵快速幂,现在分享给大家,希望可以做个参考。

抄的代码。

看不出矩阵快速幂,2B。。

注意到这是种变换,每次都是n个元素在变来变去,数据范围很大,这应该反应到时矩阵

根据大神指示,用O(n)复杂度存储空间,由于 A[i][j]=A[i-1][j-1] 

O(log(k) * n ^ 2)

据说可以用傅里叶变换,更快,没试

复制代码
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
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <map> #include <set> #include <algorithm> #include <vector> #include <string> using namespace std; int n,m,d,k; int init[505],temp[505]; void mul(int *a,int *b) { int c[505]={0}; for(int i=0;i<n;++i) for(int j=0;j<n;++j) { c[i]+=a[j]*b[ i>=j ? (i-j) : (n+i-j)]; c[i]%=m; } for(int i=0;i<n;++i) a[i]=c[i]; } int main () { while(scanf("%d%d%d%d",&n,&m,&d,&k)!=EOF) { for(int i=0;i<n;++i) scanf("%d",&init[i]); temp[0]=1; for(int i=1;i<=d;++i) temp[i]=temp[n-i]=1; while(k) { if(k&1) mul(init,temp); k>>=1; mul(temp,temp); } for(int i=0;i<n;++i) { printf("%d",init[i]); if(i<n-1) printf(" "); else printf("n"); } } return 0; }


最后

以上就是跳跃鼠标最近收集整理的关于POJ 3150 矩阵快速幂的全部内容,更多相关POJ内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(121)

评论列表共有 0 条评论

立即
投稿
返回
顶部