Codeforces Round 695 D. Sum of Paths
警告
本文最后更新于 2021-01-13,文中内容可能已过时。
$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)$
|
|