CodeForces #695 D. Sum of Paths

题目链接

题意

给出一个长度为 \(n\) 的整数数组，现在可以将一个机器人放到任意一个位置。

这个机器人必须走 \(k\) 步，每次可以选择向左或者向右走，但不会越界。走 \(k\) 步之后，经过的数组元素和，就是这条 \(good\ path\) 的权值。

现在给定 \(q\) 个操作，每次给出两个数字 \(i，x\)，将 下标 \(i\) 处的元素替换为 \(x\)。
对于每个操作，输出所有可能的路径的权值和。

题解

概要：
求出每个元素对于路径权值和的贡献次数，以及初始权值和；对于每次修改，加上权值差 * 贡献次数。

用 \(dp[i][j]\) 表示第 \(i\) 步走到 \(j\) 位置的路径数量。

\(num[i]\) 表示下标为 \(i\) 对于权值和的贡献次数。

可以知道以 \(i\) 为开头的路径数量和以 \(i\) 为结尾的路径数量是相同的。

对于 \(i\)，考虑其在长度为 \(k\) 的路径中的次序。

for (int j = 0; j <= k;j++){
    num[i] += dp[j][i] * dp[k - j][i];
}

将所有的可能加起来，就得到了下标 \(i\) 的贡献次数。

代码

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const ll inf = 0x3f3f3f3f;
const ll N = 5e3 + 10;

ll dp[N][N], arr[N];
ll num[N];
int main()
{
    ll n, k, q;
    scanf("%lld%lld%lld", &n, &k, &q);
    for (ll i = 1; i <= n; i++) {
        scanf("%lld", &arr[i]);
    }
    for (ll i = 1; i <= n; i++) {
        dp[0][i] = 1;
    }
    for (ll i = 1; i <= k; i++) {
        for (ll j = 1; j <= n; j++) {
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
        }
    }
    for (ll i = 1; i <= n; i++) {
        for (ll j = 0; j <= k; j++) {
            num[i] = (num[i] + dp[j][i] * dp[k - j][i] % mod) % mod;
        }
    }
    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        ans = (ans + num[i] * arr[i] % mod) % mod;
    }
    while (q--) {
        ll pos, val;
        scanf("%lld%lld", &pos, &val);
        ans = (ans + ((val - arr[pos]) % mod + mod) % mod * num[pos] % mod) % mod;
        printf("%lld\n", ans);
        arr[pos] = val;
    }
    return 0;
}