FWT / FMT 快速沃尔什/莫比乌斯变换 P4717

前言

在学过FFT/NTT后，我们已经可以解决许多多项式问题了，而出题人觉得还不够

所以我们接着来处理更复杂的多项式卷积------快速沃尔什变换和快速莫比乌斯变换

很多时候，人们把这两个变换同称为一个快速沃尔什变换，但实际上它们是分开的

快速莫比乌斯变换是来解决 与卷积、或卷积（也可认为是交卷积、并卷积），

note: 下文中我们的 ∗ * ∗ 不是卷积符号，仅仅是乘法

我们重新来看多项式的运算的定义： C = A + B , C [ k ] = ∑ i = j = k A [ i ] + B [ j ] C = A + B,C[k]=\sum_{i=j=k}A[i]+B[j] C=A+B,C[k]=i=j=k∑​A[i]+B[j] C = A × B , C [ k ] = ∑ i + j = k A [ i ] B [ j ] C = A \times B,C[k]=\sum_{i+j=k}A[i]B[j] C=A×B,C[k]=i+j=k∑​A[i]B[j] C = A ∣ B , C [ k ] = ∑ i ∣ j = k A [ i ] B [ j ] C = A \mid B,C[k]=\sum_{i|j=k}A[i]B[j] C=A∣B,C[k]=i∣j=k∑​A[i]B[j] C = A & B , C [ k ] = ∑ i & j = k A [ i ] B [ j ] C = A \And B,C[k]=\sum_{i \And j=k}A[i]B[j] C=A&B,C[k]=i&j=k∑​A[i]B[j] C = A ⊗ B , C [ k ] = ∑ i ⊗ j = k A [ i ] B [ j ] C = A \otimes B,C[k]=\sum_{i \otimes j=k}A[i]B[j] C=A⊗B,C[k]=i⊗j=k∑​A[i]B[j] 此时，我们也看的出来，多项式的算术运算和位运算还是有蛮大的区别 加法运算可线性得出，乘法运算则利用FFT/NTT亚线性得出 算数运算和位运算则是两条思路，一个寻找去寻找单位元，一个去寻找反演不变性

在位运算中，与运算、或运算属于FMT的范畴 因为本质上它们来源于集合上的莫比乌斯反演，与对应交，或对应并 而出题人最长出的异或则来源于快速沃尔什变换，其实也可以对应集合差的和

当然，这两个变换自然地借鉴了FFT/NTT的思想，即寻找一种变换和新运算使得多项式可以快速运算

FMT中，我们以或运算为例，寻求一种变换 F M T ( S ) FMT(S) FMT(S)和新运算 U ⋅ V U \cdot V U⋅V，使得 F M T ( C ) = F M T ( A ∣ B ) = F M T ( A ) ⋅ F M T ( B ) FMT(C)=FMT(A|B)=FMT(A)\cdot FMT(B) FMT(C)=FMT(A∣B)=FMT(A)⋅FMT(B)自然地， U ⋅ V U\cdot V U⋅V这个运算就让它是对应项相乘这个 O ( n ) O(n) O(n)运算好了，现在的问题就找变换了，使得： F M T ( ∑ k ∑ i ∣ j = k A [ i ] B [ j ] ) = F M T ( ∑ k A [ k ] ) F M T ( ∑ k B [ k ] ) FMT(\sum_k\sum_{i|j=k}A[i]B[j])=FMT(\sum_kA[k])FMT(\sum_kB[k]) FMT(k∑​i∣j=k∑​A[i]B[j])=FMT(k∑​A[k])FMT(k∑​B[k])此时，我们想到了集合上的莫比乌斯反演相关性质，受此启发 ∑ l ⊂ k ∑ i ∪ j = l A [ i ] B [ j ] = ∑ ( i ∪ j ) ⊂ k A [ i ] B [ j ] = ∑ i ⊂ k A [ i ] ∑ j ⊂ k B [ j ] \sum_{l\subset k}\sum_{i \cup j=l}A[i]B[j]=\sum_{(i\cup j)\sub k}A[i]B[j]=\sum_{i\sub k}A[i]\sum_{j\sub k}B[j] l⊂k∑​i∪j=l∑​A[i]B[j]=(i∪j)⊂k∑​A[i]B[j]=i⊂k∑​A[i]j⊂k∑​B[j]我们来定义 F M T FMT FMT为子集和： F M T ( A ) [ k ] = ∑ i ⊂ k A [ i ] FMT(A)[k]=\sum_{i\sub k}A[i] FMT(A)[k]=i⊂k∑​A[i]或者说： F M T ( A ) [ k ] = ∑ i ∣ k = k A [ i ] FMT(A)[k]=\sum_{i|k=k}A[i] FMT(A)[k]=i∣k=k∑​A[i]这样我们就可以解决其变换后的快速运算了，那进行变换本身的时间复杂度如何呢，

我们找找它的性质，发现： F M T ( < ϕ , U > ) = < F M T ( ϕ ) , F M T ( ϕ + U ) > FMT()= FMT()= F M T ( < A 0 , A 1 > ) = < F M T ( A 0 ) , F M T ( A 0 + A 1 ) > FMT()= FMT()=其中 A 0 A_0 A0​代表数位为0， A 1 A_1 A1​代表数位为1，很好，可以递归下去

and运算也有相似的性质，此处的变换不再是子集和，而是超集和 F M T o r ( < A 0 , A 1 > ) = < F M T o r ( A 0 ) , F M T o r ( A 0 + A 1 ) > FMTor()= FMTor()= F M T a n d ( < A 0 , A 1 > ) = < F M T a n d ( A 0 + A 1 ) , F M T a n d ( A 1 ) > FMTand()= FMTand()= 然后，我们来到FWT，它要解决异或问题，此时它似乎不再有上述性质了，我们需要另寻思路， 这时，我们可以考虑广义的模2，这样只需奇偶位对应即可，实际上两个递推左右交换也是可以的 F W T x o r ( < A 0 , A 1 > ) = < F W T x o r ( A 0 + A 1 ) , F W T x o r ( A 0 − A 1 ) > FWTxor()= FWTxor()=

一、例题

例题：洛谷 P4717

二、思路与代码 1.思路

很板子的一道板子题，直接上模板

2.代码

代码如下：

#include 
#define int long long
using namespace std;
const int mod = 998244353;
const int maxn = 1e7 + 9;
int n, N;
int a[maxn], b[maxn], ans[maxn];
int tempa[maxn], tempb[maxn];
int quickpow(int a, int n) {
  int ans = 1;
  while (n) {
    if (n & 1) ans = ans * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return ans;
}
int inv2 = quickpow(2, mod - 2);
// int inv2 = (mod + 1) / 2;
void FMTor(int a[], int inv) {
  for (int i = 1; i