题目链接
题解
用特征方程求得斐波那契通项：
\[f(n) = \frac{(\frac{1 + \sqrt{5}}{2})^{n} - (\frac{1 - \sqrt{5}}{2})^{n}}{\sqrt{5}}
\]
\]
那么
\[\begin{aligned}
ans &= \sum\limits_{i = 1}^{n} (\frac{(\frac{1 + \sqrt{5}}{2})^{i} - (\frac{1 - \sqrt{5}}{2})^{i}}{\sqrt{5}})^{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}{k \choose 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}{k \choose j}(-1)^{k - j}\sum\limits_{i = 1}^{n} (\frac{1 + \sqrt{5}}{2})^{ij}(\frac{1 - \sqrt{5}}{2})^{i(k - j)} \\
&= (\frac{1}{\sqrt{5}})^{k}\sum\limits_{j = 0}^{k}{k \choose j}(-1)^{k - j}\sum\limits_{i = 1}^{n} ((\frac{1 + \sqrt{5}}{2})^{j}(\frac{1 - \sqrt{5}}{2})^{k - j})^{i}
\end{aligned}
\]
ans &= \sum\limits_{i = 1}^{n} (\frac{(\frac{1 + \sqrt{5}}{2})^{i} - (\frac{1 - \sqrt{5}}{2})^{i}}{\sqrt{5}})^{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}{k \choose 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}{k \choose j}(-1)^{k - j}\sum\limits_{i = 1}^{n} (\frac{1 + \sqrt{5}}{2})^{ij}(\frac{1 - \sqrt{5}}{2})^{i(k - j)} \\
&= (\frac{1}{\sqrt{5}})^{k}\sum\limits_{j = 0}^{k}{k \choose j}(-1)^{k - j}\sum\limits_{i = 1}^{n} ((\frac{1 + \sqrt{5}}{2})^{j}(\frac{1 - \sqrt{5}}{2})^{k - j})^{i}
\end{aligned}
\]
后面用等比数列求和即可
复杂度\(O(klogn)\)
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 0x3f3f3f3f,P = 1000000009;
inline LL read(){
LL out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
return flag ? out : -out;
}
const LL s5 = 383008016;
LL N,K,fac[maxn],inv[maxn],fv[maxn],v1[maxn],v2[maxn];
void init(){
fac[0] = fac[1] = inv[0] = inv[1] = fv[0] = fv[1] = 1;
v1[0] = v2[0] = 1;
for (int i = 2; i < maxn; i++){
fac[i] = fac[i - 1] * i % P;
inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
fv[i] = fv[i - 1] * inv[i] % P;
}
v1[1] = (1 + s5) * inv[2] % P; v2[1] = ((1 - s5) % P + P) % P * inv[2] % P;
for (int i = 2; i < maxn; i++){
v1[i] = v1[i - 1] * v1[1] % P;
v2[i] = v2[i - 1] * v2[1] % P;
}
}
inline LL qpow(LL a,LL b){
LL re = 1; a %= P;
for (; b; b >>= 1,a = a * a % P)
if (b & 1) re = re * a % P;
return re;
}
inline LL Inv(LL a){
if (a < maxn) return inv[a];
return qpow(a,P - 2);
}
inline LL C(LL n,LL m){
if (m > n) return 0;
return fac[n] * fv[m] % P * fv[n - m] % P;
}
int main(){
init();
int T = read();
while (T--){
N = read(); K = read(); LL ans = 0;
for (int j = 0; j <= K; j++){
LL t,tmp;
t = v1[j] * v2[K - j] % P;
tmp = t == 1 ? N % P : ((qpow(t,N + 1) - t) % P + P) % P * Inv(t - 1) % P;
tmp = tmp * C(K,j) % P;
if ((K - j) & 1) ans = (ans + P - tmp) % P;
else ans = (ans + tmp) % P;
}
printf("%lld\n",ans * qpow(s5,K * (P - 2)) % P);
}
return 0;
}