HDU 2842 Chinese Rings(矩阵快速幂+递推) - c++编程基础

TOP

HDU 2842 Chinese Rings(矩阵快速幂+递推)

2015-07-20 17:39:37 来源: 作者: 【大中小】浏览:3次

题目地址：HDU 2842

这个游戏是一个九连环的游戏。

假设当前要卸下前n个环。由于要满足前n-2个都卸下，所以要先把前n-2个卸下，需要f(n-2)次。然后把第n个卸下需要1次，然后这时候要卸下第n-1个，然后此时前n-2个都已经被卸下了。这时候把前n-2个都卸下与都装上所需的次数是一样的，因为卸下与装上的规则是一样的。所以又需要f(n-2)次，这时候前n-1个都在上面，卸下前n-1个需要f(n-1)次。

所以，总共需要2*f(n-2)+f(n-1)+1次。

然后构造如下矩阵。

1,2,1

1,0,0

0,0,1

f(n-1)

f(n-2)

f(n)

f(n-1)

然后用矩阵快速幂求解。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; #define LL __int64 const int mod=200907; struct matrix { LL ma[4][4]; }init, res; matrix Mult(matrix x, matrix y) { matrix tmp; int i, j, k; for(i=0;i<3;i++) { for(j=0;j<3;j++) { tmp.ma[i][j]=0; for(k=0;k<3;k++) { tmp.ma[i][j]=(tmp.ma[i][j]+x.ma[i][k]*y.ma[k][j])%mod; } } } return tmp; } matrix Pow(matrix x, int k) { matrix tmp; int i, j; for(i=0;i<3;i++) for(j=0;j<3;j++) tmp.ma[i][j]=(i==j); while(k) { if(k&1) tmp=Mult(tmp,x); x=Mult(x,x); k>>=1; } return tmp; } int main() { int k, i, j; while(scanf("%d",&k)!=EOF&&k) { if(k==1) { printf("1\n"); continue ; } init.ma[0][0]=1; init.ma[0][1]=2; init.ma[0][2]=1; init.ma[1][0]=1; init.ma[1][1]=0; init.ma[1][2]=0; init.ma[2][0]=0; init.ma[2][1]=0; init.ma[2][2]=1; res=Pow(init,k-2); LL ans; ans=(2*res.ma[0][0]+res.ma[0][1]+res.ma[0][2])%mod; printf("%I64d\n",ans); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU4939Stupid Tower Defense (有..	下一篇：NYOJ-聪明的小珂

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: