S=A+A2+A4+ +AkS=A+A2+A4+ +Ak(每个元素mod m)" type="text/javascript">
题意:给定一个n*n的矩阵A,求
题解:矩阵快速幂:
设
#include#include #include #include using namespace std; int n,k,m; struct mat { int a[100][100]; }; mat operator*(const mat &a,const mat &b) { mat ans; for(int i=0; i<2*n; i++) { for(int j=0; j<2*n; j++) { ans.a[i][j]=0; for(int k=0; k<2*n; k++) { ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j])%m; } } } return ans; } mat base; mat qm(int t) { mat ans; memset(ans.a,0,sizeof ans.a); for(int i=0; i<2*n; i++) ans.a[i][i]=1; while(t) { if(t&1) ans=ans*base; t>>=1; base=base*base; } return ans; } int main() { while(scanf("%d%d%d",&n,&k,&m)!=EOF) { memset(base.a,0,sizeof base.a); for(int i=0; i