題意要求矩陣S=A+A^2+A^3+...+A^k mod m，可以用二分的方法
首先矩陣相乘用一次二分，然后求和再用一次二分，兩次二分搞定。
其中，矩陣相乘二分：A^2k=A^k*A^k,
A^(2k+1)=A^k*A^k*A.
求和二分：A+A^2+A...+A^(2k+1)= A+A^2+...+A^k+A^(k+1)+A^(k+1)*(A+A^2+...+A^k).
A+A^2+...+A^2k = A+A^2+...+A^k+A^k*(A+A^2+...+A^k).
Ps：用結構體傳遞矩陣很好用。。
POJ 3233
#include<iostream>
using namespace std;
struct M
{
int m[31][31];
};
int n,k,p;
M Mod(M a)
{
M res;
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
res.m[i][j]=a.m[i][j]%p;
}
return res;
}
M Mult(M a,M b)
{
M tmp;
memset(tmp.m,0,sizeof(tmp.m));
int i,j,k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
tmp.m[i][j]=(tmp.m[i][j]+a.m[i][k]*b.m[k][j]%p)%p;
return Mod(tmp);
}
M Pow(M a,int t)
{
M tmp;
memset(tmp.m,0,sizeof(tmp.m));
int i;
if(t==0)
{
for(i=1;i<=n;i++)
tmp.m[i][i]=1;
return tmp;
}
else
{
M k=Pow(a,t/2);
if(t&1)
return Mult(a,Mult(k,k));
else
return Mult(k,k);
}
}
M Add(M a,M b)
{
M tmp;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
tmp.m[i][j]=(a.m[i][j]+b.m[i][j])%p;
return tmp;
}
M Sum(M b,int t)
{
M res;
M a=Mod(b);
if(t==1)
{
res=a;
return res;
}
else
{
M k=Sum(a,t/2);
if(t&1)
{
M o=Pow(a,t/2+1);
return Add(Add(k,o),Mult(o,k));
}
else
{
M o=Pow(a,t/2);
return Add(k,Mult(k,o));
}
}
}
int main()
{
cin>>n>>k>>p;
M a;
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin>>a.m[i][j];
a.m[i][j]%=p;
}
}
M b=Sum(a,k);
for(i=1;i<=n;i++)
{
for(j=1;j<n;j++)
{
cout<<b.m[i][j]<<" ";
}
cout<<b.m[i][j]<<endl;
}
system("pause");
return 0;
}