学步园

类似a^b的快速幂。很经典一道题。

#include<iostream>
#include<cstdio>
#include<cstring>
typedef __int64 LL;
using namespace std ;

int n,M;
LL k;

struct matrax{
	   int m[35][35];
	   
	   void unit(){
			memset(m,0,sizeof(m));
			for(int i=0;i<n;i++) m[i][i]=1;
	   }  
 
	   matrax operator + (const matrax &a){
			matrax c;
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++){
					c.m[i][j]=(m[i][j]+a.m[i][j])%M;
				}
			}
			return c;
	   }
	   
	   matrax operator * (const matrax &a){
			matrax c;
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++){
					c.m[i][j]=0;
					for(int k=0;k<n;k++) 
					c.m[i][j]=(c.m[i][j]+m[i][k]*a.m[k][j])%M;
				}
			}
			return c;
	   }	   	 
};

matrax A;

matrax operator ^ (matrax a,LL k)
{
    matrax ans;
	ans.unit();
	while(k){
	   if(k&1) ans=ans*a;
		a=a*a;
		k>>=1;
	}
	return ans;
}

matrax Sum(LL k)
{
   if(k==1) return A;
   matrax tmp=Sum(k>>1);
   matrax tmp2;
   if(k&1){
	    tmp2=A^((k>>1)+1);
		return tmp+tmp2+tmp*tmp2;
   }
   else{
	    tmp2=A^(k>>1);
		return tmp+tmp*tmp2;
   }
}

int main()
{
    int i,j;
    while(scanf("%d %I64d %d",&n,&k,&M)!=EOF){
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				scanf("%d",&A.m[i][j]);
				A.m[i][j]%=M;
			}
		}
	    matrax ans=Sum(k);
	    for(i=0;i<n;i++){
			for(j=0;j<n;j++)
				printf(j==n-1?"%d\n":"%d ",ans.m[i][j]);
	    }
    }
 	return 0 ;
}