矩阵快速幂
Tr A
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1789 Accepted Submission(s): 1318
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的内容。
每组数据的第一行有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
2 2
1 0
0 1
3 99999999
1 2 3
4 5 6
7 8 9
Sample Output
2
2686
2686
Author
xhd
Source
Recommend
linle
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int N;
const int MOD=9973;
struct Matrix
{
int m[111][111];
};
Matrix a,t1,e;
Matrix muil(Matrix a,Matrix b)
{
Matrix c;
memset(c.m,0,sizeof(c.m));
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
for(int k=0;k<N;k++)
c.m[j]=((a.m[k]*b.m[k][j])%MOD+c.m[j])%MOD;
}
}
return c;
}
Matrix quickpow(Matrix a,int k)
{
Matrix t;
memset(t.m,0,sizeof(t.m));
for(int i=0;i<=N+10;i++)
t.m=1;
while(k>1)
{
if(k&1)
{
k--;
t=muil(t,a);
}
else
{
k/=2;
a=muil(a,a);
}
}
return muil(a,t);
}
int main()
{
int T;
cin>>T;
while(T--)
{
int K;
cin>>N>>K;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
cin>>a.m[j];
}
t1=quickpow(a,K);
memcpy(a.m,t1.m,sizeof(t1.m));
int ans=0;
for(int i=0;i<N;i++)
{
ans=(ans+a.m)%MOD;
}
cout<<ans<<endl;
/*
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
cout<<a.m[j]<<" ";
cout<<endl;
}
*/
}
return 0;
}