HDU 5451 广义斐波那契数列

这道题目可以先转化:

令f(1) = 5+2√6

f(2) = f(1)*(5+2√6)

...

f(n) = f(n-1)*(5+2√6)

f(n) = f(n-1)*(10-(5-2√6)) = 10*f(n-1)-(5-2√6)f(n-1) = 10*f(n-1) - 10/(5+2√6) f(n-1) = 10*f(n-1) - 10/(5+2√6) * (5+2√6)f(n-2)

= 10*f(n-1) - f(n-2)

那么就可以写成矩阵相乘的形式了

(f(n) , f(n-1)) = (f(n-1) , f(n-2)) (10 , 1

　　　　　　　　　　　　　　　　 -1 , 0)

但这里2^x+1还是很大，这里就用到广义斐波那契数列找循环节的思想

循环节长度 = (mod-1)*(mod+1)

具体证明可以参考这里: 广义斐波那契数列

那么只要求出对模循环节后的长度进行幂运算就行了

但这里f(i)都是带根号的小数 , 这里就选择用近似的整数代替

5+2√6 = 9.89...

f(0) = (5+2√6)^0 = 1

f(1) = (5+2√6)^1 = 5+2√6

/*囧想了半天我还是不知道为什么f(0)用2代替， f(1)用10代替就一定保证之后取到的都是上顶*/

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 100010
 4 #define ll long long
 5 int n,q;
 6 ll MOD;
 7 struct Matrix{
 8     int m[2][2];
 9     void init(){m[0][0]=m[1][1]=1;m[0][1]=m[1][0]=0;}
10     Matrix operator*(const Matrix &p) const{
11         Matrix ret;
12         for(int i=0 ; i<2 ; i++)
13             for(int j=0 ; j<2 ; j++){
14                 ret.m[i][j]=0;
15                 for(int k=0 ; k<2 ; k++){
16                     ret.m[i][j] = (ret.m[i][j]+((ll)m[i][k]*p.m[k][j])%MOD)%MOD;
17                 }
18             }
19         return ret;
20     }
21 };
22 
23 int qpow(int b)
24 {
25     ll ret=1 , a=2;
26     while(b){
27         if(b&1) ret = ret*a%MOD;
28         a = a*a%MOD;
29         b>>=1;
30     }
31     return ret;
32 }
33 
34 Matrix qpow(Matrix a , int b)
35 {
36     Matrix ret;
37     ret.init();
38     while(b){
39         if(b&1) ret = ret*a;
40         a = a*a;
41         b>>=1;
42     }
43     return ret;
44 }
45 
46 int main()
47 {
48    // freopen("a.in" , "r" , stdin);
49     int T , cas=0;
50     scanf("%d" , &T);
51     while(T--)
52     {
53         scanf("%d%d" , &n , &q);
54         MOD = (q-1)*(q+1);
55         n = qpow(n);
56         MOD = q;
57         Matrix a;
58         a.m[0][0]=10 , a.m[1][0]=-1 , a.m[0][1]=1 , a.m[1][1]=0;
59         a = qpow(a , n);
60         ll val = (ll)10*a.m[0][0]+(ll)2*a.m[1][0];
61         val = ((val%MOD)+MOD)%MOD;
62         printf("Case #%d: %I64d
" , ++cas , (val+MOD-1)%MOD);
63     }
64     return 0;
65 }