POJ 3233 快速矩阵乘法

觉得专业课学习有点落下了，而且acm这方面也没有弄好= =蛋疼死了！！稍微写写博客就开始学习吧！！

矩阵的快速幂和a^b%n类似。运用二分的思想。在这题中需要计算的是A+A^2+A^3+...+A^k的和，由于矩阵相乘有结合律，所以!@#$%^&*.....

不多说了，代码很丑。还是拿来占个位置吧.... 第二次写递归啊！！我的神啊~~

#include<iostream>
#define MAXN 31
using namespace std;struct Matrix
{unsigned long long matrix[MAXN][MAXN];
};int n,m;void MatrixPow( int k,Matrix &pre )
{int i,j,p;if( k<=1 )return ;else if( k==2 ){Matrix now1=pre;for( i=1;i<=n;i++ )for( j=1;j<=n;j++ ){pre.matrix[i][j]=0;for( p=1;p<=n;p++ )pre.matrix[i][j]+=now1.matrix[i][p]*now1.matrix[p][j];pre.matrix[i][j]%=m;}}else if( k%2==0 ){Matrix now1=pre;MatrixPow( k>>1,now1 );MatrixPow( 2,now1 );pre=now1;}else{Matrix now1=pre;Matrix now2=pre;MatrixPow( k>>1,now1 );MatrixPow( 2,now1 );for( i=1;i<=n;i++ )for( j=1;j<=n;j++ ){pre.matrix[i][j]=0;for( p=1;p<=n;p++ )pre.matrix[i][j]+=now1.matrix[i][p]*now2.matrix[p][j];pre.matrix[i][j]%=m;}}
}void addMatrix( int k,Matrix &pre )
{int i,j,p;if( k<=1 )return ;else if( k==2 ){Matrix now1=pre;Matrix now2=pre;MatrixPow( 2,now2 );for( i=1;i<=n;i++ )for( j=1;j<=n;j++ ){pre.matrix[i][j]=now1.matrix[i][j]+now2.matrix[i][j];pre.matrix[i][j]%=m;}}else if( k%2==0 ){Matrix now1=pre;Matrix now2=pre;addMatrix( k>>1,now1 );MatrixPow( k>>1,now2 );for( i=1;i<=n;i++ )for( j=1;j<=n;j++ ){pre.matrix[i][j]=0;for( p=1;p<=n;p++ )pre.matrix[i][j]+=now1.matrix[i][p]*now2.matrix[p][j];pre.matrix[i][j]%=m;}for( i=1;i<=n;i++ )for( j=1;j<=n;j++ ){pre.matrix[i][j]+=now1.matrix[i][j];pre.matrix[i][j]%=m;}}else if( k%2==1 ){Matrix now1=pre;Matrix now2=pre;addMatrix( k-1,now1 );MatrixPow( k,now2 );for( i=1;i<=n;i++ )for( j=1;j<=n;j++ ){pre.matrix[i][j]=now1.matrix[i][j]+now2.matrix[i][j];pre.matrix[i][j]%=m;}}
}int main()
{int k;while( scanf( "%d %d %d",&n,&k,&m )!=EOF ){int i,j;Matrix ans;for( i=1;i<=n;i++ )for( j=1;j<=n;j++ ){scanf( "%llu",&ans.matrix[i][j] );}addMatrix( k,ans );for( i=1;i<=n;i++ ){for( j=1;j<n;j++ )printf( "%llu ",ans.matrix[i][j]%m );printf( "%llu\n",ans.matrix[i][n]%m );     }} return 0;
}