2020 Multi-University Training Contest 1---- HDU--6755、Fibonacci Sum（数论、二次剩余、二项式展开）

题目链接

题面：

题意：
求
${\sum }_{i=0}^n(F_{c\ast i}{)}^{k}mod1000000009$∑i=0n​(Fc∗i​)k mod 1000000009
c,n<=1e18,k<=1e5

题解：
首先认识到，1000000009 是一个质数，且 5 是模 1000000009 的二次剩余，即 $x^2=5\left(mod1000000009\right)$x2=5(mod 1000000009) 有解，那么我们解出 x 来就可以代替 $\sqrt{5}$5 ​ 进行计算。

①斐波那契通项：
$F_n=\frac{1}{\sqrt{5}}\left[\right(\frac{1+\sqrt{5}}{2}{)}^n-\left(\frac{1-\sqrt{5}}{2}{)}^n\right]$Fn​=5 ​1​[(21+5 ​​)n−(21−5 ​​)n]

②、
$我们令a=\frac{1+\sqrt{5}}{2},b=\frac{1-\sqrt{5}}{2})$我们令a=21+5 ​​,b=21−5 ​​)
$有F_n=\frac{1}{\sqrt{5}}(a^n-b^n)-->F_n^k=\left(\frac{1}{\sqrt{5}}{)}^k\right(a^n-b^n{)}^k$有Fn​=5 ​1​(an−bn)−−>Fnk​=(5 ​1​)k(an−bn)k

把 $(a^n-b^n{)}^k$(an−bn)k 二项式展开有
$(a^n-b^n{)}^k=C_k^0(a^n{)}^k(-b^n{)}^0+C_k^1(a^n{)}^{k-1}(-b^n{)}^1+...+C_k^r(a^n{)}^{k-r}(-b^n{)}^r+...+C_k^k(a^n{)}^0(-b^n{)}^k$(an−bn)k=Ck0​(an)k(−bn)0+Ck1​(an)k−1(−bn)1+...+Ckr​(an)k−r(−bn)r+...+Ckk​(an)0(−bn)k

化简后有：
$(a^n-b^n{)}^k=(-1{)}^0{C}_k^0\left(a^n{)}^k\right(b^n{)}^0+(-1{)}^1{C}_k^1(a^n{)}^{k-1}(b^n{)}^1+...+(-1{)}^r{C}_k^r\left(a^n{)}^{k-r}\right(b^n{)}^r+...+(-1{)}^k{C}_k^k(a^n{)}^0(b^n{)}^k$(an−bn)k=(−1)0Ck0​(an)k(bn)0+(−1)1Ck1​(an)k−1(bn)1+...+(−1)rCkr​(an)k−r(bn)r+...+(−1)kCkk​(an)0(bn)k

对于每一个 $(F_{c\ast i}{)}^k$(Fc∗i​)k都这样表示，那么 $(-1{)}^r{C}_k^r$(−1)rCkr​项合并后为等比数列。（其中 i == 0 时， $(F_{c\ast i}{)}^k$(Fc∗i​)k为0，可以忽略）。

等比数列 $a_1=a^{c\ast (k-r)}{b}^{c\ast \left(r\right)},q=a^{c\ast (k-r)}{b}^{c\ast \left(r\right)},n=n$a1​=ac∗(k−r)bc∗(r),q=ac∗(k−r)bc∗(r),n=n
那么求和为， $sum=(-1{)}^r{C}_k^r\ast \frac{q\ast (q^n-1)}{q-1}$sum=(−1)rCkr​∗q−1q∗(qn−1)​

当 $q\ne 1$q​=1时，可以直接用公式计算
当 $q=1$q=1时，就是长度为 n 的首项为 1 的常数列。

③、
$x^2=5\left(mod1000000009\right)$x2=5(mod 1000000009)的一个解 $x=383008016$x=383008016
在模1e9+9的意义下， $inv\left(2\right)=500000005$inv(2)=500000005
那么 $a=(1+\sqrt{5})\ast inv\left(2\right)=691504013,b=(1-\sqrt{5})\ast inv\left(2\right)=308495997$a=(1+5 ​)∗inv(2)=691504013,b=(1−5 ​)∗inv(2)=308495997

代码：
原来的代码比赛的时候过了来着，赛后再交就TLE，又各种优化，各种预处理。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+9;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxm=100100;
const int up=100000;
const int inv2=500000005;
const int sqrt5=383008016;
const int invsqrt5=276601605;
const int A=691504013;
const int B=308495997;


int fac[maxn],inv[maxn];

int mypow(int a,ll b)
{
    b%=mod-1;
    int ans=1;
    while(b)
    {
        if(b&1) ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return ans;
}

void init(void)
{
    fac[0]=1;
    for(int i=1;i<maxn;i++)
        fac[i]=1ll*fac[i-1]*i%mod;
    inv[maxn-1]=mypow(fac[maxn-1],mod-2);
    for(int i=maxn-2;i>=0;i--)
        inv[i]=1ll*inv[i+1]*(i+1)%mod;
}

int C(int n,int m)
{
    return 1ll*fac[n]*inv[n-m]%mod*inv[m]%mod;
}

int main(void)
{
    int tt;
    scanf("%d",&tt);
    init();
    ll n,k,c,ans,res;
    int q,tmp;
    while(tt--)
    {
        scanf("%lld%lld%lld",&n,&c,&k);
        ans=0;
        q=mypow(mypow(A,k),c);
        tmp=mypow(1ll*B*mypow(A,mod-2)%mod,c);
        for(int i=0;i<=k;i++,q=1ll*q*tmp%mod)
        {
            if(q==1) res=n%mod*C(k,i)%mod;
            else res=1ll*q*(mypow(q,n)-1)%mod*mypow(q-1,mod-2)%mod*C(k,i)%mod;
            if(i&1) ans=(ans-res+mod)%mod;
            else ans=(ans+res)%mod;
        }
        ans=ans*mypow(invsqrt5,k)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}