FWT

系统管理员 2022-10-02 15:58 181阅读 0赞

# 快速沃尔什变换    #

fengwentao

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

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

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

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

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

考虑怎么求A'。

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

然后求A1，A1i表示二进制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...

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     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 }

洛谷P4717 快速沃尔什变换

转载于:https://www.cnblogs.com/huyufeifei/p/10513402.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220109/d2ed1903d9894c5d874e8ee7ee7c082b.png