[数学记录]51nod1236 序列求和 V3

· · 个人记录

题意 ： 设 F[n] 为斐波那契数列的第 n 项。

给出 n,k ，求下列式子的值 :

\sum\limits_{i=1}^nF[i]^k

答案对 10^9+9 取模。

多组数据，T\leq 10,n\leq 10^{18},k\leq 10^5，时限 \texttt{6s}。

考虑斐波那契数列的通项公式 ：

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

方便起见，设 r=\frac{\sqrt{5}}{5},a=\frac{1+\sqrt{5}}{2},b=\frac{1-\sqrt{5}}{2} ，则 F[n]=r(a^n-b^n)。

附 : \sqrt{5}=383008016\pmod{10^9+9}。

{\rm Ans}=\sum\limits_{i=1}^nF[i]^k =\sum\limits_{i=1}^n\big(r(a^i-b^i)\big)^k =\sum\limits_{i=1}^nr^k\sum\limits_{j=0}^k\dbinom{k}{j}a^{ij}(-b^{i})^{(k-j)} =r^k\sum\limits_{j=0}^k\dbinom{k}{j}(-1)^{k-j}\sum\limits_{i=1}^n(a^{j}b^{k-j})^{i}

后半部等比数列求和即可，复杂度 O(k\log n)。

#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 100500
using namespace std;
int mod=1000000009,w=383008016;
ll powM(ll a,int t=mod-2){
  ll ret=1;
  while(t){
    if (t&1)ret=ret*a%mod;
    a=a*a%mod;t>>=1;
  }return ret;
}
ll fac[MaxN],ifac[MaxN],pwa[MaxN],pwb[MaxN];
void Init(int n)
{
  fac[0]=1;
  for (int i=1;i<=n;i++)
    fac[i]=fac[i-1]*i%mod;
  ifac[n]=powM(fac[n]);
  for (int i=n;i;i--)
    ifac[i-1]=ifac[i]*i%mod;
  ll a=(1+w)*powM(2)%mod
    ,b=(1-w)*powM(2)%mod;
  pwa[0]=pwb[0]=1;
  for (int i=1;i<=n;i++){
    pwa[i]=pwa[i-1]*a%mod;
    pwb[i]=pwb[i-1]*b%mod;
  }
}
ll S(ll a,ll n){
  if (a==1)return n%mod;
  return a*(powM(a,n%(mod-1))-1)%mod*powM(a-1)%mod;
}
void solve(ll n,int k)
{
  ll ans=0;
  for (int i=0;i<=k;i++){
    ll buf=ifac[i]*ifac[k-i]%mod*S(pwa[i]*pwb[k-i]%mod,n);
    if ((k-i)&1)ans=(ans-buf)%mod;
    else ans=(ans+buf)%mod;
  }ans=(ans+mod)%mod;
  printf("%lld\n",ans*fac[k]%mod*powM(w,mod-1-k)%mod);
}
ll n[15];int T,k[15],lim;
int main()
{
  scanf("%d",&T);
  for (int i=1;i<=T;i++){
    scanf("%lld%d",&n[i],&k[i]);
    lim=max(lim,k[i]);
  }Init(lim);
  for (int i=1;i<=T;i++)
    solve(n[i],k[i]);
  return 0;
}