POJ3233 Matrix Power Series————矩阵快速幂，二分

题解：本题主要考查矩阵快速幂，二分。
简要题意：给定一个方阵A，和数k，求 $S = A + A^2 + A^3 + … + A^k$
1.矩阵快速幂：快速求 $A^k$就需要矩阵快速幂。但是如果慢慢求 $S = A + A^2 + … + A^k$，(k<= $10^9$)一定TLE，所以要优化。
2.二分：对k进行二分，每次将规模减半，分k为奇偶两种情况，如当k = 6和k = 7时有：
k=6有： $S(6)=(1+A^3)*(A+A^2+A^3) = (1 + A^3) * S(3)$
k=7有： $S(7) = A + (A + A^4) * (A + A^2 + A^3) = A + (A + A^4) * S(3)$
代码如下：

#include<cstring>
#include<iostream>
using namespace std;
struct N
{
    int v[33][33];
};
N A;
int n,k,mod;
N mtAdd(N A,N B) //矩阵加法 A+B      
{
    N C;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    C.v[i][j]=(A.v[i][j]+B.v[i][j])%mod;
    return C;
}
N mtMul(N A,N B)   //矩阵乘法  A*B
{
    N C;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            C.v[i][j]=0;
            for(k=1;k<=n;k++)
            C.v[i][j]=(A.v[i][k]*B.v[k][j]+C.v[i][j])%mod;
        }
    return C;
}
N mtPow(N A,int y)    //快速幂
{
	N C;
	memset(C.v,0,sizeof(C.v));
	for(int i=1;i<=n;i++)
	C.v[i][i]=1;
	while(y>0)
	{
		if(y%2==1)C=mtMul(C,A);  
        A=mtMul(A,A);
        y>>=1;
	}
	return C;
}
N mtCal(N A,int k)   //二分求解      
{    
    N B,C;
    if(k==1)return A;
    B=mtPow(A,(k+1)/2);
    C=mtCal(A,k/2);
    if(k%2==0)
    return mtMul(mtAdd(mtPow(A,0),B),C);
    else return mtAdd(A,mtMul(mtAdd(A,B),C));
}
int main()
{
    cin>>n>>k>>mod;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    cin>>A.v[i][j];
    A=mtCal(A, k);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {cout<<A.v[i][j]<<" ";}
        cout<<endl;
    }
    return 0;
}