题解：P12020 CF1033F 加强版

Petit_Souris · 2025-04-05 12:01:27 · 题解

模拟赛场上获得了尊贵的 92 分，因为我忘记 FFT 可以用 FWT 代替了。

事实证明，把数据范围开到 w=16 之后，大家都可以爆标！

首先先把原题过一下！我们考虑每一位的限制是什么意思，实际上对于 \texttt{O,x,a}，相当于限定对应位上的 x,y 之和为 0/1/2；对于 \texttt{A,X,o}，相当于限定对应位上的 x,y 之和为 0/1，0/2，1/2。这可以轻松导出一个 \mathcal O(4^w+q2^w) 的做法：首先平方枚举，预处理出三进制下所有 x+y 对应的方案数。查询的时候直接对于 \texttt{A,X,o} 枚举选了哪一个，这样就确定了 x+y 的值了。

接着考虑优化发现 \texttt{A,X,o} 个数比较少的时候这个做法已经可以 work 了，我们考虑一下 \texttt{O,x,a} 比较少的情况。

刚刚做的事情实际上是把大小为 2 的限制拆成了大小为 1 的限制，那么我们不妨试试把大小为 1 的限制拆成大小为 2 的限制。设 f_{S} 表示限制集合为 S 的方案数，那么我们可以这样拆：f_{0}=\frac{f_{0,1}+f_{0,2}-f_{1,2}}{2}，这样我们可以对于每个大小为 1 的限制枚举取了这三个中的哪一个（带容斥系数），最后除掉一个 2^k 就行了。

现在剩下的事情就变成了，给定一个三进制数 X，要求 x+y 的每一位都和 X 不同，求方案数。这个问题可以扩展一下三维 FWT 的过程，即对于每位做 a'_0=a_1+a_2,a'_1=a_0+a_2,a'_2=a_0+a_1。于是我们得到了一个 \mathcal O(4^w+3^ww+q\min(2^k,3^{w-k})) 的做法，其中 k 表示问询中 \texttt{A,X,o} 的个数。当 k\le 10 时用 2^k 的做法，k>10 时用 3^{w-k} 的做法。

能不能再给力一点？其实仔细一想发现这个 4^w 也可以优化掉的。最搞笑的方法是用 FFT（因为这是个加法卷积），但是常数太大了。我们发现由于 x,y 转成三进制之后每位都是 0 或 1，所以实际上做三进制不进位加法的 FWT 就是对的了，因为根本不会进位。最终复杂度为 \mathcal O(3^ww+q\min(2^k,3^{w-k}))。