Tr A
Time Limit : 1000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 35 Accepted Submission(s) : 24
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
HDU 2007-1 Programming Contest
此题也是最基础的矩阵快速幂，注意把数据开大一点就好，代码：
#include <stdio.h>
#include <cstring>
#define MOD 9973
__int64 n;
struct matrix
{__int64 a[15][15];
};
matrix multi(matrix e,matrix d)
{__int64 i,j,k;matrix m;memset(m.a,0,sizeof(m.a));for(i=1; i<=n; i++)for(j=1; j<=n; j++)for(k=1; k<=n; k++){m.a[i][j] += e.a[i][k]*d.a[k][j];m.a[i][j] %= MOD;}return m;
}
matrix fast_mod(matrix a1,__int64 cishu)
{__int64 i;matrix f;memset(f.a,0,sizeof(f.a));for(i=1; i<=n; i++)f.a[i][i] = 1;while(cishu){if(cishu&1)f = multi(f,a1);a1 = multi(a1,a1);cishu>>=1;}return f;
}
int main()
{__int64 i,j,t,cishu;matrix c,last;scanf("%I64d",&t);while(t--){scanf("%I64d%I64d",&n,&cishu);for(i=1; i<=n; i++)for(j=1; j<=n; j++){scanf("%I64d",&c.a[i][j]);c.a[i][j] %= MOD;}last = fast_mod(c,cishu);__int64 sum=0;for(i=1; i<=n; i++){sum += last.a[i][i];sum %= MOD;}printf("%I64d\n",sum);memset(last.a,0,sizeof(last.a));}return 0;
}