題意要求矩陣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).
PKU 3233
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
#define maxn 32
int m,n,k;
struct Matrix
{
int m[maxn][maxn];
};
Matrix mat;
Matrix operator * (const Matrix & m1,const Matrix & m2)
{
Matrix res;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
res.m[i][j]=0;
for(int k=0;k<n;k++)
{
res.m[i][j]+=m1.m[i][k]*m2.m[k][j];
}
res.m[i][j]%=m;
}
return res;
}
Matrix operator +(const Matrix & m1,const Matrix & m2)
{
Matrix res;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
res.m[i][j]=(m1.m[i][j]+m2.m[i][j])%m;
return res;
}
//Matrix power(int exp)
//{
// Matrix p,q;
// p=mat; //p是初始矩陣
// //q=unit; //q是單位矩陣
// for(int i=0;i<n;i++)
// {
// for(int j=0;j<n;j++)
// q.m[i][j]=0;
// q.m[i][i]=1;
// }
// while(exp!=1)
// {
// if(exp&1) //要求得冪是奇數
// {
// exp--;
// q=p*q;
// }
// else //要求的冪是偶數
// {
// exp>>=1; //相當于除2
// p=p*p;
// }
// }
// p=p*q;
// return p;
//}
Matrix power(int l)
{
if(l<=0)
{
Matrix res;
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
res.m[i][j]=0;
res.m[i][i]=1;
}
}
else if(l==1)
{
return mat;
}
else
{
Matrix res;
Matrix tmp=power(l/2);
res=tmp*tmp;
if(l&1)
res=res*mat;
return res;
}
}
Matrix solve(int k)
{
Matrix res;
if(k<=0)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
res.m[i][j]=0;
res.m[i][i]=1;
}
return res;
}
else if(k==1)
return mat;
else
{
res=solve(k/2);
if(k&1) //k是奇數
{
Matrix tmp=power(k/2+1);
res=tmp*res+res+tmp;
}
else //k是偶數
{
res=power(k/2)*res+res;
}
return res;
}
}
void print(const Matrix & m)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n-1;j++)
printf("%d ",m.m[i][j]);
printf("%d\n",m.m[i][n-1]);
}
}
int main()
{
scanf("%d%d%d",&n,&k,&m);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
scanf("%d",&mat.m[i][j]);
mat.m[i][j]%=m;
}
print(solve(k));
}