引入
考虑一个基本问题：给定序列 \(a_n,b_n\)，求出序列 \(c_n\)，满足 \(c_i=\sum_{j \oplus k=i} a_jb_k\)，其中 \(\oplus\) 是一种二元运算符，形如上式的问题一般被称为卷积。
当 \(\oplus\) 为 \(+\) 时即为一般的卷积（和卷积），当 \(\oplus\) 为 \(\times\) 即为狄利克雷卷积。FMT 是用于解决 \(\oplus\) 为 \(and\) （与卷积）与 \(or\) （或卷积）的工具；FWT 是用于解决 \(\oplus\) 为 xor （异或卷积）的工具。
FMT & FWT
首先可以考虑 \(\max\) 卷积的计算方式，即 \(c_i=\sum_{\max(j,k)=i} a_j b_k\)，不难想到用容斥处理，即：
\[c_i=\sum_{max(j,k) \leq i} a_j b_k-\sum_{max(j,k) < i} a_j b_k \]\[=(\sum_{j \leq i} a_j) \times (\sum_{j \leq i} b_j)-(\sum_{j < i} a_j) \times (\sum_{j < i} b_j) \]因此该卷积的过程就是：
-
先对 \(a,b\) 序列求出前缀和；
-
再将 \(a,b\) 对应位置分别相乘；
-
最后对得到的序列进行查分。
这一过程与 FFT 中 求值-点值相乘-插值的过程极其相似，可以仿造这一过程完成与运算和或运算的卷积。
以或卷积为例：定义序列 \(a_0,a_1,\ldots a_{2^n-1}\) 的 FMT 变换为 \(FMT(a)_i=\sum_{j \in i} a_j\)，IFMT 变换为上述变换的逆变换，序列的点乘表示对应位置相乘，则不难发现或卷积等价于 \(c=IFMT(FMT(a)\cdot FMT(b))\)，时间复杂度为 \(O(n2^n)\)。
这里的 \(j \subseteq i\) 意为，二进制下 \(j\) 的每一位都小于等于 \(i\)，即 \(j\) 的二进制展开为 \(i\) 的二进制展开的子集。这也可以理解为重新定义了一种小于关系，那么就可以用类似于 \(\max\) 卷积的计算方式，即在二进制上的每一位都取最大值。不难发现，或卷积实质上就是做了一个 \(n\) 维的前缀和，得出或卷积的代码：
//FMT or
for(int i=0;i<m;i++)
for(int j=0;j<(1<<m);j++)
if((j>>i)&1) a[j]+=a[j-(1<<i)];
//IFMT or
for(int i=m-1;i>=0;i--)
for(int j=(1<<m)-1;j>=0;j--)
if((j>>i)&1) a[j]-=a[j-(1<<i)];
不难发现，在做高维前缀和的时候，枚举维度的顺序对答案是没有影响的，所以 IFMT 中第一层循环也可以正向枚举。在一般情况下前缀和变为差分是一定要从大往小枚举的，但由于此时每一维度上的值只能是 \(0\) 或 \(1\)，那么做差分的顺序也就不会影响答案了，可以将这两份代码合并：
//or
//FMT op=1
//IFMT op=-1
for(int i=0;i<m;i++)
for(int j=0;j<(1<<m);j++)
if((j>>i)&1) a[j]+=op*a[j-(1<<i)];
而对于与卷积，可以看成是在每一维上取最小值，那么和或卷积的区别就是把前缀和变为了后缀和，代码如下：
//and
for(int i=0;i<m;i++)
for(int j=0;j<(1<<m);j++)
if((j>>i)&1) a[j-(1<<i)]+=op*a[j];
而对于异或卷积，这两种办法就不适用了。异或运算本质可以看成高维不进位加法卷积。表达式为 \(FWT(a)_i=\sum_{j=0}^{2^n-1}(-1)^{|i \cap j|}a_j\)。那么就可以在每一维上实施长度为 \(2\) 的FFT。具体地，FWT 变换为：\((a_0,a_1) \to (a_0+a_1,a_0-a_1)\)。IFWT 变换为：\((a_0,a_1) \to (\frac{a_0+a_1}{2},\frac{a_0-a_1}{2})\)。通过代数的形式可以证明 \(IFWT(FWT(a_0,a_1) \cdot FWT(b_0,b_1)) \to (a_0b_0+a_1b_1,a_0b_1+a_1b_0)\)。代码如下：
//FWT
for(int i=0;i<m;i++)
for(int j=0;j<(1<<m);j++) if((j>>i)&1) {
int x=a[j-(1<<i)],y=a[j];
a[j-(1<<i)]=x+y,a[j]=x-y;
}
//IFWT
for(int i=0;i<m;i++)
for(int j=0;j<(1<<m);j++) if((j>>i)&1) {
int x=a[j-(1<<i)],y=a[j];
a[j-(1<<i)]=(x+y)/2,a[j]=(x-y)2;
}
最后，给出模板题的完整代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=(1<<17)+10,mod=998244353;
#define LL long long
LL a[N],b[N];int n,m,A[N],B[N];
void in(){for(int i=0;i<n;i++) a[i]=A[i],b[i]=B[i];}
void get(){for(int i=0;i<n;i++) a[i]=a[i]*b[i]%mod;}
void print(){for(int i=0;i<n;i++) printf("%lld ",a[i]);puts("");}
void OR(LL f[],int op)
{
for(int i=0;i<m;i++)
for(int j=0;j<(1<<m);j++)
if((j>>i)&1) f[j]=(f[j]+op*f[j-(1<<i)])%mod;
}
void AND(LL f[],int op)
{
for(int i=0;i<m;i++)
for(int j=0;j<(1<<m);j++)
if((j>>i)&1) f[j-(1<<i)]=(f[j-(1<<i)]+op*f[j])%mod;
}
void XOR(LL f[],int op)
{
for(int i=0;i<m;i++)
for(int j=0;j<(1<<m);j++) if((j>>i)&1)
{
LL x=f[j-(1<<i)],y=f[j];
f[j-(1<<i)]=(x+y)*op%mod,f[j]=(x-y+mod)*op%mod;
}
}
int main()
{
scanf("%d",&m);n=1<<m;
for(int i=0;i<n;i++) scanf("%d",&A[i]);
for(int i=0;i<n;i++) scanf("%d",&B[i]);
in();OR(a,1),OR(b,1),get(),OR(a,mod-1),print();
in();AND(a,1),AND(b,1),get(),AND(a,mod-1),print();
in();XOR(a,1),XOR(b,1),get(),XOR(a,499122177),print();
}