题目链接
翻译
可以从数组中任意一个位置开始出发走一条路径，每一步可以往走到相邻的一个格子(左或右)。但是不能超过边界。
问你所有不同的长度为 \(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;
}