解决的问题
\(\rm FWT\) 是用来解决位运算卷积的。
啥是位运算卷积呢？
常见的多项式乘法可以认为是一种加法卷积，即 \(A_{i+j}=\sum B_i \times C_j\)。
位运算卷积就是 \(A_{i \ \text{Or/And/Xor} \ j}=\sum B_i \times C_j\)。
主要思想
现在以异或卷积为例，默认 \(n=2^k\)。
回忆 \(\rm FFT/NTT\) 的过程，最重要的一步就是把多项式转成点值表示，然后卷积就变成了点积。
所以，我们希望 \(\rm FWT\) 也能把卷积转成点积。
设 \(\text{FWT}(A)\) 表示幂级数 \(A\) 通过 \(\rm FWT\) 转化成的幂级数。
我们想让 \(\rm FWT\) 满足若 \(A * B = C\)，则
\[\text{FWT}(A) ⋅ \text{FWT}(B)=\text{FWT}(C) \]设 \(c(i,j)\) 为 \(A_j\) 贡献到 \(\text{FWT}(A)_j\) 的系数。
那么有 \(\text{FWT}(A)_i = \sum A_j \times c(i,j)\)。
带入原式，得到：
\[\sum A_j \times c(i,j) \times \sum B_k \times c(i,k) = \sum C_p \times c(i,p) \]\[\sum \sum c(i,j)c(i,k)A_jB_k=\sum C_p \times c(i,p) \]又由于 \(A * B = C\)，所以：
\[C_p = \sum_{t1 \oplus t2=p} A_{t1} \times B_{t2} \]\[\sum \sum c(i,j)c(i,k)A_jB_k=\sum_{p=0}^{n-1} c(i,p) \times \sum_{t1 \oplus t2=p} A_{t1} \times B_{t2} \]又因为：
\[\sum \sum c(i,j)c(i,k)A_jB_k=\sum_{p=0}^{n-1} \sum_{t1 \oplus t2=p} c(i,t1)c(i,t2)A_{t1}B_{t2}=\sum_{p=0}^{n-1} \sum_{t1 \oplus t2=p} c(i,t1) \times c(i,t2) \sum_{t1 \oplus t2=p} A_{t1} \times B_{t2} \]然后就得到：
\[\sum_{p=0}^{n-1} c(i,p) \times \sum_{t1 \oplus t2=p} A_{t1} \times B_{t2}=\sum_{p=0}^{n-1} \sum_{t1\oplus t2=p} c(i,t1) \times c(i,t2) \sum_{t1 \oplus t2=p} A_{t1} \times B_{t2} \]所以 \(c\) 只需满足 \(c(i,j) \times c(i,k)=c(i,j \oplus k)\)。
又因为位运算的独立性，所以 \(c(i,j)\) 可以分位考虑。
设 \(d(0/1,0/1)\) 表示某种满足要求的变换。
那么把每一位乘起来，设 \(x_i\) 表示 \(x\) 的二进制第 \(i\) 位，得到
\[c(i,j) = d(i_0,j_0) \times d(i_1,j_1) \times ... \]实现
假设我们已经求出 \(c\) 和 \(d\)，那么我们现在需要快速求解。
\[\text{FWT}(A)_i=\sum c(i,j) \times A_j \]那么根据位运算的优秀性质，设 \(x'\) 表示 \(x\) 去掉二进制首位后变成的数，我们可以从中间劈开来，得到：
\[\text{FWT}(A)_i=\sum_{j=0}^{\frac{n}{2}-1} c(i,j) \times A_j + \sum_{j=\frac{n}{2}}^{n-1} c(i,j) \times A_j \]\[\text{FWT}(A)_i=\sum_{j=0}^{\frac{n}{2}-1} d(i_0,j_0) \times c(i,j) \times A_j + \sum_{j=\frac{n}{2}}^{n-1} d(i_0,j_0) \times c(i,j) \times A_j \]\[\text{FWT}(A)_i=d(i_0,0) \times \sum_{j=0}^{\frac{n}{2}-1} c(i,j) \times A_j + d(i_0,1) \times \sum_{j=\frac{n}{2}}^{n-1} c(i,j) \times A_j \]设 \(A_0\) 为幂级数下标首位为零的部分，\(A_1\) 为幂级数下标首位为一的部分。
如果 \(i_0=0\)，那么有：
\[\text{FWT}(A)_i=d(0,0) \text{FWT}(A_0)_i + d(0,1) \text{FWT}(A_1)_i \]如果 \(i_0=1\)，那么有：
\[\text{FWT}(A)_i=d(1,0) \text{FWT}(A_0)_i + d(1,1) \text{FWT}(A_1)_i \]这里 \(\text{FWT}(A_{0/1})_i\) \(i\) 的范围都是 \([0,\frac{n}{2})\)。
这样我们就可以 \(\mathcal O(n)\) 合并 \(A_0\) 和 \(A_1\) 了，而 \(A_0\) 和 \(A_1\) 的规模都是原问题的一半，所以复杂度为 \(\mathcal O(n \log n)\)。
\(\rm FWT\) 逆变换就相当于矩阵求逆。
inline void FWT(mint *f,const mint d[2][2],int n){
for (int len=1;len<n;len<<=1)
for (int p=0;p<n;p+=len+len)
for (int i=p;i<p+len;++i){
mint A=f[i],B=f[i+len];
f[i]=d[0][0]*A+d[0][1]*B;
f[i+len]=d[1][0]*A+d[1][1]*B;
}
}
inline void get(mint *a,mint *b,const mint d[2][2],const mint id[2][2]){
FWT(a,d,n),FWT(b,d,n);
for (int i=0;i<n;++i) a[i]*=b[i];
FWT(a,id,n);
}
求解 \(d\) 矩阵
根据定义直接硬推，过程不放了，放几个结论。
\(\rm Or\) 运算的矩阵为：\(\left[\begin{matrix}1 & 0\\1 & 1\end{matrix}\right]\)，逆矩阵为：\(\left[\begin{matrix}1 & 0\\-1 & 1\end{matrix}\right]\)。
\(\rm And\) 运算的矩阵为：\(\left[\begin{matrix}1 & 1\\0 & 1\end{matrix}\right]\)，逆矩阵为：\(\left[\begin{matrix}1 & -1\\0 & 1\end{matrix}\right]\)。
\(\rm Xor\) 运算的矩阵为：\(\left[\begin{matrix}1 & 1\\1 & -1\end{matrix}\right]\)，逆矩阵为：\(\left[\begin{matrix}0.5 & 0.5\\0.5 & -0.5\end{matrix}\right]\)。