51nod_1236_序列求和 V3 _组合数学
Fib(n)表示斐波那契数列的第n项，Fib(n) = Fib(n-1) + Fib(n-2)。Fib(0) = 0, Fib(1) = 1。
(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...)
F(n, k) = Fib(n)^k（Fib(n)的k次幂）。
S(n, k) = F(1, k) + F(2, k) + ...... F(n, k)。
例如：S(4, 2) = 1^2 + 1^2 + 2^2 + 3^2 = 15。
给出n和k，求S(n, k) Mod 1000000009的结果。
大力展开题.....
fib的通项是$f(n)=\frac{1}{\sqrt 5}((\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n)$
$S(n,k)=\frac{1}{\sqrt 5^k}\sum\limits_{i=1}^{n}((\frac{1+\sqrt 5}{2})^i-(\frac{1-\sqrt 5}{2})^i)^k$
$=\frac{1}{\sqrt 5^k}\sum\limits_{i=1}^{n}\sum\limits_{j=0}^{k}C(k,j)*(-1)^{k-j}*(\frac{1+\sqrt 5}{2})^{ij}*(\frac{1-\sqrt 5}{2})^{i(k-j)}$
$=\frac{1}{\sqrt 5^k}\sum\limits_{j=0}^{k}C(k,j)*(-1)^{k-j}\sum\limits_{i=1}^{n}(\frac{1+\sqrt 5}{2})^{ij}*(\frac{1-\sqrt 5}{2})^{i(k-j)}$
后面是一个等比数列求和的形式。
根号5有两种解决办法，第一种是找到一个k,使得k*k mod p=5。
第二种是把$a+b\sqrt 5$当成一个int。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long ll;
#define mod 1000000009
#define N 100050
#define G5 383008016
ll fac[N],inv[N];
ll P,Q;
ll qp(ll x,ll y) {
x=(x%mod+mod)%mod;
ll re=1; for(;y;y>>=1ll,x=x*x%mod) if(y&1ll) re=re*x%mod; return re;
}
void init() {
int i;
for(fac[0]=1,i=1;i<=100000;i++) fac[i]=fac[i-1]*i%mod;
inv[100000]=qp(fac[100000],mod-2);
for(i=99999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
ll C(ll n,ll m) {
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
ll Sum(ll x,ll n) {
if(x==1) return n%mod;
if(x==0) return 0;
return (qp(x,n+1)-x)%mod*qp(x-1,mod-2)%mod;
}
ll solve(ll n,int K) {
int j; ll ans=0;
for(j=0;j<=K;j++) {
int opt=((K-j)&1)?-1:1;
ll t1=C(K,j),t2=opt,t3=Sum(qp(P,j)*qp(Q,K-j)%mod,n);
ans=((ans+t1*t2%mod*t3%mod)%mod+mod)%mod;
}
return ans;
}
int main() {
init();
ll i2=qp(2,mod-2);
P=(1+G5)*i2%mod; Q=((1-G5)*i2%mod+mod)%mod;
int T;
ll n; int K;
scanf("%d",&T);
ll ig5=qp(G5,mod-2);
while(T--) {
scanf("%lld%d",&n,&K);
printf("%lld\n",qp(ig5,K)*solve(n,K)%mod);
}
}