对于斐波那契问题，一般想到的解法是递推或者矩阵快速幂，但是本题数据非常之大，怎么做都超时，临时想了一下斐波那契的公式，觉得这个浮点误差很大没法写，实际上可以写但是要用到很多知识，本题的总结收获不少（唯一难受的是代码优化能做的都做了自己写的还是超时）
首先给出斐波那契数列的公式：
F
(
n
)
=
1
5
[
(
1
+
5
2
)
n
−
(
1
−
5
2
)
n
]
F(n)=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n]
F
(
n
)
=
5
1
[
(
2
1
+
5
)
n
−
(
2
1
−
5
)
n
]
因为取模的数一般都是质数，而且我们能求出
x
2
≡
5
(
m
o
d
1
e
9
+
9
)
x^2 \equiv 5(mod~~1e9+9)
x
2
≡
5
(
m
o
d
1
e
9
+
9
)
是有解的，解出的两个解为
616991993
616991993
6
1
6
9
9
1
9
9
3
和
383008016
383008016
3
8
3
0
0
8
0
1
6
，这里我们采用第二个，也就是在这个取模的意义下二者是相等的，设
p
r
e
=
383008016
pre=383008016
p
r
e
=
3
8
3
0
0
8
0
1
6
令
a
=
1
+
5
2
,
b
=
1
−
5
2
a=\frac{1+\sqrt{5}}{2},b=\frac{1-\sqrt{5}}{2}
a
=
2
1
+
5
,
b
=
2
1
−
5
，而且不难得到
a
=
(
p
r
e
+
1
)
∗
i
n
v
(
2
)
%
p
,
b
=
(
1
−
p
r
e
+
p
)
%
p
∗
i
n
v
(
2
)
%
p
;
a=(pre+1)*inv(2)\%p, b=(1-pre+p)\%p*inv(2)\%p;
a
=
(
p
r
e
+
1
)
∗
i
n
v
(
2
)
%
p
,
b
=
(
1
−
p
r
e
+
p
)
%
p
∗
i
n
v
(
2
)
%
p
;
F
(
n
)
=
i
n
v
(
p
r
e
)
∗
(
a
n
−
b
n
)
F(n)=inv(pre)*(a^n-b^n)
F
(
n
)
=
i
n
v
(
p
r
e
)
∗
(
a
n
−
b
n
)
，那么
F
(
n
)
k
=
i
n
v
(
p
r
e
)
k
∗
(
a
n
−
b
n
)
k
F(n)^k=inv(pre)^k*(a^n-b^n)^k
F
(
n
)
k
=
i
n
v
(
p
r
e
)
k
∗
(
a
n
−
b
n
)
k
此时对右式按二项式定理展开得到：
(
a
n
−
b
n
)
k
=
C
k
0
(
a
k
)
n
−
C
k
1
(
a
k
−
1
b
)
n
+
.
.
.
+
C
k
k
(
b
k
)
n
(a^n-b^n)^k=C_k^0(a^k)^n-C_k^1(a^{k-1}b)^n+…+C_k^k(b^k)^n
(
a
n
−
b
n
)
k
=
C
k
0
(
a
k
)
n
−
C
k
1
(
a
k
−
1
b
)
n
+
.
.
.
+
C
k
k
(
b
k
)
n
我们发现对于任意的
n
n
n
展开后只需要计算每一块
(
−
1
)
x
C
k
x
(
a
k
−
x
b
x
)
y
(-1)^xC_k^x(a^{k-x}b^x)^y
(
−
1
)
x
C
k
x
(
a
k
−
x
b
x
)
y
，剩余的项构成一个等比数列
(
−
1
)
x
C
k
x
[
(
a
k
−
x
b
x
)
c
+
(
a
k
−
x
b
x
)
2
c
+
.
.
.
+
(
a
k
−
x
b
x
)
n
c
]
(-1)^xC_k^x[(a^{k-x}b^x)^c+(a^{k-x}b^x)^{2c}+…+(a^{k-x}b^x)^{nc}]
(
−
1
)
x
C
k
x
[
(
a
k
−
x
b
x
)
c
+
(
a
k
−
x
b
x
)
2
c
+
.
.
.
+
(
a
k
−
x
b
x
)
n
c
]
，那么设等比数列的和
S
n
S_n
S
n
并设公比
t
=
(
a
k
−
x
b
x
)
c
t=(a^{k-x}b^x)^c
t
=
(
a
k
−
x
b
x
)
c
，根据等比数列的求和公式直接可以得到
S
n
=
t
(
t
n
−
1
)
t
−
1
S_n=\frac{t(t^n-1)}{t-1}
S
n
=
t
−
1
t
(
t
n
−
1
)
(实际上第一项
F
(
0
)
k
=
0
F(0)^k=0
F
(
0
)
k
=
0
无需考虑)
那么实际上就是遍历
x
→
[
0
,
k
]
x→[0,k]
x
→
[
0
,
k
]
，对每一个
x
x
x
求
S
n
S_n
S
n
累加即可，最后不要忘了乘
i
n
v
(
p
r
e
)
k
inv(pre)^k
i
n
v
(
p
r
e
)
k
本题时间卡的很紧，比赛时过的代码现在交已经
T
L
E
TLE
T
L
E
了，对于组合数最好的方法是求阶乘按定义解，这样只需要一次预处理阶乘以及阶乘的逆元。然后
n
n
n
会很大可以欧拉降幂，再者就是每次计算时相当于是乘
b
b
b
除
a
a
a
，那么递推计算也行（比赛时写的是递推预处理
A
i
,
B
i
,
0
≤
i
≤
k
A_i,B_i,0\leq i \leq k
A
i
,
B
i
,
0
≤
i
≤
k
但现在已经行不通了）
因为优化代码时参考了其他博客，这里贴上链接：
https://www.cnblogs.com/stelayuri/p/13357775.html
我自己的超时代码
无所谓吧此题我已经学到很多了
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=1e9+9;
const int maxn=1e5+10;
ll fac[maxn+10],inv[maxn+10];
ll a,b,pre,mod;
ll qkp(ll x,ll n,ll p){
ll ans=1;
x%=p;
if(n>p) n=n%(p-1); //欧拉降幂
while(n){
if(n&1) ans=ans*x%p;
x=x*x%p;
n>>=1;
}
return ans;
}
void init(ll p){
fac[0]=1LL;
for(int i=1;i<maxn+10;i++) //预处理阶乘
fac[i]=fac[i-1]*i%p;
inv[maxn]=qkp(fac[maxn],p-2,p);
for(int i=maxn-1;i>=0;i--) //预处理阶乘的逆元
inv[i]=inv[i+1]*(i+1)%p;
pre=383008016;
a=(pre+1)*inv[2]%p;
b=(1-pre+p)%p*inv[2]%p;
}
ll getC(int n,int m,ll p){ //得到C(n,m)
return fac[n]*inv[m]%p*inv[n-m]%p;
}
ll solve(ll n,ll c,int k,ll p){
ll ans=0;
ll t1=qkp(a,c,p),t2=qkp(b,c,p); //预处理a^c和b^c
ll fa=qkp(t1,k,p),fb=1,inv_a=qkp(t1,p-2,p); //得到第一次运算的a和b
for(int i=0;i<=k;i++){
ll t=fa*fb%p,res;
if(t==1) res=n%p;
else res=t*(qkp(t,n,p)-1)%p*qkp(t-1,p-2,p)%p; //等比数列求和
res=res*getC(k,i,p)%p; //乘以组合数
//判断符号正负
if(i&1) ans=(ans-res+p)%p;
else ans=(ans+res)%p;
fa=fa*inv_a%p; //更新下次计算的a
fb=fb*t2%p; //更新下次计算的b
}
ll m=qkp(pre,p-2,p); //最后乘上1/sqrt{5}的k次方
ans=ans*qkp(m,k,p)%p;
return ans;
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll n,c; int k,t;
init(Mod);
scanf("%d",&t);
while(t--){
scanf("%lld%lld%d",&n,&c,&k);
printf("%lld\n",solve(n,c,k,Mod));
}
return 0;
}