2019.5.21

Emmm很不想写代码的感觉。

CF392C Yet Another Number Sequence

题目描述

Everyone knows what the Fibonacci sequence is. This sequence can be defined by the recurrence relation:

$ F_{1}=1,F_{2}=2,F_{i}=F_{i-1}+F_{i-2}$ We’ll define a new number sequence $A_{i}(k)$ by the formula:

$ A_{i}(k)=F_{i}×i^{k} (i>=1). $ In this problem, your task is to calculate the following sum: $A_{1}(k)+A_{2}(k)+…+A_{n}(k)$ . The answer can be very large, so print it modulo 1000000007 $(10^{9}+7)$

Solution

定义$f(n,k) = \sum\limits_{i=1}^{n}A_i(k)$

大致猜一个推导方向是常系数线性递推。

二项式定理展开

交换求和顺序

这一步需要注意一下边界情况,$F_0=1,0^0=1$(这里按照IEEE标准)

矩阵快速幂优化即可,注意一下初始状态
时间复杂度$O(k^3\log n)$

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
#include <iostream>
const int mod = 1000000007;
using LL = long long;
int k, C[50][50], pow[50], num[2][50], K, tot;
void up(int &x, int y) { if ((x += y) >= mod) x -= mod; }
struct matrix {
int num[83][83];
matrix operator * (matrix rhs) const {
matrix res;
for (int i = 0; i <= K; i++)
for (int j = 0; j <= K; j++) {
int ans = 0;
for (int k = 0; k <= K; k++) up(ans, static_cast<LL> (num[i][k]) * rhs.num[k][j] % mod);
res.num[i][j] = ans;
}
return res;
}
} base, init;
LL n;
int main() {
std::cin >> n >> k; K = 2 * k + 2;
for (int i = 0; i <= k + 1; i++) pow[i] = (1LL << i) % mod;
for (int i = 0; i <= k; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) {
up(C[i][j] = C[i - 1][j - 1], C[i - 1][j]);
}
}
for (int i = 0; i < 2; i++) for (int j = 0; j <= k; j++) num[i][j] = tot++;
for (int j = 0; j <= k; j++) {
for (int p = 0; p <= j; p++)
base.num[num[0][p]][num[0][j]] = C[j][p];
for (int p = 0; p <= j; p++)
base.num[num[1][p]][num[0][j]] = static_cast<LL> (C[j][p]) * pow[j - p] % mod;
base.num[K][num[0][j]] = pow[j] + 1;
base.num[num[0][j]][num[1][j]] = 1;
}
base.num[K][K] = 1;
for (int j = 0; j <= k; j++) {
init.num[0][num[0][j]] = (1 + pow[j + 1]) % mod;
init.num[0][num[1][j]] = 1;
}
init.num[0][K] = 1;
if (n == 1) std::printf("%d\n", init.num[0][num[1][k]]);
else {
for (----n; n; n >>= 1, base = base * base) if (n & 1) init = init * base;
std::printf("%d\n", init.num[0][num[0][k]]);
}
return 0;
}

其实还可以用更优的方法。

定义$F,G$分别是斐波那契数列的初始矩阵和转移矩阵。比较特殊$(FG^{i-1})_{1,1} = G^{i-1}_{1,1}$

$F(2n,k) = \sum\limits_{i=1}^{n} + G^{n}_{1,1}\sum\limits_{i=1}^{n}G^{i}_{1,1}(i+n)^k$

恒等变换后等于

时间复杂度是$O(8klogn)$,实现的时候因为$n$不是2的次幂,所以先处理到$2^k$大于$n$即可。

每个转移的复杂度是常数。

很中档的一道题。。