Tr A
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4191 Accepted Submission(s): 3131 Problem Description
A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%9973。
Input
数据的第一行是一个T，表示有T组数据。 每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行，每行有n个数据，每个数据的范围是[0,9]，表示方阵A的内容。
Output
对应每组数据，输出Tr(A^k)%9973。
Sample Input
2 2 2 1 0 0 1 3 99999999 1 2 3 4 5 6 7 8 9
Sample Output
2 2686
Author
xhd
Source
Recommend
linle | We have carefully selected several similar problems for you:
【题解】【矩阵快速幂裸题】
【范围很大，要用long long】
#include#include #include #define ll long long#define mod 9973using namespace std;struct node{ ll k[20][20];}a,sum;int n,t,p;ll ans; inline node jc(node a,node b){ int i,j,l; node d; for(i=1;i<=n;++i) for(j=1;j<=n;++j) d.k[i][j]=0; for(i=1;i<=n;++i) for(j=1;j<=n;++j) for(l=1;l<=n;++l) d.k[i][j]+=(a.k[i][l]*b.k[l][j])%mod; return d;}node poww(node a,int p){ if(p==1) return a; if(p==2) return jc(a,a); if(!(p%2)) { node x; x=poww(a,p/2); x=jc(x,x); return x; } else { node x; x=poww(a,p/2); x=jc(x,x); x=jc(x,a); return x; }}int main(){ int i,j,h; scanf("%d",&t); for(h=1;h<=t;++h) { scanf("%d%d",&n,&p); for(i=1;i<=n;++i) for(j=1;j<=n;++j) scanf("%d",&a.k[i][j]); sum=poww(a,p); ans=0; for(i=1;i<=n;++i) ans=(ans+sum.k[i][i])%mod; printf("%I64d\n",ans%mod); } return 0;}