题解：P13497 【MX-X14-T7】墓碑密码

一个简单一点的做法？

由于从 $S$ 中选出的数是可重的，我们不妨先假设不可重，然后设选出了 $k$ 个，方案数乘上 $C(\lfloor\frac{n-k}{2}\rfloor+|S|,|S|)$。现在转化为求 $f_k$ 表示从 $S$ 中选出 $k$ 个数的选法数，满足这 $k$ 个数的异或和属于集合 $T$。

先考虑值域 $2^{20}$ 的部分分。将其写成一些短多项式乘积的形式 $[y^k]\prod(1+x^{a_i}y^0)$，这里我们增加了 $y$ 这一元记录选出了多少个。这个是经典 FWT，简要来说，考虑 $1+x^{a_i}$ 的 FWT 数组只存在 $0$ 和 $2$，求出 $0$ 和 $2$ 的个数 $c_0$ 和 $c_2$ 就可以计算选出 $k$ 个的方案数，即 $\sum_{i=0}^k (-1)^i2^{k-i}C(c_0,i)C(c_2,k-i)$。求出 FWT 再 IFWT，答案为 $\sum_{t\in T}[x^t]$ 项。对每个 $k$ 都要做一次 IFWT，时间复杂度 $O(20|S|\times 2^{20})$，赛时实现了这个在梦熊上获得了 60 分。

进一步优化，由于我们只需求 IFWT 数组 $w_{*}$ 在 $T$ 中的对应项之和，即：

将其变成：

对 $T$ 做 FWT，再对应点乘。现在时间复杂度变为 $O(|S|2^{20})$。

注意到瓶颈仅仅在于求出 $S$ 和 $T$ 的 FWT 数组，计算答案的部分可以在 $O(|S|^3)$ 的时间复杂度内完成。

考虑优化 FWT，一个重要的事实是 $S$ 和 $T$ 的大小都只有 $128$。对每个 $0\le i<2^{28}$ 记录一个 128 位的二进制数表示每个 $S$ 中数 $s$ 的 $(-1)^{|i\&s|}$，通过 $i-lowbit(i)$ 转移到 $i$，空间复杂度仍然不可接受。一个优化的办法是按位 dfs，任意时刻 dfs 栈中最多只有 $28$ 个数。这一部分的时间复杂度 $O(\frac{2^{28}\times 128}{w})$，空间复杂度 $O(1)$。

总时间复杂度 $O(\frac{n2^{m}}{w}+n^3+qn+l)$，其中 $n=|S|+|T|$，$m=28$，$w$ 是位长，$l$ 是询问的 $n$ 的大小。在此批评出题人时限只开 2s 重度卡常。