POJ 3233 Matrix Power Series （矩阵快速幂和）

题意：Given a n × n matrix A and a positive integer k, find the sum S = A + A² + A³ + … + A^k.

分析：与矩阵快速幂的思想一样，都是二分。

1、k为偶数，设k=2*m，则S = A + A² + A³ + … + A^m+(A + A² + A³ + … + A^m)*A^m

2、k为奇数，设k=2*m+1，则S = A + A² + A³ + … + A^m+(A + A² + A³ + … + A^m)*A^m+A^k

由上可见，原问题均可递归成与原问题结构相同的子问题，递归边界为k=1时，结果为A

#include <stdio.h>
#include <string.h>
#define N 30
int n,m,k;
int A[N][N];
int ans[N][N];
void print(int a[][N])
{
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n-1;j++)    printf("%d ",a[i][j]);
        printf("%d\n",a[i][j]);
    }
}
void mat_add(int a[][N],int b[][N])
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            a[i][j]+=b[i][j];
            if(a[i][j]>=m)   a[i][j]%=m;
        }
    }
}
void mat_mul(int a[][N],int b[][N])
{
    int tmp[N][N];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            tmp[i][j]=0;
            for(int k=0;k<n;k++)
            {
                tmp[i][j]+=a[i][k]*b[k][j];
                if(tmp[i][j]>=m) tmp[i][j]%=m;
            }
        }
    }
    memcpy(a,tmp,sizeof(int)*N*N);
}
void mat_pow(int a[][N],int b[][N],int x)
{
    memset(a,0,sizeof(int)*N*N);
    for(int i=0;i<n;i++)    a[i][i]=1;
    int tmp[N][N];
    memcpy(tmp,b,sizeof(int)*N*N);
    while(x)
    {
        if(x&1)
        {
            mat_mul(a,tmp);
        }
        x>>=1;
        mat_mul(tmp,tmp);
    }
}
void pow_sum(int a[][N],int b[][N],int x)
{
    int c[N][N],d[N][N];
    if(x==0)
    {
        memset(a,0,sizeof(int)*N*N);
        for(int i=0;i<n;i++)    a[i][i]=1;
        return;
    }
    if(x==1)
    {
        memcpy(a,b,sizeof(int)*N*N);
        return;
    }
    pow_sum(a,b,x>>1);
    mat_pow(c,b,x>>1);
    memcpy(d,a,sizeof(int)*N*N);
    mat_mul(a,c);
    mat_add(a,d);
    if(x&1)
    {
        mat_mul(c,c);
        mat_mul(c,b);
        mat_add(a,c);
    }
}
void read()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)    scanf("%d",&A[i][j]);
    }
}
int main()
{
    while(~scanf("%d%d%d",&n,&k,&m))
    {
        read();
        pow_sum(ans,A,k);
        print(ans);
    }
    return 0;
}