HDU - 6755 Fibonacci Sum（斐波那契+二次剩餘+二項式定理）

傳送門

對于斐波那契問題，一般想到的解法是遞推或者矩陣快速幂，但是本題資料非常之大，怎麼做都逾時，臨時想了一下斐波那契的公式，覺得這個浮點誤差很大沒法寫，實際上可以寫但是要用到很多知識，本題的總結收獲不少（唯一難受的是代碼優化能做的都做了自己寫的還是逾時）

首先給出斐波那契數列的公式：

F ( n ) = 1 5 [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ] F(n)=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n] F(n)=5

​1​[(21+5

​​)n−(21−5

​​)n]

因為取模的數一般都是質數，而且我們能求出 x 2 ≡ 5 ( m o d    1 e 9 + 9 ) x^2 \equiv 5(mod~~1e9+9) x2≡5(mod  1e9+9)是有解的，解出的兩個解為 616991993 616991993 616991993和 383008016 383008016 383008016，這裡我們采用第二個，也就是在這個取模的意義下二者是相等的，設 p r e = 383008016 pre=383008016 pre=383008016

令 a = 1 + 5 2 , b = 1 − 5 2 a=\frac{1+\sqrt{5}}{2},b=\frac{1-\sqrt{5}}{2} a=21+5

​​,b=21−5

​​，而且不難得到 a = ( p r e + 1 ) ∗ i n v ( 2 ) % p , b = ( 1 − p r e + p ) % p ∗ i n v ( 2 ) % p ; a=(pre+1)*inv(2)\%p, b=(1-pre+p)\%p*inv(2)\%p; a=(pre+1)∗inv(2)%p,b=(1−pre+p)%p∗inv(2)%p;

F ( n ) = i n v ( p r e ) ∗ ( a n − b n ) F(n)=inv(pre)*(a^n-b^n) F(n)=inv(pre)∗(an−bn)，那麼 F ( n ) k = i n v ( p r e ) k ∗ ( a n − b n ) k F(n)^k=inv(pre)^k*(a^n-b^n)^k F(n)k=inv(pre)k∗(an−bn)k此時對右式按二項式定理展開得到：

( a n − b n ) k = C k 0 ( a k ) n − C k 1 ( a k − 1 b ) n + . . . + C k k ( b k ) n (a^n-b^n)^k=C_k^0(a^k)^n-C_k^1(a^{k-1}b)^n+...+C_k^k(b^k)^n (an−bn)k=Ck0​(ak)n−Ck1​(ak−1b)n+...+Ckk​(bk)n

我們發現對于任意的 n n n展開後隻需要計算每一塊 ( − 1 ) x C k x ( a k − x b x ) y (-1)^xC_k^x(a^{k-x}b^x)^y (−1)xCkx​(ak−xbx)y，剩餘的項構成一個等比數列 ( − 1 ) x C k x [ ( a k − x b x ) c + ( a k − x b x ) 2 c + . . . + ( a k − x b x ) n c ] (-1)^xC_k^x[(a^{k-x}b^x)^c+(a^{k-x}b^x)^{2c}+...+(a^{k-x}b^x)^{nc}] (−1)xCkx​[(ak−xbx)c+(ak−xbx)2c+...+(ak−xbx)nc]，那麼設等比數列的和 S n S_n Sn​并設公比 t = ( a k − x b x ) c t=(a^{k-x}b^x)^c t=(ak−xbx)c，根據等比數列的求和公式直接可以得到 S n = t ( t n − 1 ) t − 1 S_n=\frac{t(t^n-1)}{t-1} Sn​=t−1t(tn−1)​(實際上第一項 F ( 0 ) k = 0 F(0)^k=0 F(0)k=0無需考慮)

那麼實際上就是周遊 x → [ 0 , k ] x→[0,k] x→[0,k]，對每一個 x x x求 S n S_n Sn​累加即可，最後不要忘了乘 i n v ( p r e ) k inv(pre)^k inv(pre)k

本題時間卡的很緊，比賽時過的代碼現在交已經 T L E TLE TLE了，對于組合數最好的方法是求階乘按定義解，這樣隻需要一次預處理階乘以及階乘的逆元。然後 n n n會很大可以歐拉降幂，再者就是每次計算時相當于是乘 b b b除 a a a，那麼遞推計算也行（比賽時寫的是遞推預處理 A i , B i , 0 ≤ i ≤ k A_i,B_i,0\leq i \leq k Ai​,Bi​,0≤i≤k但現在已經行不通了）

因為優化代碼時參考了其他部落格，這裡貼上連結：https://www.cnblogs.com/stelayuri/p/13357775.html

我自己的逾時代碼

無所謂吧此題我已經學到很多了

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=1e9+9;
const int maxn=1e5+10;

ll fac[maxn+10],inv[maxn+10];
ll a,b,pre,mod;

ll qkp(ll x,ll n,ll p){
    ll ans=1;
    x%=p;
    if(n>p) n=n%(p-1); //歐拉降幂
    while(n){
        if(n&1) ans=ans*x%p;
        x=x*x%p;
        n>>=1;
    }
    return ans;
}

void init(ll p){
    fac[0]=1LL;
    for(int i=1;i<maxn+10;i++)  //預處理階乘
        fac[i]=fac[i-1]*i%p;
    inv[maxn]=qkp(fac[maxn],p-2,p);
    for(int i=maxn-1;i>=0;i--)  //預處理階乘的逆元
        inv[i]=inv[i+1]*(i+1)%p;
    pre=383008016;
    a=(pre+1)*inv[2]%p;
    b=(1-pre+p)%p*inv[2]%p;
}

ll getC(int n,int m,ll p){  //得到C(n,m)
    return fac[n]*inv[m]%p*inv[n-m]%p;
}

ll solve(ll n,ll c,int k,ll p){
    ll ans=0;
    ll t1=qkp(a,c,p),t2=qkp(b,c,p);  //預處理a^c和b^c
    ll fa=qkp(t1,k,p),fb=1,inv_a=qkp(t1,p-2,p);  //得到第一次運算的a和b
    
    for(int i=0;i<=k;i++){
        ll t=fa*fb%p,res;
        
        if(t==1) res=n%p;
        else res=t*(qkp(t,n,p)-1)%p*qkp(t-1,p-2,p)%p;  //等比數列求和
        res=res*getC(k,i,p)%p;  //乘以組合數
        
        //判斷符号正負
        if(i&1) ans=(ans-res+p)%p;
        else ans=(ans+res)%p;
        
        fa=fa*inv_a%p;  //更新下次計算的a
        fb=fb*t2%p;   //更新下次計算的b
    }
    ll m=qkp(pre,p-2,p);  //最後乘上1/sqrt{5}的k次方
    ans=ans*qkp(m,k,p)%p;
    return ans;
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll n,c; int k,t;
    init(Mod);
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld%d",&n,&c,&k);
        printf("%lld\n",solve(n,c,k,Mod));
    }
    return 0;
}