Posted on 2009-08-23 22:32
Uriel 閱讀(487)
評論(0) 編輯 收藏 引用 所屬分類:
POJ 、
遞歸 & 分治
/**//*Problem: 3233 User: Uriel
Memory: 208K Time: 172MS
Language: C++ Result: Accepted*/
#include<stdio.h>
#include<stdlib.h>
const int MAX=65;
typedef int M[MAX][MAX];
int n,m;
M in;
void copy(M x,M y)
{
int i,j;
for(i=0;i<2*n;++i)
for(j=0;j<2*n;++j)
{
x[i][j]=y[i][j];
}
}
void mu(M x,M y)
{
M C;
int i,j,k;
int t;
for(i=0;i<2*n;++i)
{
for(j=0;j<2*n;++j)
{
t=0;
for(k=0;k<2*n;++k)
{
if(x[i][k] && y[k][j])
{
t=(t+x[i][k]*y[k][j])%m;
}
}
C[i][j]=t;
}
}
copy(x,C);
}
void BS(M x,int k)
{
if(k==1)
{
copy(x,in);
return;
}
BS(x,k/2);
mu(x,x);
if(k & 1)
{
mu(x,in);
}
}
int main()
{
int k;
scanf("%d %d %d",&n,&k,&m) ;
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&in[i][j]);
in[i][j+n]=in[i][j];
in[i+n][j]=0;
in[i+n][j+n]=0;
}
in[i+n][i+n]=1;
}
M x;
BS(x,k);
for(i=0;i<n;++i)
{
for(j=n;j<2*n;++j)
{
printf("%d ",x[i][j]) ;
}
printf("\n") ;
}
system("PAUSE");
return 0 ;
}
這題搞了很久。。第一次寫二分，第一次用做矩陣乘法。。
轉移矩陣好強大
| A A |
| 0 I |