这道题两次二分，相当经典。首先我们知道，A^i可以二分求出。
然后我们需要对整个题目的数据规模k进行二分。
比如，当k=6时，有： A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3) 应用这个式子后，规模k减小了一半。
我们二分求即可得到原问题的答案。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,k,m;
struct mitrix
{
int a[31][31];
};
mitrix unit;
mitrix add(mitrix x,mitrix y)
{
mitrix c;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
c.a[i][j]=x.a[i][j]+y.a[i][j];
c.a[i][j]%=m;
}
}
return c;
}
mitrix mul(mitrix x,mitrix y)
{
mitrix c;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)c.a[i][j]=0;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
c.a[i][j]+=x.a[i][k]*y.a[k][j];
c.a[i][j]%=m;
}
}
}
return c;
}
mitrix mi(mitrix b,int x)
{
mitrix p,q;
p=b;
q=unit;
while(x!=1)
{
if(x%2)
{
x--;
q=mul(p,q);
}
else
{
x>>=1;
p=mul(p,p);
}
}
p=mul(p,q);
return p;
}
mitrix solve(mitrix b,int x)
{
if(x==1)return b;
if(x%2)
{
mitrix d=solve(b,x-1);
mitrix e=add(b,mul(b,d));
return e;
}
else
{
mitrix d=mi(b,x/2);
mitrix e=solve(b,x/2);
e=add(e,mul(e,d));
return e;
}
}
int main()
{
scanf("%d%d%d",&n,&k,&m);
mitrix b;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&b.a[i][j]);
b.a[i][j]%=m;
if(i==j)unit.a[i][j]=1;
else unit.a[i][j]=0;
}
}
mitrix c=solve(b,k);
for(int i=1;i<=n;i++)
{
printf("%d",c.a[i][1]%m);
for(int j=2;j<=n;j++)
{
printf(" %d",(c.a[i][j]+m)%m);
}
printf("\n");
}
return 0;
}