自动搬运

查看原文

来自洛谷，原作者为

	Undead2008 。

搬运于2025-08-24 23:16:48，当前版本为作者最后更新于2025-05-25 22:46:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

假设路径经过的每一条边依次为从上一个点 $x$ 走到 $3x+b_i+1$，将经过的 $a_i$（去掉 $a_0$）和 $b_i$ 依次写成序列，容易发现：

现在要 $\sum b_i=k$，就是

记 $a$ 的前缀和为 $s$，即有

但是 $a$ 和 $s$ 都未知，需要计数方案，考虑 dp。

记 $f_{i,j,k}$ 表示当前 dp 到 $i$，$s_{d-i}=j$，$i-1$ 向当前位进位 $k$ 的方案数，注意到 $s_{d-i+1}-s_{d-i}\in\{0,1,2\}$ 所以一个状态的后继状态个数为 $O(1)$。

状态 $O(n^3)$，转移 $O(1)$，时间复杂度 $O(n^3)$。

注意到对于一组 $(i,j)$，满足 $f_{i,j,k}$ 非零的 $k$ 的数量是 $O(1)$ 个，所以状态数其实是 $O(n^2)$ 的，拿 umap 或者 vector 存一下就行了，时间 $O(n^2)$。