[THUPC2021] 混乱邪恶

Time_tears · 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 会被卡掉)。