已完成今日 FWT 大学习
vegetable_king
·
·
题解
可能更好的阅读体验。类似的一些东西：here。
场上被 T6 做局了，赛后单杀了来写篇题解。
由于只关心异或和，可以将非严格递增序列看作可重集。那么我们只关心 S 中每种元素出现次数的奇偶性。求出不可重集的方案数后每种数加入偶数个即可。我们求出 h_i 表示大小为 i 且异或和在 T 中的 S 的子集个数，答案就是这样：
\sum_{i = 0}^{|S|} h_i \binom{(n - i) / 2 + |S|}{|S|}
我们规定 x^ax^b = x^{a \oplus b}, y^ay^b = y^{a+b}，那么可以写出 h 的生成函数：
\sum_{a \in T} [x^a] \prod_{b \in S} (1 + x^by)
先考虑后面部分，套路地 FWT 一下变成点乘：
\begin{aligned}
f_k &= [x^k] \operatorname{FWT}\left(\prod_{b \in S} (1 + x^by)\right)\\
&= \prod_{b \in S} [x^k] \operatorname{FWT}(1 + x^by)\\
&= \prod_{b \in S} (1 + y(-1)^{|k \cap b|})\\
\end{aligned}
最后还要 IFWT 回去求出各项系数：
\begin{aligned}
g_k &= \frac 1{2^v} [x^k] \operatorname{FWT}\left(\sum_{j = 0}^{2^v - 1} f_jx^j\right)\\
&= \frac 1{2^v} \sum_{j = 0}^{2^v - 1} [x^k] \operatorname{FWT}(f_jx^j)\\
&= \frac 1{2^v} \sum_{j = 0}^{2^v - 1} (-1)^{|k \cap j|}f_j\\
&= \frac 1{2^v} \sum_{j = 0}^{2^v - 1} (-1)^{|k \cap j|} \prod_{b \in S} (1 + y(-1)^{|j \cap b|})\\
\end{aligned}\\
那么我们要求的东西变成了这样：
\frac 1{2^v} \sum_{a \in T} \sum_{j = 0}^{2^v - 1} (-1)^{|a \cap j|} \prod_{b \in S} (1 + y(-1)^{|j \cap b|})\\
调换一下求和顺序：
\frac 1{2^v} \sum_{j = 0}^{2^v - 1} \sum_{a \in T} (-1)^{|a \cap j|} \prod_{b \in S} (1 + y(-1)^{|j \cap b|})\\
注意到后面的乘积里面只有 (1 - y) 和 (1 + y)：
ca_j = \sum_{a \in T} [|a \cap j| \bmod 2 = 1]\\
cb_j = \sum_{b \in S} [|b \cap j| \bmod 2 = 1]\\
\frac 1{2^v} \sum_{j = 0}^{2^v - 1} (|T| - 2ca_j) (1 + y)^{|S| - cb_j} (1 - y)^{cb_j}\\
再次合并同类项：
\sum_{i = 0}^{|S|} co_i (1 + y)^i (1 - y)^{|S| - i}\\
那么直接 \mathcal O(|S|^2) 求即可。还有一个问题是 ca_j 怎么快速算：考虑把所有的 |a \cap j| \bmod 2 压到 bitset 里，然后每次 j \gets j + 1 的时候相当于是反转了 j 的二进制表示的一段后缀，我们预处理出每种长度的后缀对 bitset 造成的影响，每次异或一下再调用 count() 即可做到 \mathcal O\left(\frac{2^v|T|}\omega\right) 求出所有 ca_j，cb_j 同理。
那么总时间复杂度就是 \mathcal O\left(|S|^2 + \frac{2^v(|S| + |T|)}\omega + q|S|\right)，其中 v = 28，可以通过。
代码中偷懒直接写了 O(n) 预处理组合数，要规避掉也是简单的，一开始那个形式显然是一个只和 n 有关的 |S| + 1 次多项式，\mathcal O(|S|^2) 插值求出各项系数后也可以单次 \mathcal O(|S|) 查询答案。好像比 std 还优一点。