【题意】给定n*n的矩阵A和正整数k和m。求矩阵A的幂的和！

【解题方法】可以参见《挑战程序设计》205页！

【AC代码】

//POJ.3233
//Matrix Power Series

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct Matrix{
    int a[62][62];
}A;
int n,k,m;
Matrix operator*(const Matrix &a,const Matrix &b)
{
    Matrix c;
    for(int i=0; i<2*n; i++)
    {
        for(int j=0; j<2*n; j++)
        {
            c.a[i][j]=0;
            for(int k=0; k<2*n; k++)
            {
                c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%m;
            }
        }
    }
    return c;
}
Matrix pow(Matrix a,int x)
{
    Matrix res;
    for(int i=0; i<2*n; i++)
        for(int j=0; j<2*n; j++)
            if(i==j) res.a[i][j]=1;else res.a[i][j]=0;
    while(x)
    {
        if(x&1) res=res*a;
        a=a*a;
        x>>=1;
    }
    return res;
}
int main()
{
    while(scanf("%d%d%d",&n,&k,&m)!=EOF)
    {
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                scanf("%d",&A.a[i][j]);
            }
        }
        for(int i=0; i<2*n; i++)
        {
            for(int j=0; j<2*n; j++)
            {
                if(i<n)
                {
                    if(j<n) continue;
                    else A.a[i][j]=0;
                }
                else
                {
                    if(j==i-n) A.a[i][j]=1;
                    else if(j==i) A.a[i][j]=1;
                    else A.a[i][j]=0;
                }
            }
        }
        A=pow(A,k+1);
        for(int i=0; i<2*n; i++)
        {
            if(i>=n)
            {
                for(int j=0; j<n; j++)
                {
                    if(i-n==j) A.a[i][j]=(A.a[i][j]-1+m)%m;
                    printf("%d%c",A.a[i][j],j==n-1?'\n':' ');
                }
            }
        }
    }
}