题目链接
翻译
可以从数组中任意一个位置开始出发走一条路径，每一步可以往走到相邻的一个格子(左或右)。但是不能超过边界。
问你所有不同的长度为 (k+1) 的路径的和是多少。
然后要支持更新操作实时回答这个路径和。
题解
(n) 和 (k) 都只有 (5000)，其实是比较容易往 (DP) 上面想的。
实时更新的话，只要能够知道最后每个数字在答案中的贡献 (cnt_i)(出现了几次)，要做到实时更新也不难。
直接在原来答案的基础上加上 ((x-a[i])*cnt_i) 即可。
怎么求这个 (cnt_i) 呢?
(DP)
设 (dp[i][j]) 表示以第 (i) 个数字结尾的长度为 (j) 的序列有多少个。
显然有转移方程 (dp[i][j] = dp[i-1][j-1] + dp[i+1][j-1]), 且 (dp[i][0] = 1)。
同时，会发现这个 (dp[i][j]) 除了可以理解为上面的意思，还能表示以第 (i) 个数字开始的长度为 (j) 的序列有多少个。
因为向左和向右是相反对称的嘛(理解这个角度的定义很重要)。
这有什么用呢?我们可以用它来求出数组 (cnt[N][K])，其中 (cnt[i][j]) 表示的是长度为 (k) 的序列, 在第 (j) 步走到了
(i) 位置的序列个数。则累加 (cnt[i][0..k]) 就是 (a[i]) 在所有长度为 (k) 的路径中的贡献了。
也即，第 (0,1,2,3...k) 步走到了 (a[i]) 的长度为 (k) 的路径数目。
因为 (dp[i][j]) 既能表示开始，也能表示结束路径个数。那么 (dp[i][j]+dp[i][k-j]) 不就是我们要求的 (cnt[i][j]) 了吗。
也即 (cnt[i][j] = dp[i][j] + dp[i][k-j]) (以 (i) 为结尾的长度为 (j) 的序列，加上一个以 (i) 开始的长度为 (k-j) 的序列。
拼起来就是长度为 (k) 的了。
算 (cnt[i][j]) 的时候做个前缀和就好。
这样就知道每个数字对最后答案的贡献了，按照我一开始说的方法实时更新答案即可。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 5000;
const LL MOD = 1e9 + 7;
const int K = 5000;
int n, k, q;
LL a[N + 10];
LL dp[N + 10][K + 10];
LL times[N + 10][K + 10];
int main() {
#ifdef LOCAL_DEFINE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> k >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
dp[i][0] = 1;
}
for (int j = 1; j <= k; j++) {
for (int i = 1; i <= n; i++) {
dp[i][j] = dp[i - 1][j - 1] + dp[i + 1][j - 1];
dp[i][j] %= MOD;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
times[i][j] = dp[i][j] * dp[i][k - j]%MOD;
if (j > 0) {
times[i][j] = (times[i][j] + times[i][j - 1]) % MOD;
}
}
}
LL ans = 0;
for (int i = 1; i <= n; i++) {
ans = (ans + times[i][k] * a[i] % MOD) % MOD;
}
while (q--) {
int i, x;
cin >> i >> x;
ans = ans + ((x - a[i]) % MOD+MOD)%MOD * times[i][k] % MOD;
ans %= MOD;
cout << ans << endl;
a[i] = x;
}
return 0;
}