HDU4565 So Easy! 矩阵快速幂-白红宇

HDU4565 So Easy! 矩阵快速幂

阅读量：5124 次

发布时间：2019-06-13

本文共 971 字，大约阅读时间需要 3 分钟。

题目链接

题目

思路

因为\((a-1)^{2}<b<a^2\)，所以\((a-1)<\sqrt b < a\)，因此\(a-\sqrt b < 1\)，从而有\((a-\sqrt b)^{n}<1\)。

设\(Ｃ_{n}=(a+\sqrt b)^n+(a-\sqrt b)^n\)，由上一段可以得知\(\lceil C_{n}\rceil = S_n\)。

又\(2aC_n=((a-\sqrt b)+(a+\sqrt b))C_n=(a-\sqrt b)C_n+(a+\sqrt b)C_n=C_{n+1}+(a^2-b)C_{n-1}\)。

因此\(C_n\)具有线性递推式\(C_n=2aC_{n-1}+(b-a^2)C_{n-2}\)。

代码实现如下

#include 
    
     #include 
     #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;typedef long long LL;typedef pair
                    
                      pLL;typedef pair
                     
                       pLi;typedef pair
                      
                        piL;;typedef pair
                       
                         pii;typedef unsigned long long uLL;#define lson rt<<1#define rson rt<<1|1#define lowbit(x) x&(-x)#define name2str(name) (#name)#define bug printf("*********\n")#define debug(x) cout<<#x"=["<
                        
                         <<"]" <
                         
                          >= 1; } printf("%d\n", f[0] % m); } return 0;}