poj Matrix Power Series (矩阵快速幂) (一)

给出矩阵n*n的矩阵A，求对m取模后的结果

解题思路: k的非常大，直接求解时间复杂度太高

定义F[k]=A+A^2+A^3+....A^k

利用乘法的分配律可以减少运算 F[6]=A+A^2+A^3+A^4+A^5+A^6=(A+A^2+A^3)+(A+A^2+A^3)*A^3

每次运算二分减少规模，二分之后再二分

奇数: F[n]=F[n-1]+A^n

偶数: F[n]=F[n/2]+F[n/2]*An/2

两处地方用到了二分：二分缩小总的规模，二进制思想的矩阵快速幂

代码:

[cpp]
#include
#include
#include
#define MAX 31
int n,m,k;
typedef struct snode{
int edge[MAX][MAX];
}Matrix;
Matrix map,ant,h,hh,c,d;

void mult(Matrix &a,Matrix &b,Matrix &c) //矩阵C=A*B
{
int i,j,k2;
memset(h.edge,0,sizeof(h.edge));
for(i=0;i for(j=0;j for(k2=0;k2 {
h.edge[i][j]+=(a.edge[i][k2]*b.edge[k2][j]); //**分开写，否则会WA
h.edge[i][j]%=m; //**
}
for(i=0;i for(j=0;j c.edge[i][j]=h.edge[i][j];
}

Matrix KSM(Matrix a,int k) //快速幂求矩阵A^k
{
int i;
memset(hh.edge,0,sizeof(hh.edge));
for(i=0;i hh.edge[i][i]=1;
while(k>=1)
{
if(k&1)
mult(a,hh,hh);
mult(a,a,a);
k>>=1;
}
return hh;
}

Matrix Sum(Matrix a,Matrix b) //A,B矩阵相加
{
int i,j;
for(i=0;i for(j=0;j {
h.edge[i][j]=(a.edge[i][j]+b.edge[i][j]);
h.edge[i][j]%=m;
}
return h;
}

Matrix F(int x)
{
if(x<=1)
return map;
else if(x%2) //n为奇数:F[n]=F[n/2]+F[n/2]*A^(n/2)
{
c=F(x-1);
d=KSM(map,x);
return Sum(c,d);
}
else //n为偶数:F[n]=F[n-1]+A^n
{
c=F(x/2);
d=KSM(map,x/2); //二分减少规模
mult(c,d,d);
return Sum(c,d);
}
}

int main()
{
int i,j;
scanf("%d%d%d",&n,&k,&m);
for(i=0;i for(j=0;j scanf("%d",&map.edge[i][j]);
ant=F(k);
for(i=0;i {
for(j=0;j {
printf("%d",ant.edge[i][j]);
if(j!=n-1) //每行最后的空格去掉，防PE
printf(" ");
}
printf("\n");
}
return 0;
}

#include
#include
#include
#define MAX 31
int n,m,k;
typedef struct snode{
int edge[MAX][MAX];
}Matrix;
Matrix map,ant,h,hh,c,d;

void mult(Matrix &a,Matrix &b,Matrix &c) //矩阵C=A*B
{
int i,j,k2;
memset(h.edge,0,sizeof(h.edge));
for(i=0;i for(j=0;j for(k2=0;k2 {
h.edge[i][j]+=(a.edge[i][k2]*b.edge[k2][j]); //**分开写，否则会WA
h.edge[i][j]%=m; //**
}
for(i=0;i for(j=0;j c.edge[i][j]=h.edge[i][j];
}

Matrix KSM(Matrix a,int k) //快速幂求矩阵A^k
{
int i;
memset(hh.edge,0,sizeof(hh.edge));
for(i=0;i hh.edge[i][i]=1;
while(k>=1)
{
if(k&1)
mult(a,hh,hh);
mult(a,a,a);
k>>=1;
}
return hh;
}

Matrix Sum(Matrix a,Matrix b) //A,B矩阵相加
{
int i,j;
for(i=0;i for(j=0;j {
h.edge[i][j]=(a.edge[i][j]+b.edge[i][j]);
h.edge[i][j]%=m;
}
return h;
}

Matrix F(int x)
{
if(x<=1)
return map;
else if(x%2) //n为奇数:F[n]=F[n/2]+F[n/2]*A^(n/2)
{
c=F(x-1);
d=KSM(map,x);
return Sum(c,d);
}
else //n为偶数:F[n]=F[n-1]+A^n
{
c=F(x/2);
d=KSM(map,x/2