题解：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 中的对应项之和，即：

2^{-20}\sum_{t\in T}\sum_{i=0}^{2^{20}-1}w_i(-1)^{|i\& t|}

将其变成：

2^{-20}\sum_{i=0}^{2^{20}-1}w_i\sum_{t\in T}(-1)^{|i\& 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 重度卡常。