Tr A
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6490 Accepted Submission(s): 4817
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
题目分析：这不同于上一篇博客那道题目，这个是要求一个矩阵本身的若干次幂，而上一篇是两个矩阵相乘，
这道题需要引入一个单位矩阵【它的作用和实数里面的1一样，是一个在i==j也就是对角线上为1，其余位置为0的矩阵】
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long n,k;
void mul(long long wqw[][],long long tat[][])
{
long long or2[][];
memset(or2,,sizeof(or2));
for(int i = ; i < n ; i++)
{
for(int j = ; j < n ; j++)
{
for(int kk = ; kk < n ;kk++)
{
or2[i][j]+=(wqw[i][kk]*(tat[kk][j]))%;
or2[i][j]%=;
}
}
}
memcpy(wqw,or2,sizeof(or2));
}
void mulself(long long awa[][])
{
long long or3[][];
memset(or3,,sizeof(or3));
for(int i = ; i < n ; i++)
{
for(int j = ; j< n ; j++)
{
for(int kk = ; kk < n ; kk++)
{
or3[i][j]+=((awa[i][kk])%)*((awa[kk][j])%)%;
or3[i][j]%=;
}
}
}
memcpy(awa,or3,sizeof(or3));
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
long long qwq[][],qaq[][];
scanf("%lld%lld",&n,&k);
memset(qwq,,sizeof(qwq));
for(int i = ; i < n ; i++)
{
for(int j = ; j < n ; j++)
{
scanf("%lld",&qaq[i][j]);
if(i==j)
qwq[i][j]=;//1单位矩阵
}
} while(k)
{
if(k&)
mul(qwq,qaq);
mulself(qaq);
k/=;
}
long long sum=;
for(int i = ; i < n ; i++)
{
sum+=(qwq[i][i]%);
sum%=;
}
cout << sum % << endl;
}
return ;
}