FZU 1683 纪念SlingShot(矩阵快速幂) - c++编程基础

TOP

FZU 1683 纪念SlingShot(矩阵快速幂)

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

题目地址：FZU 1683

这题一开始用的二分矩阵，于是就一直TLE。后来找题解才发现，可以不用二分矩阵，因为这个题最终求的是一个值，所以可以把那个值加入到构造的矩阵中：

这样就不用二分矩阵了。而是可以直接求。但是这样还是会超时，那怎么办呢。由于本题的模数是固定的，所以矩阵的幂也是固定的。那么就可以对一些2^x幂预处理出来。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; const int mod =2009; struct matrix { int ma[5][5]; } init, res, mat[40]; matrix Mult(matrix x, matrix y) { matrix tmp; int i, j, k; for(i=0; i<4; i++) { for(j=0; j<4; j++) { tmp.ma[i][j]=0; for(k=0; k<4; 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) { int i, j, cnt=0; //for(i=0; i<4; i++) for(j=0; j<4; j++) tmp.ma[i][j]=(i==j); while(k) { if(k&1) x=Mult(mat[cnt],x); k>>=1; cnt++; } return x; } void per() { int i; mat[0]=init; for(i=1; i<32; i++) { mat[i]=Mult(mat[i-1],mat[i-1]); } } int main() { int t, i, j, k, num=0; scanf("%d",&t); memset(init.ma,0,sizeof(init.ma)); init.ma[0][0]=init.ma[0][1]=init.ma[2][1]=init.ma[3][2]=1; init.ma[1][1]=3; init.ma[1][2]=2; init.ma[1][3]=7; per(); while(t--) { num++; scanf("%d",&k); printf("Case %d: ",num); if(k==0) puts("1"); else if(k==1) puts("4"); else { res=Pow(init,k-1); int ans=res.ma[0][0]*4+res.ma[0][1]*5+res.ma[0][2]*3+res.ma[0][3]; ans%=mod; printf("%d\n",ans); } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：2014北京网络预选赛1008（线段树..	下一篇：HDU - 4514 湫湫系列故事??设计风..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: