盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

ZOJ 3774 Power of Fibonacci(斐波那契数列的幂和)

题目

源地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5237

题意

求前n项斐波那契数的k次幂和

思路

http://blog.csdn.net/acdreamers/article/details/23039571
由于5是1000000009的二次剩余,所以可以用一个整数来代替sqrt(5) mod 1000000009
要注意在求等比数列时q=1的情况

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define INF 1 << 30
#define fi first
#define se second
#define debug puts("=====================");
using namespace std;
typedef long long ll;
const int N = 100005;
const ll mod = 1e9 + 9;
const ll a = 691504013; ///a = (1+sqrt(5))/2
const ll b = 308495997; ///a = (1-sqrt(5))/2
#define M 100001
ll inv[N], ba[N], rba[N], A[N], B[N], m;
ll pow_mod(ll a, ll x, ll p) {
ll res = 1;
while(x) {
if (x & 1) res = res * a % p;
x >>= 1;
a = a * a % p;
}
return res;
}
void init() {
inv[0] = inv[1] = 1;
ba[0] = ba[1] = 1;
rba[0] = rba[1] = 1;
A[0] = B[0] = 1;
A[1] = a, B[1] = b;
for (int i = 2; i < M; i++) {
inv[i] = ((mod - mod / i) * inv[mod % i]) % mod;
ba[i] = (ba[i - 1] * i) % mod;
rba[i] = (rba[i - 1] * inv[i]) % mod;
A[i] = (A[i - 1] * a) % mod;
B[i] = (B[i - 1] * b) % mod;
}
m = pow_mod(383008016, mod - 2, mod); ///383008016 = sqrt(5), m = 1/sqrt(5)
}
ll C(int n, int k) {
return (ba[n] * rba[k] % mod ) * rba[n - k] % mod;
}
ll solve(ll n, ll k) {
ll ans = 0;
for (int r = 0; r <= k; r++) {
ll t = A[k - r] * B[r] % mod;
ll c = C(k, r);
ll tmp = n % mod;
if (t != 1) tmp = t * (pow_mod(t, n, mod) - 1) % mod * pow_mod(t - 1, mod - 2, mod) % mod;
tmp = tmp * c % mod;
if (r & 1) ans -= tmp;
else ans += tmp;
ans %= mod;
}
ans = ans * pow_mod(m, k, mod) % mod;
ans = (ans + mod) % mod;
return ans;
}
int main () {
int t;
ll n, k;
init();
cin>>t;
while(t--) {
scanf("%lld%lld", &n, &k);
printf("%lld\n", solve(n, k));
}
return 0;
}