HDU 1588 Gauss Fibonacci(矩阵快速幂) - c++编程基础

TOP

HDU 1588 Gauss Fibonacci(矩阵快速幂)

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

Tags：HDU 1588 Gauss Fibonacci 矩阵快速

题目地址：HDU 1588

用于构造斐波那契的矩阵为

1,1

1,0

设这个矩阵为A。

sum=f(b)+f(k+b)+f(2*k+b)+f(3*k+b)+........+f((n-1)*k+b)

<=>sum=A^b+A^(k+b)+A^(2*k+b)+A^(3*k+b)+........+A^((n-1)*k+b)

<=>sum=A^b+A^b*(A^k+A^2*k+A^3*k+.......+A^((n-1)*k))（1）

设矩阵B为A^k;

那么（1）式为

sum=A^b+A^b*(B+B^2+B^3+......+B^(n-1));

显然，这时候就可以用二分矩阵做了，括号内的就跟POJ 3233的形式一样了。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; #define LL __int64 LL mod; struct matrix { LL ma[3][3]; }init, res1, res2, ans; matrix Mult(matrix x, matrix y) { matrix tmp; int i, j, k; for(i=0;i<2;i++) { for(j=0;j<2;j++) { tmp.ma[i][j]=0; for(k=0;k<2;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<2;i++) for(j=0;j<2;j++) tmp.ma[i][j]=(i==j); while(k) { if(k&1) tmp=Mult(tmp,x); x=Mult(x,x); k>>=1; } return tmp; } matrix Add(matrix x, matrix y) { int i, j; matrix tmp; for(i=0;i<2;i++) { for(j=0;j<2;j++) { tmp.ma[i][j]=(x.ma[i][j]+y.ma[i][j])%mod; } } return tmp; } matrix Sum(matrix x, int k) { if(k==1) return x; if(k&1) return Add(Sum(x,k-1),Pow(x,k)); matrix tmp; tmp=Sum(x,k>>1); return Add(tmp,Mult(tmp,Pow(x,k>>1))); } int main() { int k, b, n; while(scanf("%d%d%d%d",&k,&b,&n,&mod)!=EOF) { init.ma[0][0]=1; init.ma[0][1]=1; init.ma[1][0]=1; init.ma[1][1]=0; res1=Pow(init,b); res2=Pow(init,k); ans=Add(res1,Mult(res1,Sum(res2,n-1))); printf("%I64d\n",ans.ma[0][1]); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：UVA 10249 - The Grand Dinner（..	下一篇：POJ 3301 Texas Trip （三分）

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: