【日常小测】题目1

相关链接

题目传送门：http://paste.ubuntu.com/24087405/
数据生成器：http://paste.ubuntu.com/24087409/
std：http://paste.ubuntu.com/24087412/

题目大意

求$\sum_{i=1}^n{f_i^k}$
其中$f_x$为第$x$项$Fibonacci$数
$n \le 1e18, k \le 1e5$

解题报告

之前鏼爷讲过二次剩余，于是看到这个模数就知道方向了
在暴力求出$\sqrt 5$的二次剩余后，我们可以推出答案长这样
$$\sum_{j=0}^{k}{(-1)^{k-j} \cdot C_k^j \sum_{i-1}^n{(A^jB^{k-j})^i}}$$
于是我们搞一搞组合数，逆元什么的这题就做完啦！

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000009;
const int A = 691504013;
const int B = 308495997;
const int REV_SQRT_FIVE = 276601605;
const int N = 100009;

int k,vout,PA[N],PB[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int Pow(int w, LL t) {
	int ret = 1;
	for (;t;t>>=1,w=(LL)w*w%MOD) 
		if (t & 1) ret = (LL)ret * w % MOD;
	return ret;
}

inline int Mul(int a, LL b) {
	int ret = 0;
	for (;b;b>>=1,(a<<=1)%=MOD)
		if (b & 1) (ret += a) %= MOD;
	return ret;
}

int main() {
	freopen("A.in","r",stdin); 
	freopen("A.out","w",stdout); 
	LL n; cin>>n; k = read();
	PA[0] = PB[0] = 1;
	for (int i=1;i<=k;i++) {
		PA[i] = (LL)PA[i-1] * A % MOD;
		PB[i] = (LL)PB[i-1] * B % MOD;
	}
	for (int i=0,c=1,v;i<=k;i++) {
		v = (LL)PA[i] * PB[k-i] % MOD; 
		if (v == 1) v = Mul(v, n);
		else v = ((LL)Pow(v, n+1) - v) * Pow(v-1, MOD-2) % MOD;
		if (k-i & 1) (vout -= (LL)c * v % MOD) %= MOD;
		else (vout += (LL)c * v % MOD) %= MOD;
		c = ((LL)c * (k - i) % MOD) * Pow(i+1, MOD-2) % MOD; 
	} 
	printf("%d\n",((LL)vout*Pow(REV_SQRT_FIVE,k)%MOD+MOD)%MOD);
	return 0;
}