FWT 学习笔记&做题记录
前置知识
多项式卷积
先来个模板：
P4717
FWT 用来解决像下面这样的卷积：
\[F(x)=\sum_{i\oplus j=x}A(i)B(j) \]其中 \(\oplus\) 是三个位运算中的一个。
FWT 的时间复杂度为 \(O(n2^n)\)，如果把 \(2^n\) 看成 \(n\)，那么时间复杂度和 FFT，NTT 相同。
与卷积
\[F(x)=\sum_{i\ and\ j=x}A(i)B(j) \]定义 \(A'(x)\) 表示 \(\sum_{x\in y}A(y)\)，这是一个 FWT 变换，显然这个变换可以直接高维前缀和。
void FMT(int *A,int *ans){
for(int i=0;i=0;j--)
if(j&(1< 然后会发现一个惊人的式子：
\[F'(x)=A'(x)B'(x) \]证明很简单，考虑后面的式子实际上就是
\[\sum_{x\in y_1}\sum_{x\in y_2}A(y_1)B(y_2) \]然后会发现 \(x\in (y_1\cap y_2)\)，所以这样计算出来的显然和右边相等。
然后考虑咋从 \(F'(x)\) 变成 \(F(x)\)。
实际上就是再减回去，把加号变成减号即可。
void IFMT(int *A,int *ans){
for(int i=0;i=0;j--)
if(j&(1< 然后你就会发现，两个的区别只有一个符号，可以直接带一个 \(T\) 进去。
卷积写法和 FFT 差不多，就是：
FWT(A,A,1),FWT(B,B,1);
for(int i=0;i和卷积就好了。
或卷积
和上面的差不多，可以发现本质上就是枚举顺序换一下就好了。
关于写法
FWT 写法可以和 FFT 长得一样，这样看上去更加优美。
//和卷积
void FMT_And(int *A,int T){
for(int len=1;len<1<可以发现本质上 \(len\) 在枚举哪一位，\(l\) 在枚举这一位前面的，\(k\) 是后面的，然后就和上面的写法一样了。
这样写的好处在于，无论什么运算，只需要在两个数的情况下满足，就可以直接写在里面。
异或卷积
最后讲是因为实在太难了。
神仙构造：\(F'(x)=\sum_{i*x=0}F(i)-\sum_{i*x=1}F(i)\)。
令 \(p(x)\) 表示 \(x\) 二进制位上 \(1\) 的个数，则上面 \(*\) 表示 \(p(i\& x)\mod 2\)。
可以发现 \((i*x)\ xor \ (i*y)=i*(x\ xor \ y)\)。
证明很简单，按位考虑，如果 \(i\) 这位是 \(0\)，那么左右都是 \(0\)，如果 \(i\) 是 \(1\)，那么 \(x,y\) 如果有 \(1\) 就会产生 \(1\) 的贡献，又因为有对 \(2\) 取模，所以左右相等。
\[A'(x)B'(x)=(\sum_{i*x=0}A(i)-\sum_{i*x=1}A(i))(\sum_{j*x=0}B(j)-\sum_{j*x=1}B(j))\\ =(\sum_{i*x=0}A(i)\sum_{j*x=0}B(j))+(\sum_{i*x=1}A(i)\sum_{j*x=1}B(j))-(\sum_{i*x=1}A(i)\sum_{j*x=0}B(j))-(\sum_{i*x=0}A(i)\sum_{j*x=1}B(j))\\ =(\sum_{(i*x)\ xor \ (j*x)=0}A(i)B(j))-(\sum_{(i*x)\ xor \ (j*x)=1}A(i)B(j))\\ =(\sum_{x*(i\ xor \ j)=0}A(i)B(j))-(\sum_{x*(i\ xor \ j)=1}A(i)B(j))\\ =\sum_{x*y=0}F(y)-\sum_{x*y=1}F(y)=F'(x) \]考虑咋实现，对于两个数差一个二进制位的数来说，实际上就是前面的加上后面的，后面的减去前面的。
逆变换也很简单，直接还原即可。
void FMT_Xor(int *A,int T){
for(int len=1;len<1<最后我们得到了 P4717 的 代码
做题记录
P6097
给长度为 \(2^n\) 的两个序列 \(A,B\)，求其子集卷积结果。
\[c_k=\sum_{\substack{{i \& j=0}\\{i~\mid~ j=k}}} a_i b_j \]
\(n\le 20\)。
一个模板题。
考虑 \(i \& j=0\) 的限制比较阴间，没有这个限制的话可以直接或卷积。
令 \(p(x)\) 表示 \(x\) 二进制位上 \(1\) 的个数，那么可以发现，\(p(i)+p(j)\ge p(i|j)\)，仅当 \(p(i)+p(j)=p(i|j)\) 时 \(i\& j=0\)。
那么有一个想法就是加一维限制，限制其位数，对于每一个或卷积之后在进行一个多项式卷积。
\[C'(n,x)=\sum_{i=0}^n A'(i,x)B'(n-i,x) \]然后对每一位进行还原即可，时间复杂度 \(O(n^22^n)\) 可过。
code
CF662C *2600
tourist 场上没做出的题被我做出了。
有一个 \(n\) 行 \(m\) 列的表格，每个元素都是 \(0/1\) ，每次操作可以选择一行或一列，把 \(0/1\) 翻转，即把 \(0\) 换为 \(1\) ，把 \(1\) 换为 \(0\) 。请问经过若干次操作后，表格中最少有多少个 \(1\) 。
\(n\le 20,m\le 10^5\)。
\(n\) 这么小，显然先把每一列状压一下，假设状压结果是 \(b_i\)。
枚举当前行上的操作 \(x\)，令 \(g(x)\) 表示 \(\min(p(x),n-p(x))\)，即通过翻转得到的最小 \(1\) 数量。
\[F(x)=\sum g(b_i\ xor \ x) \]令 \(k_i=b_i\ xor \ x\)，\(c_i\) 表示 \(b_i\) 的出现次数。
\[F(x)=\sum_{b_i\ xor \ x=k_i} g(k_i)=\sum_{b_i\ xor \ k_i=x} g(k_i)=\sum_{i\ xor \ j=x}g(i)c(j) \]显然异或卷积，直接卷就好了。
code
P4221
题比较长，自己看吧
首先，判断一个点集是否合法可以直接暴力，只需要满足不连通或者存在奇点即可，这部分可以直接 \(O(n2^n)\)。
直接考虑当前选了多少个点，令 \(f_{i,j}\) 表示已经选了 \(i\) 个点，集合为 \(j\) 的乘积，这明显是一个子集卷积，枚举上一轮选了多少个点，直接和上面预处理的结果卷起来就好了。
每一轮之后再去除以整个集合的和，也就是式子的下半部分。
这样一直做 \(n\) 轮就做完了，时间复杂度 \(O(n^22^n)\)。
code