P7670 [JOI 2018 Final] 毒蛇越狱 / Snake Escaping 题解

黑色的双倍经验！AT_joi2018ho_e

前置定义：$k_0$ 表示 $0$ 的数量，$k_1$ 表示 $1$ 的数量，$k_?$ 表示 $?$ 的数量。

前置知识：数据点分治，快速沃尔什变换（FWT）。

首先考虑一个非常 trival 的暴力，对于每一个 ? 字符，将其暴力替换为 0 和 1 然后判断答案。因此获得了一个 $O(Q2^{k_?})$ 的暴力。

然后考虑其的一个子问题：若字符串中只含有 0 字符和 ? 字符，那怎么做？考虑将该状态用二进制数表示，0 字符所对应的位置固定，? 字符可以对应 $0/1$。因此问题转化为给定固定集合求其子集的和，这个东西可以使用 FWT 来解决。1 和 ? 也同理。

如果字符串中同时含有 0，1，? 呢？考虑容斥，将所有的 1 转化为 ?，然后问题转化为 0 和 ? 的部分，可以用 FWT 解决。但是这样显然算多了，1 的部分已经固定，不能用 $0$ 来代替。因此暴力容斥掉 $0$ 的部分即可，获得了一个 $O(Q2^{k_1})$ 的暴力。

同样的，考虑将 0 转化为 ?，然后 FWT 套容斥，此时获得了一个 $O(Q2^{k_0})$ 的暴力。

但是问题是这三个暴力都可以被卡掉！因此考虑将她们数据点分，每一次找到其中期望跑的最快的一个跑，即比较 $k_0,k_1,k_?$ 中最小的元素然后跑暴力。这样就可以在 $O(n2^n+Q2^{\min(k_0,k_1,k_?)})$ 的时间复杂度内十分暴力的过题啦。代码很好写就不放了。