hello kity

期待您的批阅,由于写解题报告时 不一定考虑的很周到,所以如果您有什么不懂的地方,请您留言,然而一天之内我肯定会看见您信息,再对代码注释详细,让您更好的阅读

分类

最新评论

最新留言

链接

RSS

计数器
224242

功能

HDU (1575 Tr A)
spoiler
posted @ 2011年4月26日 21:52
in 十个利用矩阵乘法解决的经典题目
, 1930 阅读
题目分析:Tr A表示方阵A的迹(主对角线元素之和),求Tr(Ak) % 9973。
由于k最大有10^9,所以只能用矩阵二分快速幂得到Ak,最后求和即可。
代码:
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 | # include <iostream> # include <cstdio> # include <cstring> using namespace std; struct M { int s[ 11 ][ 11 ]; }; int n,p= 9973 ; struct M multiply(struct M a,struct M b){ struct M c; memset(c.s, 0 ,sizeof(c.s)); for ( int i= 1 ;i<=n;i++) for ( int j= 1 ;j<=n;j++) for ( int k= 1 ;k<=n;k++) c.s[i][j]=(c.s[i][j]+(a.s[i][k]*b.s[k][j])%p)%p; return c; } struct M paw(struct M a, int t){ if (t== 1 ) return a; else { struct M b=paw(a,t/ 2 ); if (t& 1 ){ return multiply(multiply(b,b),a); } else return multiply(b,b); } } int main(){ struct M a,b; int k,sum,cas; cin>>cas; while (cas--){ scanf( "%d %d" ,&n,&k); sum= 0 ; for ( int i= 1 ;i<=n;i++) for ( int j= 1 ;j<=n;j++) scanf( "%d" ,&a.s[i][j]); /*for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) printf("%d",a.s[i][j]);*/ b=paw(a,k); for ( int i= 1 ;i<=n;i++) sum=(sum+b.s[i][i])%p; printf( "%d\n" ,sum); } return 0 ; } |