FWT/快速沃尔什变换
前言
FWT是处理一类问题形如（\(\oplus\)指or,and,xor二元运算符）
\[c_{i}=\sum_{i=j \oplus k} a_{j} b_{k} \]考虑像FFT一样，用\(O(n\log n)\)的复杂度构造出\(fwt\)，在\(O(n)\)计算出\(fwt_a\times fwt_b\)，最后在\(O(n\log n)\)将\(fwt\)转化回去
正题
OR
考虑构造
\[fwt_i=\sum_{j|i=i}a_j \]那么
\[\begin{aligned} fwt[a] \times fwt[b] &= \left(\sum_{j|i=i} a_j\right)\left(\sum_{k|i=i} b_k\right) \\\\ &= \sum_{j|i=i} \sum_{k|i=i} a_jb_k \\\\ &= \sum_{(j|k)|i = i} a_jb_k \\\\ &= fwt[c] \end{aligned} \]考虑按位计算fwt，如果新的一位是1，那么它要加上对应新的一位是0的值
然后IOR就是相当于逆运算（inv=-1）
void OR(int* f,int inv){
for(int l=1;l<=n/2;l<<=1) for(int i=1;i<=n;i+=l<<1) Fu(j,i,i+l-1)
f[j+l]=(1ll*f[j+l]+f[j]*inv+mod)%mod;
}
AND
构造和证明与OR类似
\[fwt_i=\sum_{j\&i=i}a_j \]考虑按位计算fwt，如果新的一位是0，那么它要加上对应新的一位是1的值
void AND(int* f,int inv){
for(int l=1;l<=n/2;l<<=1) for(int i=1;i<=n;i+=l<<1) Fu(j,i,i+l-1)
f[j]=(1ll*f[j]+f[j+l]*inv+mod)%mod;
}
XOR
定义 \(x\otimes y=\text{popcount}(x \& y) \bmod 2\)，其中 \(\text{popcount}\) 表示「二进制下 \(1\) 的个数」。
满足 \((i \otimes j) \operatorname{xor} (i \otimes k) = i \otimes (j \operatorname{xor} k)\)。
证明很好想，就是考虑1的个数mod2后xor，等价于加起来在异或，而+和xor的奇偶性不变
构造 \(fwt[a]_i = \sum_{i\otimes j = 0} a_j - \sum_{i\otimes j = 1} a_j\)。
\[\begin{aligned} fwt[a] \times fwt[b] &= \left(\sum_{i\otimes j = 0} a_j - \sum_{i\otimes j = 1} a_j\right)\left(\sum_{i\otimes k = 0} b_k - \sum_{i\otimes k = 1} b_k\right) \\ &=\left(\sum_{i\otimes j=0}a_j\right)\left(\sum_{i\otimes k=0}b_k\right)-\left(\sum_{i\otimes j=0}a_j\right)\left(\sum_{i\otimes k=1}b_k\right)-\left(\sum_{i\otimes j=1}a_j\right)\left(\sum_{i\otimes k=0}b_k\right)+\left(\sum_{i\otimes j=1}a_j\right)\left(\sum_{i\otimes k=1}b_k\right) \\ &=\sum_{i\otimes(j \operatorname{xor} k)=0}a_jb_k-\sum_{i\otimes(j\operatorname{xor} k)=1}a_jb_k \\ &= fwt[c] \end{aligned} \]很好证明，就是分配律，然后利用上面的性质化简
还是考虑一位一位计算，新加的一位如果是0，那么不改变\(\otimes\)后的值，直接把0,1都加上
如果是1，对于0的话不变，对于1的话变成相反数
最后IXOR的inv=1/2
void XOR(int* f,int inv){
for(int l=1;l<=n/2;l<<=1) for(int i=1;i<=n;i+=l<<1) Fu(j,i,i+l-1){
int x=f[j],y=f[j+l];
f[j]=1ll*inv*(x+y)%mod,f[j+l]=1ll*inv*(x-y+mod)%mod;
}
}
K-FWT（不会证明）
我们考虑上面都是分成两部分，然后左右两半对应位置（两个位置）进行变换得到新的答案
然后我们把他考虑成矩阵乘法形式，and，or，xor分别是一下三种
\[\begin{bmatrix} 1,0\\1,1 \end{bmatrix}\\ \begin{bmatrix} 1,1\\0,1 \end{bmatrix}\\ \begin{bmatrix} 1,&1\\1,&-1 \end{bmatrix} \]于是拓展成k维，就是全是1的下三角矩阵，上三角矩阵，和范德蒙德矩阵（如下）
\[\begin{bmatrix} 1& 1 & 1& ... & 1\\ 1& w_k^1& w_k^2& ... & w_k^{k - 1}\\ 1& w_k^2 & w_k^4& ... & w_k^{2(k - 1)}\\ ...& ...& ...& ...& ...\\ 1& w_k^{k - 1}& w_k^{2(k - 1)} & ... & w_k^{(k - 1)(k - 1)} \end{bmatrix} \]然后考虑枚举长度是k的倍数，然后分成k部分，对应位就有k个，然后乘完矩阵再放回去
贺别人的代码：
void DWT(Cp *a) // 也叫 K 进制不进位加法卷积；K 进制 FWT
{
static Cp t[10];
for(int d = 1; d < M; d = d * V) // 从低维向高维做
for(int i = 0; i < M; i += d * V)
for(int j = 0; j < d; ++j) // 枚举向量的第 j 位
{
for(int k = 0; k < V; ++k) // n^2 跑 dft
{
t[k] = Cp();
for(int p = 0; p < V; ++p)
t[k] = t[k] + a[i + j + p * d] * w[p * k];
}
for(int k = 0; k < V; ++k)
a[i + j + k * d] = t[k];
}
}
时间复杂度我觉得是\(nk\log n\)
例题（3维）：[P7930 [COCI2021-2022#1] Set](P7930 [COCI2021-2022#1] Set)
然后好像可以用原根代替单位根，然后就可以处理一些鬼畜的取mod
例题：P5109 归程
标签：right,int,sum,笔记,学习,fwt,FWT,otimes,left From： https://www.cnblogs.com/zhy114514/p/18028263