Dowemo
0 0 0 0

int mod;
struct matrix{
 int a[12][12];//根据实际数据局范围调整。int r;
 int c;
};matrix multiply (matrix x,matrix y)//矩阵相乘{
 matrix t;
 t.r=x.r;
 t.c=y.c;
 for(int i=0; i<x.r; ++i)
 for(int j=0; j<y.c; ++j)
 t.a[i][j]=0;
 for(int i=0; i<x.r; ++i)
 for(int j=0; j<y.c; ++j)
 for(int k=0; k<x.r; ++k)
 {
 t.a[i][j]+=x.a[i][k]*y.a[k][j];
 t.a[i][j]%=mod;
 }
 return t;
}matrix powmatrix (matrix x,int y)
{
 matrix t=x;//快速幂肯定是方阵,x.r==x.c。所以直接让t=x,再将t中数组a转化成一个单位矩阵。for(int i=0; i<n; ++i)
 for(int j=0; j<n; ++j)
 if(i==j)
 t.a[i][j]=1;
 else t.a[i][j]=0;
 while(y)//跟快速幂原理相同 {
 if(y&1)
 t=multiply(t,x);
 y/=2;
 x=multiply(x,x);
 }
 return t;
}



Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs