求斐波那契数列k次幂和

二次剩余+快速幂+离线阶乘逆元。朝鲜人的考古题，快速幂年年有，啥时候把这题改成光速幂版本，又能卡死一群。

向金日成综合大学的巨巨们低头。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6  
 7 const int P=1000000009;
 8 const int INV2=500000005;
 9 const int SQRT5=383008016;
10 const int INVSQRT5=276601605;
11 
12 ll A0=691504013;
13 ll B0=308495997;
14 
15 ll A=691504013;
16 ll B=308495997;
17  
18 const int N=100005;
19 
20 ll n,K;
21 ll fac[N],inv[N];
22 ll pa[N],pb[N];
23 
24 inline void Pre(int n){
25   fac[0]=1; for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%P;
26   inv[1]=1; for (int i=2;i<=n;i++) inv[i]=(P-P/i)*inv[P%i]%P;
27   inv[0]=1; for (int i=1;i<=n;i++) inv[i]=inv[i]*inv[i-1]%P;
28 }
29 
30 inline void Pre2(int n){
31   pa[0]=1; for (int i=1;i<=n;i++) pa[i]=pa[i-1]*A%P;
32   pb[0]=1; for (int i=1;i<=n;i++) pb[i]=pb[i-1]*B%P;
33 }
34  
35 inline ll C(int n,int m){
36   return fac[n]*inv[m]%P*inv[n-m]%P;
37 }
38  
39 inline ll Pow(ll a,ll b){
40   ll ret=1;
41   for (;b;b>>=1,a=a*a%P)
42     if (b&1)
43       ret=ret*a%P;
44   return ret;
45 }
46  
47 inline ll Inv(ll x){
48   return Pow(x,P-2);
49 }
50  
51 inline void Solve(){
52   ll Ans=0;
53   for (int j=0;j<=K;j++){
54     ll t=pa[K-j]*pb[j]%P,tem;
55     tem=t==1?n%P:t*(Pow(t,n)-1+P)%P*Inv(t-1)%P;
56     if (~j&1)
57       Ans+=C(K,j)*tem%P,Ans%=P;
58     else
59       Ans+=P-C(K,j)*tem%P,Ans%=P;
60   }
61   Ans=Ans*Pow(INVSQRT5,K)%P;
62   printf("%lld
",Ans);
63 }
64  
65 int main(){
66   int T;
67   Pre(100000);
68   scanf("%d",&T);
69   ll c;
70   while (T--){
71     scanf("%lld%lld%lld",&n,&c,&K);
72     A=Pow(A0,c);
73     B=Pow(B0,c);
74     Pre2(K);
75     Solve();
76   }
77 }