[数学记录]51nod1236 序列求和 V3
command_block
2020-11-20 21:59:37
**题意** ： 设 $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)$。
```cpp
#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;
}
```