给定 $n, k$ ,设 $a_1 = 1, a_x = \sum_{i=1}^{x-1}a_i + x^k$ ,求 $a_n$ 对 $10^9 + 7$ 取模的结果。
BZOJ 5015

题解

考虑矩阵快速幂。注意到 $a_x$ 的值与前 $x - 1$ 项的和有关,用 $a_x - a_{x - 1}$ 得到递推公式
$$a_{x+1} = 2a_x + (x+1)^k - x^k$$
需要通过线性组合表示 $(x+1)^k$ 。考虑二项式定理,由于
$$(x+1)^k = \sum_{i=0}^k C_k^i x^i$$
从而可以将 $(x+1)^k$ 表示为 $x_0, x_1, \ldots,x_k$ 的线性组合形式,列向量的形式即为:
$$\left[ \begin {matrix} a_x \\ x^k \\ x^{k-1} \\ \vdots \\ x^1 \\ x^0 \\ \end {matrix} \right]$$
递推组合数只需 $O(k^2)$ 的时间,总的复杂度仅为 $O(k^3\ logn)$ 。

代码

StackEdit 真好使啊。。

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
#include <cstdio>
typedef long long ll;
const int MAXK = 12, MAXW = 14;
const ll MOD = 1e9 + 7;
int r, w;
ll n, co[MAXK][MAXK];
inline void make_comb() {
co[0][0] = 1; // ***
for (int i = 1; i <= r; ++i) {
co[i][0] = 1; // ***
for (int j = 1; j <= i; ++j) {
co[i][j] = co[i - 1][j - 1] + co[i - 1][j];
if (co[i][j] > MOD)
co[i][j] -= MOD;
}
}
}
struct Matrix {
ll a[MAXW][MAXW]; // (k + 2) * (k + 2)
};
Matrix operator * (const Matrix &a, const Matrix &b) {
Matrix c;
for (int i = 1; i <= w; ++i) {
for (int j = 1; j <= w; ++j) {
c.a[i][j] = 0;
for (int k = 1; k <= w; ++k) {
c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j]) % MOD; // ***
}
}
}
return c;
}
inline void qpow(Matrix &a, ll p, Matrix &res) {
res = a;
--p;
for (; p; p >>= 1, a = a * a)
if (p & 1)
res = res * a;
}
// f(n+1) = 2*f(n) + (n+1)^k - n^k
int main() {
Matrix a, res;
int i, j;
ll ans = 0;
scanf("%lld%d", &n, &r);
if (n == 1) {
puts("1\n");
return 0;
}
w = r + 2;
make_comb();
for (i = 1; i <= w; ++i)
for (j = 1; j <= w; ++j)
a.a[i][j] = 0;
a.a[1][1] = 2;
for (i = 0; i <= r; ++i)
a.a[1][r - i + 2] = co[r][i];
a.a[1][2] -= 1;
for (i = 0; i <= r; ++i)
for (j = 0; j <= i; ++j)
a.a[r - i + 2][r - j + 2] = co[i][j];
qpow(a, n - 1, res);
for (i = 1; i <= w; ++i) {
ans += res.a[1][i];
if (ans > MOD)
ans -= MOD;
}
printf("%lld\n", ans);
return 0;
}