题解：P10360 [PA 2024] Desant 3

· · 题解

[PA 2024] Desant 3

好怪的数数，不过这种套路好像挺常见（？

和 P9393 的想法有点像，可以看一下。

首先可以发现这个题的数据范围及其古怪，不是超级 dp 就应该是一些胡乱的复杂度的做法。但这题完全没有可以 dp 的拓扑序，所以考虑状压，然后用一些奇怪手法把复杂度降下来。

枚举每个位置是 0 还是 1 显然没有什么前途，考虑按照顺序根据 m 个操作把状态填出来。对于每一位，我们设其有 0，1，-1 三种状态，其中 0 表示没有准备好，1 表示已经准备好，-1 表示还没有确定。最终统计答案时由于一个初状态对应的末状态是唯一的，所以直接枚举为 1 的答案区间的左右端点，如果为 1 的位置全部在这个区间中并且区间中没有 0 就直接计入答案。

考虑对这个状态进行转移，设当前操作为 \left(x,y\right)，x 和 y 的位置的权值分别为 a,b。

  1. 直接模拟操作向后转移即可，这样是从 $1$ 个状态转移到 $1$ 个状态，不影响答案。
  2. 考虑 $a=-1,b=0$ 的情况。那么可以发现如果确定后的状态中这两个数全为 $0$ 那么这一次交换还是不交换不影响答案数量与状态正确性，而一个为 $1$ 一个为 $0$ 时需要交换，所以直接视作交换即可，将其变为 $a'=0,b'=-1$。 $a=1,b=-1$ 同理。 这时状态数不会增加。
  3. a=-1,b=1$ 或 $a=0,b=-1

    此时无论为 -1 的数实际上指代的是什么都无需交换，这时状态不变，状态数不增加。

  4. a=-1,b=-1

    这时分类讨论其真实对应的值的四种情况即可，这时状态数会变为原来的 4 倍。

考虑这样转移的复杂度，前 3 种转移显然不影响复杂度，而第 4 种转移会让状态数乘 4，-1 的个数减少两个。所以总时间复杂度是 \operatorname{O}(2^n(m+n^2)) 无法通过。

考虑优化。仔细读题发现有一个非常重要的东西我们没有用上，即输出种类数对 2 取模的结果。考虑现在的复杂度瓶颈处，不难发现在转移 4 中真实数值为 a=0,b=1 和 a=1,b=0 两种情况在转移后的状态是相同的，可以一一对应，所以说这两种情况可以不考虑，这样就只会转移到两个状态。时间复杂度为 \operatorname{O}(2^{\frac{n}{2}}(m+n^2))。