自动搬运

查看原文

来自洛谷，原作者为

	Petit_Souris 鼓励的话语 无论多少次我都会说给你听 | 你在名为弱小的深渊 究竟看见过什么 | 天空中出现了一种罕见的天文现象

搬运于2025-08-24 23:12:10，当前版本为作者最后更新于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}))$。