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

HDU 4959 Poor Akagi(卢卡斯数+二次域运算+等比数列求和)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=4959

题意

求前n项卢卡斯数的k次幂和

思路

http://blog.csdn.net/ahm001/article/details/38724607
其实知道了卢卡斯数的通项公式,就比较容易计算了。这道题目因为sqrt(5)不是1000000007的二次剩余,所以就不能够用之前把sqrt(5)当做一个整数的方式来处理。
但是可以用定义二次域运算的方式来处理此题,重定义二次域上的运算

代码

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#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 + 7;
#define pll pair<ll, ll>
pll operator + (pll a, pll b) {
a.fi = (a.fi + b.fi) % mod;
a.se = (a.se + b.se) % mod;
return a;
}
pll operator * (pll a, pll b) {
pll c;
c.fi = (a.fi * b.fi + 5 * a.se * b.se) % mod;
c.se = (a.fi * b.se + a.se * b.fi) % mod;
return c;
}
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;
}
pll operator / (pll a, pll b) {
pll c = a * pll(b.fi, (mod - b.se) % mod);
ll multi = ((b.fi * b.fi - 5 * b.se * b.se) % mod + mod) % mod;
return c * pll(pow_mod(multi, mod - 2, mod), 0);
}
pll pow_mod(pll a, ll x) {
pll res(1, 0);
while(x) {
if (x & 1) res = res * a;
x >>= 1;
a = a * a;
}
return res;
}
ll inv[N], ba[N], rba[N];
#define M 100001
void init() {
inv[0] = inv[1] = 1;
ba[0] = ba[1] = 1;
rba[0] = rba[1] = 1;
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;
}
}
ll C(int n, int k) {
return (ba[n] * rba[k] % mod) * rba[n - k] % mod;
}
int main () {
ll rev2 = pow_mod(2, mod - 2, mod);
pll a(rev2, (mod - 1) * rev2 % mod);
pll b(rev2, rev2);
init();
int t;
ll n, k;
scanf("%d", &t);
while(t--) {
scanf("%I64d%I64d", &n, &k);
pll ans(0, 0);
for (int i = 0; i <= k; i++) {
ll c = C(k, i);
pll q = pow_mod(a, i) * pow_mod(b, k - i);
pll qn = pow_mod(q, n + 1);
pll e(mod - 1, 0);
pll s;
if (q.first == 1 && q.second == 0) s = q * pll((n + 1) % mod * c % mod, 0);
else s = (qn + e) / (q + e) * pll(c, 0);
ans = ans + s;
}
printf("%d\n", (ans.first + mod) % mod);
}
return 0;
}