HDU 2256 Problem of Precision(矩阵快速幂) - c++编程基础

TOP

HDU 2256 Problem of Precision(矩阵快速幂)

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

Tags：HDU 2256 Problem Precision 矩阵快速

题目地址：HDU 2256

思路：

(sqrt(2)+sqrt(3))^2*n=(5+2*sqrt(6))^n;

这时要注意到(5+2*sqrt(6))^n总可以表示成an+bn*sqrt(6);

an+bn*(sqrt(6))=(5+2*sqrt(6))*(a(n-1)+b(n-1)*sqrt(6))

=(5*a(n-1)+12*b(n-1))+(2*a(n-1)+5*b(n-1))*sqrt(6);

显然，an=5*a(n-1)+12*b(n-1);bn=2*a(n-1)+5*b(n-1);

此时可以很容易的构造出一个矩阵来快速求an和bn：

5,12

2,5

那么下一步应该怎么办呢？对于我等菜渣来说最好的办法当然是。。打表。。找规律。。

然后规律就是ans=2*an-1；

那么怎么证明呢？证明如下：

(5+2*sqrt(6))^n=an+bn*sqrt(6); (5-2*sqrt(6))^n=an-bn*sqrt(6);

(5+2*sqrt(6))^n+(5-2*sqrt(6))^n=2*an;

然后，由于

(5-2*sqrt(6))^n=(0.101....)^n<1;

再由于

(5+2*sqrt(6))^n=2*an-(5-2*sqrt(6))^n

可得

2*an-1<(5+2*sqrt(6))^n<2*an;

所以对(5+2*sqrt(6))^n向下取整的结果一定是2*an-1；

证明完毕。

所以说只要用矩阵快速幂求出an即可。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; const int mod=1024; struct matrix { int ma[3][3]; }init, res; 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) { int i, j; matrix tmp; 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; } int main() { int t, k; scanf("%d",&t); while(t--) { scanf("%d",&k); init.ma[0][0]=5; init.ma[0][1]=12; init.ma[1][0]=2; init.ma[1][1]=5; res=Pow(init,k-1); int ans=(2*(res.ma[0][0]*5+res.ma[0][1]*2)-1)%mod; printf("%d\n",ans); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU 3400 Line belt （三分再三分..	下一篇：poj2503--Babelfish(字典树一水)

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: