[矩阵乘法实践]HDU 1575——Tr A
要求求解Tr(a^k)%9937,注意不要到最后才余，在每处理完一次的时候就余一下（矩阵性质：矩阵中的每个数同时除以/乘以相同整数，矩阵的性质均不变（包括矩阵的迹、矩阵的秩、矩阵的最简阶梯行列式等等）否则数字过大会溢出。
[cpp]
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
class Mat
{
public:
int mat[15][15];
};
int n; //维度,即矩阵A的行数
int MOD=9973;//好多问题要求给出取余之后的数字
Mat E;
void initE()
{
for(int i=0;i<15;i++)
E.mat[i][i]=1;
}
Mat operator*(Mat a,Mat b)
{
int i,j,k;
Mat c;
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
c.mat[i][j] = 0;
for (k=0;k<n;k++)
{
c.mat[i][j]+=(a.mat[i][k]*b.mat[k][j]);
}
c.mat[i][j]%=MOD;
}
}
return c;
}
Mat operator+(Mat a,Mat b)
{
Mat c;
int i,j;
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
c.mat[i][j] = a.mat[i][j]+b.mat[i][j];
c.mat[i][j]%=9973;
}
return c;
}
Mat operator^(Mat a,int x)
{
Mat p = E,q = a;
while (x>=1)
{
if(x%2==1)
p = p*q;
x/=2;
q = q*q;
}
return p;
}
Mat solve(Mat a,int p)
{
if(p==1)
return a;
else if(p&1)
return (a^p)+solve(a,p-1);
else
return ((a^(p>>1))+E)*solve(a,p>>1);
}
int main()
{
int testcase;
cin>>testcase;
Mat at,bt;
int res;
int kp;
while(testcase--)
{
res=0;
initE();
memset(at.mat,0,sizeof(at.mat));
memset(bt.mat,0,sizeof(bt.mat));
cin>>n>>kp;
for(int i=0;i<n;i++)
{ www.zzzyk.com
for(int j=0;j<n;j++)
{
cin>>at.mat[i][j];
}
}
bt=at^kp;
for(int i=0;i<n;i++)
{
res+=bt.mat[i][i];
}
cout<<res%9973<<endl;
}
return 0;
}
补充：软件开发 , C++ ,
