黎明前的巧克力
给定集合 \(S\)，求：
\[\sum_{A,B\subseteq S\\A\cap B=\emptyset}|\text{xor}_{x\in A\cup B}\ x=0| \]\(n,a_i \le 10^6\)
相当于求：
\[[x^0] \prod_{i}(1+2x^{a_i}) \]对每个 \(i\) 分别做 fwt，考察每个式子的贡献。
fwt 做过以后得到 \(g_S = \sum_T (-1)^{|S \cap T|} f_T\)，带入上面的式子就知道：
\[g_x=\prod_{i}(1+2\times (-1)^{|x\ \text{and}\ a_i|}) \]只需对每个 \(x\) 算出，贡献 \(-1/3\) 分别的次数。
总之我们得到 \(\sum (-1)^{x\ \text{and}\ a_i}\) 就行了，直接对 \(\sum x^{a_i}\) 做个 fwt 就能得到具体的系数。
由于我们只需得到 \(Ans_0\)，所以可以不做逆 fwt。
给定 \(n\) 个 \(m\) 元组 \((a_{i,1},\cdots,a_{i,m})\)。
对每个 \(x \in [0,2^k)\) 计算，有多少个 \(i\) 满足 \(\forall j, [(-1)^{|a_{i,j}\ \text{ and } x|}=-1]\)
我们想用一次 fwt 计算答案。
记 \(f(S)\) 表示集合 \(S\) 的异或和。
给出结论：如果 \(x\) 对 \(m\) 元组 \(A_{m}\) 存在贡献，那么：
\[\sum_{S \subseteq A} (-1)^{|S| + |f(S)\text{ and }x|}=2^{m} \]反之，上式为 0。
于是合在一起做个 fwt 就行了。
标签：text,sum,元组,问题,fwt,经典,FWT,prod From： https://www.cnblogs.com/havzriu/p/17113457.html