自动搬运

查看原文

来自洛谷，原作者为

	Time_tears oi复健ing

搬运于2025-08-24 22:31:29，当前版本为作者最后更新于2021-06-13 17:02:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

出题人分为 $10$ 种阵营：守序善良、守序中立、守序邪恶、中立善良、绝对中立、中立邪恶、混乱善良、混乱中立和混乱邪恶，九条可怜。真正的出题人，就要能够在阵营之间不断切换，最终成为九条可怜。

容易发现这个题目的描述看起来就很背包，而且由于这个 $\bmod p$ 意义下的加法，似乎就只能背包做了，那么考虑背包怎么做。

首先我们把这个等边三角形的边改一下，变成沿 $x$ 轴，沿 $y$ 轴，沿 $y=x$ 的三条线，容易发现这样做后走法是一一对应的，所以没有区别。

设 $f_{i,j,k,l,g}$ 表示 Dp 前 $i$ 个数，当前横坐标在 $j$，当前纵坐标在 $k$，当前 $L$ 是 $l$，当前 $G$ 是 $g$ 是否可行。

这样 Dp 复杂度是 $O(n^3p^2)$ 的，即使用了 bitset 复杂度也为 $O(\dfrac{n^3p^2}{\omega})$，卡不过去。

考虑如何优化，但是这样的背包已经是最优了，也就是说背包是不可能再优化了，只能考虑从其它地方优化。

考虑非常经典的随机游走问题，它告诉我们在二维平面上每次随机选一个方向走 $1$ 的单位长度，走 $n$ 步期望的距离不会超过 $\sqrt n$ 级别，而这道题我们选择的方案也可以当成是随机在 $6$ 种当中选 $1$ 种出来。

所以我们只需将输入的 $a,b$ 随机化，并将 $j,k$ 这两维只开到 $\sqrt n$，这样复杂度就降为 $O(\dfrac{n^2p^2}{\omega})$ 了。(事实上要开到 $2\sqrt n$，$\sqrt n$ 会被卡掉)。