快速沃尔什变换

 

fengwentao

解决集合卷积。说人话就是把FFT下标的+变成位运算。

&和|的FWT可以用高维前缀和来理解。

考虑对于A | B = C，我们有A'_i = ∑A_j，其中j⊂i。B同理。

接下来我们把A'和B'对位相乘得C'。显然有C'_i = ∑C_j，其中j⊂i。

接下来把C逆变换回去即可。

考虑怎么求A'。

我们先求一次A⁰，A⁰_i表示二进制第0位是i的子集，0位以上都是严格等于i的位置权值和。

然后求A¹，A¹_i表示二进制0,1位都是i的子集，而1位以上严格等于i的位置权值和。

然后搞完最高位就完事了。逆变换就反着来。

异或是什么毒瘤？见鬼去吧！

核心片段背诵：

|：(0, 1) -> (0, 0 + 1)          逆：(0, 1) -> (0, 0 - 1)

&：(0, 1) -> (0 + 1, 1)              (0, 1) -> (0 - 1, 1)

^：(0, 1) -> (0 + 1, 0 - 1)          (0, 1) -> ((0 + 1) / 2， (0 - 1) / 2)

写法跟FFT差不多，尤其是xor...

首先是裸到爆炸的模板题...

 

1 #include 
      
        2  3 const int N = 140010, MO = 998244353, inv2 = 499122177; 4  5 int a[N], b[N], c[N]; 6  7 inline void FWT_or(int *a, int n, int f) { 8     for(int len = 1; len < n; len <<= 1) { 9         for(int i = 0; i < n; i += (len << 1)) {10             for(int j = 0; j < len; j++) {11                 a[i + len + j] = (a[i + len + j] + f * a[i + j]) % MO;12             }13         }14     }15     return;16 }17 18 inline void FWT_and(int *a, int n, int f) {19     for(int len = 1; len < n; len <<= 1) {20         for(int i = 0; i < n; i += (len << 1)) {21             for(int j = 0; j < len; j++) {22                 a[i + j] = (a[i + j] + f * a[i + len + j]) % MO;23             }24         }25     }26     return;27 }28 29 inline void FWT_xor(int *a, int n, int f) {30     for(int len = 1; len < n; len <<= 1) {31         for(int i = 0; i < n; i += (len << 1)) {32             for(int j = 0; j < len; j++) {33                 int t = a[i + len + j];34                 a[i + len + j] = (a[i + j] - t) % MO;35                 a[i + j] = (a[i + j] + t) % MO;36                 if(f == -1) {37                     a[i + j] = 1ll * a[i + j] * inv2 % MO;38                     a[i + len + j] = 1ll * a[i + len + j] * inv2 % MO;39                 }40             }41         }42     }43     return;44 }45 46 int main() {47 48     int lm, n;49     scanf("%d", &lm);50     n = 1 << lm;51     for(int i = 0; i < n; i++) {52         scanf("%d", &a[i]);53     }54     for(int i = 0; i < n; i++) {55         scanf("%d", &b[i]);56     }57 58     FWT_or(a, n, 1); FWT_or(b, n, 1);59     for(int i = 0; i < n; i++) c[i] = 1ll * a[i] * b[i] % MO;60     FWT_or(a, n, -1); FWT_or(b, n, -1); FWT_or(c, n, -1);61     for(int i = 0; i < n; i++) {62         printf("%d ", (c[i] + MO) % MO);63     }64     puts("");65 66     FWT_and(a, n, 1); FWT_and(b, n, 1);67     for(int i = 0; i < n; i++) c[i] = 1ll * a[i] * b[i] % MO;68     FWT_and(a, n, -1); FWT_and(b, n, -1); FWT_and(c, n, -1);69     for(int i = 0; i < n; i++) {70         printf("%d ", (c[i] + MO) % MO);71     }72     puts("");73 74     FWT_xor(a, n, 1); FWT_xor(b, n, 1);75     for(int i = 0; i < n; i++) c[i] = 1ll * a[i] * b[i] % MO;76     FWT_xor(a, n, -1); FWT_xor(b, n, -1); FWT_xor(c, n, -1);77     for(int i = 0; i < n; i++) {78         printf("%d ", (c[i] + MO) % MO);79     }80     puts("");81 82     return 0;83 }