CF449D Jzzhu and Numbers
简要题意
给定序列 \(\{a_n\}\)，求有多少个子序列满足所有元素的按位与为 \(0\)。
题解
F1
考虑 FWT 的与卷积形式，构造序列 \(\{A_n\}\)，使 \(A_i=\displaystyle\sum_{j\&i=i}a_i\)，记 \(B_i=\displaystyle\sum_{b\in a}[(b_1\&b_2\&\cdots\&b_n)\&i=i]\)，则有 \(B_i=2^{A_i}-1\)，最后对 \(B_i\) 做一次 IFWT 或者容斥即可。
F2
考虑一个背包 \(f_{i,j}\) 表示考虑 \(a_1\) 到 \(a_i\)，按位与结果为 \(j\) 的子序列数量。
有转移：
两端做 FWT：
其中 \(F_{i,\cdot}\) 是 \(f_{i,\cdot}\) 的 FWT，\(G_{i,\cdot}\) 是 \(g_{i,\cdot}\) 的 FWT，\(g_{i,j}=\begin{cases}1 & j=a_i\\0 & j\ne a_i\end{cases}\)。
简单计算可以得到同 F1 的结果，有 \(F_{n,\cdot}=A\)。
record
CF1119H Triple
简要题意
给定几个数：\(n,t,u,v,w\) 满足 值域 \(≤2^t\)。给出 \(n\) 个三元组 \((ai,bi,ci)\)，表示有 \(x\) 个 \(a_i\)，\(y\) 个 \(b_i\)，\(z\) 个 \(c_i\)。对于每个 \(k\in[0,2t−1]\)，请求出从每组选出一个数的异或和为 \(k\) 的方案数。
题解
我们要求
其中 \(\prod\) 为异或卷积。考虑进行 FWT，有
第二行之后及下文的 \(\prod\) 为点积。
注意到 \(\mathcal{F}(x^k)=\sum_S(\pm1)x^S\)，因此
总共只有八种情况，对于每一个 \(k\)，算出这八种情况在乘积中各出现多少次，然后快速幂就做完了。
考虑到八种情况还是太臃肿了，我们进行一个小 trick：将 \(b_i,c_i\) 异或上 \(a_i\)，然后令 \(a_i=0\)，最终输出答案的时候再异或回来即可，故 \(\mathcal{F}(x^{a_i})=\mathcal{F}(x^\varnothing)=\sum x^S\)，所以 \(u\) 的系数恒为 \(1\)，只剩下四种情况
记他们出现的次数分别为
接下来考虑如何计算。直接算显然是不切实际的，但是我们考虑只计算 \(v\) 的系数的和 \(p_v\)，则有对于最终答案的 \(x^k\) 这一项，
对于 \(w\) 和 \(p_w\) 同理，再加上 \(c_1+c_2+c_3+c_4=n\)，我们得到了三个线性无关的方程，考虑再找一个方程：
注意到 \(\mathcal{F}(x^{b_i})\mathcal{F}(x^{c_i})=\mathcal{F}(x^{b_i\oplus c_i})\) 为 \(v,w\) 系数的乘积记为 \(p_{v\oplus w}\)，有
至此四个方程集齐：
解出来之后做个快速幂，然后 IFWT 就做完了。