题目大意

设 Fibonacci 数列第 $i$ 项为 $F_i$，求

$$ S = \sum_{i = 0}^n (F_{i c})^k $$

分析

由特征方程法，设

$$ x^2 + x - 1 = 0 \Longrightarrow A, B = \frac{1 \pm \sqrt{5}}{2} $$

因此 Fibonacci 通项公式即可表示为

$$ F_n = \frac{A^n - B^n}{A - B} $$

根据二次剩余的知识，模意义下是可以开方的。因此

$$ (F_{i c})^k = \left( \frac{A^{i c} - B^{i c}}{A - B} \right)^k = \frac{1}{(A - B)^k} \sum_{j = 0}^k \binom{k}{j} (- 1)^{k - j} (A^j B^{k - j})^{i c} $$

求和有

$$ (A - B)^k S = (A - B)^k \sum_{i = 0}^n (F_{i c})^k = \sum_{i = 0}^n \sum_{j = 0}^k \binom{k}{j} (- 1)^{k - j} (A^j B^{k - j})^{i c} $$

换序求和，即是等比数列（公比可能为 $1$，需要特判）

$$ \begin{aligned} (A-B)^{k}S & =\sum_{j=0}^{k}\binom{k}{j}(-1)^{k-j}\sum_{i=0}^{n}(A^{j}B^{k-j})^{ic}\\ & =\sum_{j=0}^{k}\binom{k}{j}(-1)^{k-j}{\frac{(A^{j}B^{k-j})^{c(n+1)}-1}{(A^{j}B^{k-j})^{c}-1}} \end{aligned} $$

直接计算会 TLE，需要用中间变量简化

$$ \frac{(A^j B^{k - j})^{c (n + 1)} - 1}{(A^j B^{k - j})^c - 1} = \frac{B^{k c (n + 1)} {(A B^{- 1})^{c (n + 1) j}} - 1}{B^{k c} (A B^{- 1})^{c j} - 1} $$

用中间变量在循环中递推，再加上 Euler 降幂，就可以过题了。

const ll mod = 1e9 + 9, phi_mod = mod - 1;
const ll maxn = 1e5 + 10;
#define ACM_MOD mod

#include "template/basic/qpow.hpp"
#include "template/basic/inv.hpp"

const ll sqrt_5 = 383008016;
const ll A = (1 + sqrt_5) * inv(2) % mod, B = (1 - sqrt_5 + mod) * inv(2) % mod;

ll euler_pow(ll a, ll b) {
	return qpow(a, b % phi_mod);
}

ll fac[maxn], ind[maxn];
void pre(ll n) {
	fac[0] = 1;
	for (ll i = 1; i <= n; i++) {
		fac[i] = fac[i - 1] * i % mod;
	}
	ind[n] = inv(fac[n]);
	for (ll i = n - 1; i >= 0; i--) {
		ind[i] = ind[i + 1] * (i + 1) % mod;
	}
}

ll binom(ll a, ll b) {
	if (b > a)
		b = a - b;
	return fac[a] * ind[b] % mod * ind[a - b] % mod;
}

int main() {
	pre(1e5 + 1);
	ll ttt = rr();
	while (ttt--) {
		ll n = rr(), c = rr(), k = rr();
		ll step1 = euler_pow(A * inv(B) % mod, c), step2 = euler_pow(step1, n + 1);
		ll T1 = euler_pow(B, c % phi_mod * k), T2 = euler_pow(T1, n + 1);
		ll ans = 0;
		for (ll j = 0; j <= k; j++) {
			ll tsum = binom(k, j);
			if (T1 != 1) {
				tsum = tsum * (T2 - 1) % mod * inv(T1 - 1) % mod;
			} else {
				tsum = (n + 1) % mod * tsum % mod;
			}
			if ((k - j) % 2 == 1)
				tsum *= -1;
			ans = (ans + tsum + mod) % mod;
			T1 = T1 * step1 % mod, T2 = T2 * step2 % mod;
		}
		ans = ans % mod * euler_pow(inv(A - B), k) % mod;
		printf("%lld\n", ans);
	}
	return 0;
}