$n$ 个连续的格子, 从左到右分别标号为 $1 \sim n$. 初始第 $i$ 个格子上的数为 $a_i$. 把从任意一点开始, 正好走 $k$ 步的一条路径成为合法路径. 每一步只能走相邻的格子, 且不能出界. 一条路径的价值是, 每一次走到一个格子, 价值就加上格子上的这个数.
给出$q$个修改, 每次只修改一个格子的数$a_i$, 输出每次修改后的所有路径价值之和模$10^9 + 7$.
$1 \le n, k, le 5000, 1 \le q \le 2 \cdot 10^5, 1 \le a_i \le 10^9$
显然要转化贡献. 这道题也难在转化贡献.
首先有一点很容易想: 我们要求第$i$个位置对所有路径的贡献$cnt_i$, 答案就是$\sum ai \cdot cnt_i$.
接下来, 如果用一条路径上出现的$i$个数求$cnt_i$, 就得用三维dp, 复杂度爆炸. 所以不能这么做.
再转化一次贡献, 求经过了第$i$个位置的合法路径有多少条. 由于一条路径可能不止一个, 所以我们再拆分一下. 设 $A_{i, j}$ 为 第 $j$ 步在 $i$ 的路径条数. 然后求和 $cnt_i = \sum_{j = 0}^k A_{i, j}$.
现在我们已经将贡献从出现次数转化到了路径条数. 那么, 尝试dp求一下路径条数: $dp_{i, j}$ 表示走了 $j$ 步, 最后一步在 $i$ 的路径条数. 由于对称性, 它还表示从 $i$ 开始走 $j$ 步的路径条数.
要求第 $j$ 步在 $i$ 的路径条数, 我们就得把这条路分成两部分:
- 第 $0$ 步到第 $j$ 步, 路径数有 $dp_{i, j}$
- 第 $j$ 步到第 $k$ 步, 路径数有 $dp_{i, k-j}$
然后相乘就是$A_{i, j}$了.
复杂度$O(n^2 + q)$
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
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5005, mod = 1e9 + 7;
int dp[N][N], cnt[N], a[N], q, n, k;
void pre() {
for (int i = 0; i < n; i++)
dp[i][0] = 1;
for (int j = 1; j < N; j++) {
dp[0][j] = dp[1][j - 1];
for (int i = 1; i < n - 1; i++)
dp[i][j] = (dp[i - 1][j - 1] + dp[i + 1][j - 1]) % mod;
dp[n - 1][j] = dp[n - 2][j - 1];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++)
cnt[i] += dp[i][j] * dp[i][k - j], cnt[i] %= mod;
}
}
void solveTestCase() {
int ans = 0;
for (int i = 0; i < n; i++)
cin >> a[i], ans += a[i] * cnt[i], ans %= mod;
while (q--) {
int i, x;
cin >> i >> x;
i--;
ans -= (a[i] * cnt[i]) % mod, ans += mod, ans %= mod;
a[i] = x;
ans += (a[i] * cnt[i]), ans %= mod;
cout << ans << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> k >> q;
pre();
int t = 1;
//cin >> t;
while (t--)
solveTestCase();
}
|