Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
/*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;
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  |


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理