杭电多校第一场 1005 Fibonacci Sum 题解

题目大意

定义一个斐波那契数列

$F_0=0,F_1=1$

$F_n=F_{n-1}+F_{n-2}\ (n>1)$

求$(F_{0})^K+(F_{C})^K+(F_{2C})^K+\dots +(F_{NC})^{K}$。

解题思路

这题直接让我自闭好吧。

这是啥，基础数论，难度easy。。

我感觉我离退役不远了。

首先我们需要知道斐波那契数列的通项公式（这个我就不知道。。
$$
F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right)
$$
通过暴力，我们可以求出来，在$mod10^9+9$的情况下，与$\sqrt 5$同余的是383008016。

const int MOD=1e9+9;
for(int i=0;i<MOD;++i){
	if((long long)i*i%MOD == 5){
		cout<<i<<endl;//383008016
		break;
	}
}

通过快速幂，求出$\frac{1} {\sqrt 5}$的逆元是276601605。

然后，通项公式中还含有$ \large\frac{1+\sqrt 5}{2}$和$\large \frac{1-\sqrt 5}{2}$。

为了方便表示，可以令$\large a=\frac{1+\sqrt 5}{2},b = \frac{1-\sqrt 5}{2}$。

这个a和b的值的计算，我不是很懂。。

大致就是把a和b的值用$1+\sqrt 5$和$1-\sqrt 5$的同余乘以2的逆元，得出的结果就是691504013和308495997。

具体的可以去看这位大佬的博客。

讲解的很详细，很好。

总之，可以得出$a=691504013，b=308495997$。

这样，基础准备就已经做好了。

$\begin{align} \text{ans}&=\sum_{i=0}^{N}(F_{iC})^{K}\ &=\sum_{i=0}^{N}\left(\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{iC}-\left(\frac{1-\sqrt{5}}{2}\right)^{iC}\right)\right)^K\ &=\left(\frac{1}{\sqrt{5}}\right)^K\cdot \sum_{i=0}^{N}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{iC}-\left(\frac{1-\sqrt{5}}{2}\right)^{iC}\right)^{K} \end{align}$

为了方便表示，令$A=\left(\frac{1+\sqrt{5}}{2}\right)^C,B=\left(\frac{1-\sqrt{5}}{2}\right)^C$。

这样，答案就变成了$\large \left(\frac{1}{\sqrt{5}}\right)^K\sum_{i=0}^{N}(A^i-B^i)^K$。

前面那一项，我们可以用快速幂求出来。

只需要求出后面那一项即可。

对此可以进行二项式展开。

过程同上面那个大佬博客中的二项式展开类似。

就是从n变成了cn。

$\large (A-B)^k = C_k^0A^k - C_k^1A^{k-1}B^1 + \cdots + (-1)^iC_k^iA^{k-i}B^i + \cdots +(-1)^kC_k^kB^k (n \in N^*)$

这样，对于不同的斐波那契项，相同位置的二次项展开数，构成了一个等比数列。

对于每一项来说，公比$\large q=a^{c(k-i)}b^{ci}$。

其前n项和公式为
$$
\large S_n=\frac{(-1)^i·c_k^i·a^{c(k-i)}·b^{ci}·(1-a^{cn(k-i)}·b^{cni})}{1-a^{c(k-i)}b^{ci}}
$$
接着只需要从0枚举到k，把每项用求和公式求出来相加即可。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const ll maxn = 1e5 + 5, mod = 1e9 + 9, N = 1e5;
ll A = 691504013, B = 308495997;
ll sqrt5 = 383008016, invsqrt5 = 276601605;
ll fac[maxn], finv[maxn];
ll sac[maxn], sbc[maxn];

ll qpow(ll a, ll b) {
	ll ans = 1;
	a %= mod;
	while (b) {
		if (b & 1)	ans = (ans * a % mod) % mod;
		a = (a * a) % mod, b >>= 1;
	}
	return ans;
}

ll C(ll a, ll b) {
	if (a < b)	return 0;
	if (!b || a == b)	return 1;
	return ((fac[a] * finv[a - b]) % mod * finv[b]) % mod;
}

void init() {
	fac[1] = 1;
	for (ll i = 2; i <= N; i++)	fac[i] = (fac[i - 1] * i)%mod;
	finv[N] = qpow(fac[N], mod - 2);
	for (ll i = N - 1; i >= 0; i--)	finv[i] = (finv[i + 1] * (i + 1)) % mod;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	init();
	int t;
	cin >> t;
	while (t--) {
		ll n, c, k;
		cin >> n >> c >> k;
		ll ans = 0, flag = -1;
		ll ac = qpow(A, c), bc = qpow(B, c);
		sac[0] = sbc[0] = 1;
		for (int i = 1; i <= k; i++) {
			sac[i] = sac[i - 1] * ac % mod;
			sbc[i] = sbc[i - 1] * bc % mod;
		}
		ll acn = qpow(ac, n), bcn = qpow(bc, n), acninv = qpow(acn, mod - 2);
		ll now_acn = qpow(acn, k), now_bcn = 1;
		ll x, y;
		for (ll i = 0; i <= k; i++) {
			flag *= -1;
			ll q = sac[k - i] * sbc[i] % mod;
			if (q == 1) {
				ll t = C(k, i) * (n % mod) % mod;
				ans = (ans + (flag * t) % mod + mod) % mod;
			}
			else {
				x = ((C(k, i) * sac[k - i]) % mod * sbc[i]) % mod;
				x = (x * (1 - (now_acn * now_bcn % mod) + mod) % mod) % mod;
				y = (1 - q) % mod;
				y = qpow(y, mod - 2);
				ans = (ans + flag * x * y % mod + mod) % mod;
			}
			now_acn = (now_acn * acninv) % mod;
			now_bcn = (now_bcn * bcn) % mod;
		}
		ll mul = qpow(invsqrt5, k);
		cout << (ans * mul) % mod << endl;
	}
	return 0;
}