## 【数论】Fibonacci Sum – 20HDU多校1-5

### 传送门

383008016^2 ≡616991993^2≡5 (mod 10^9+9)

F_n=C(A^n-B^n)

F_{cn}^k=C^k(A^{cn}-B^{cn})^k

\sum\limits_{i=0}^n F_{ci}^k=C^k\sum\limits_{i=0}^n(A^{ci}-B^{ci})^k

\sum\limits_{i=0}^nF_{ci}^k= C^k\sum\limits_{i=0}^n \sum\limits_{r=0}^k \binom{k}{r}(A^{ci(k-r)}B^{cir}(-1)^r)

\sum\limits_{i=0}^nF_{ci}^k= C^k \sum\limits_{r=0}^k \binom{k}{r} (-1)^r \sum\limits_{i=0}^n (A^{ci(k-r)}B^{cir})

• 注意本题从0累加到n实际上有n + 1项，求几何级数的时候需要注意。但是第0项等于0，所以也可以看作从1开始枚举，用通项的时候单独减去1。两种处理方法都可以。

• 第二个需要注意的点是公式仅适用于r =\not 1。如果r=1直接用r * n或者r*(n+1)即可。取决于上面一步是什么处理方法。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 9;
const int C = 276601605; // 1 / sqrt(5)
const int A = 691504013; // (1 + sqrt(5)) / 2
const int AA = 691504012; // A ^ -1
const int B = 308495997; // (1 - sqrt(5)) / 2
const int maxn = 1e5 + 233;
LL f[maxn], finv[maxn];

inline int ksm(int n, int k)
{
n %= mod;
int res = 1;
while(k)
{
if(k & 1) res = (LL)res * n % mod;
n = (LL)n * n % mod;
k >>= 1;
}
return res % mod;
}

void init(int n) {
f[0] = 1;
for(int i = 1; i <= n; i++) {
f[i] = 1LL*f[i-1]*i%mod;
}
finv[n] = ksm(f[n], mod-2);
for(int i = n; i > 0; i--) {
finv[i-1] = 1LL*finv[i]*i%mod;
}
}
inline int Comb(int n, int m) {
if(m > n) return 0;
return 1LL*f[n]*finv[m]%mod*finv[n-m]%mod;
}

int main()
{
init(100001);

cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
// freopen("t.txt", "w", stdout);
int T; cin >> T;
// int base = 10;
while(T--)
{
LL n, c;
int k; cin >> n >> c >> k;
int ans = 0;
int R1 = ksm(A, c % (mod - 1) * k % (mod - 1) );
int R2 = ksm(B, c % (mod - 1) * 0 % (mod - 1) );
int invR1 = ksm(ksm(A, c % (mod - 1)), mod - 2);
int uniR2 = ksm(B, c % (mod - 1));
for(int i = 0; i <= k; i++)
{
int Co = Comb(k, i);
if(i & 1) Co = mod - Co;
// int R = ksm(A, (c % (mod - 1) * (k - i) % (mod - 1)), base) * ksm(B, c % (mod - 1) * i % (mod - 1), base) % mod;
int R = (LL)R1 * R2 % mod;
// 1 + R + R^2 + ... + R^n = S(n + 1)
// cerr << R << endl;
int n1 = (n + 1) % (mod - 1);
if(R == 1) ans = ((LL)ans + n % mod * Co % mod) % mod;
else
{
int S = (ksm(R, n1) - 1LL) * ksm(R - 1, mod - 2) % mod;
S = S - 1; // F1 ~ FN except 1
ans = ((LL)ans + (LL)Co * S % mod) % mod;
}
R1 = (LL)R1 * invR1 % mod;
R2 = (LL)R2 * uniR2 % mod;
}
cout << ((LL)ans * ksm(C, k) % mod + mod) % mod << endl;
}

}