Codeforces Round 695 D. Sum of Paths

Wings 收录于类别 ACM

2021-01-13 2021-01-13 约 339 字预计阅读 2 分钟次阅读条评论

$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)$

cpp

#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();
}