快速沃尔什变换

Posted on | In | | Visitors:
Words count in article: 1.9k | Reading time ≈ 10

集合幂级数

给每个$S\in 2^A$赋予一个权值$w(S)$，则定义它关联的集合幂级数为

与、或、异或卷积

定义两个形式幂级数$f(x)=\sum\limits_{i=0}^{2^n-1}a_ix^i,g(x)=\sum\limits_{i=0}^{2^n-1}b_ix^i$的积为$h(x)=\sum\limits_{i=0}^{2^n-1}c_ix^i$，其中$c_k=\sum_{i\otimes j=k}a_ib_j$，$\otimes$可以为$\&,|,\oplus$中的一种，分别称为对应的积为与、或、异或卷积。

快速沃尔什变换（FMT/FWT）

与卷积

求解$C_k=\sum\limits_{i\&j=k}A_iB_j$
考虑找到一种操作$\mathcal{F}(A)$，使得其满足如下条件：

  • $\mathcal{F}(A)$存在逆变换$\mathcal{F}^{-1}(\mathcal{F}(A))=A$
  • $\mathcal{F}(A)_i\times \mathcal{F}(B)_i=\mathcal{F}(C)_i$
  • $\mathcal{F}(A+B)=\mathcal{F}(A)+\mathcal{F}(B)$

将$A,B,C$分成$[0,2^{n-1}-1],[2^{n-1},2^n-1]$两部分，分别记作$A_0,A_1,B_0,B_1,C_0,C_1$。
很明显有

这里$\times$表示每一位相乘，进一步化简得

所以$\mathcal{F}$操作可以为

正逆变换复杂度都是$O(n2^n)$。

或卷积

求解$C_k=\sum\limits_{i|j-k}A_iB_j$
和$\&$卷积相同的思路，需要满足

得到的$\mathcal{F}$操作为

异或卷积

求解$C_k=\sum\limits_{i\oplus j=k}A_iB_j$
和$\&$卷积相同的思路，需要满足

即

得到的$\mathcal{F}$操作为

总结

找到一种关于集合幂级数的可逆变换$\mathcal{F}$，使得$h(x)=f(x)g(x)$满足
$[x^i]\mathcal{F}(h(x))=[x^i]\mathcal{F}(f(x))\cdot[x^i]\mathcal{F}(g(x))\;(0\le i<2^n)$

假设$f(x)=f_0(x)+x^{2^{n-1}}f_1(x)$，则$\mathcal{F}$为：

  • 与卷积：$\mathcal{F}(f)=(\mathcal{F}(f_0)+\mathcal{F}(f_1))+x^{2^{n-1}}\mathcal{F}(f_1)$
  • 或卷积：$\mathcal{F}(f)=\mathcal{F}(f_0)+x^{2^{n-1}}(\mathcal{F}(f_0)+\mathcal{F}(f_1))$
  • 异或卷积：$\mathcal{F}(f)=(\mathcal{F}(f_0)+\mathcal{F}(f_1))+x^{2^{n-1]}}(\mathcal{F}(f_0)-\mathcal{F}(f_1))$

它们的逆运算：

  • 与卷积：$\mathcal{F}^{-1}(f)=(\mathcal{F}^{-1}(f_0)-\mathcal{F}^{-1}(f_1))+x^{2^{n-1}}\mathcal{F}(f_1)$
  • 或卷积：$\mathcal{F}^{-1}(f)=\mathcal{F}^{-1}(f_0)+x^{2^{n-1}}(\mathcal{F}^{-1}(f_1)-\mathcal{F}^{-1}(f_0))$
  • 异或卷积：$\mathcal{F}^{-1}(f)=\dfrac{1}{2}((\mathcal{F}^{-1}(f_0)+\mathcal{F}^{-1}(f_1))+x^{2^{n-1}}(\mathcal{F}^{-1}(f_0)-\mathcal{F}^{-1}(f_1)))$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
template <class T>
void Or_FWT(T f[], int n, int opt) {//opt=1为正变换
    for (int len = 2, mid = 1; len <= n; len <<= 1, mid <<= 1) {
        for (int i = 0; i < n; i += len) {
            for (int j = 0; j < mid; ++j) {
                if (opt == 1)f[i + j + mid] = ADD(f[i + j + mid], f[i + j]);
                else f[i + j + mid] = DEL(f[i + j + mid], f[i + j]);
            }
        }
    }
}
template <class T>
void And_FWT(T f[], int n, int opt) {
    for (int len = 2, mid = 1; len <= n; len <<= 1, mid <<= 1) {
        for (int i = 0; i < n; i += len) {
            for (int j = 0; j < mid; ++j) {
                if (opt == 1)f[i + j] = ADD(f[i + j], f[i + j + mid]);
                else f[i + j] = DEL(f[i + j], f[i + j + mid]);
            }
        }
    }
}
template <class T>
void Xor_FWT(T f[], int n, int opt) {
    for (int len = 2, mid = 1; len <= n; len <<= 1, mid <<= 1) {
        for (int i = 0; i < n; i += len) {
            for (int j = 0; j < mid; ++j) {
                f[i + j] = ADD(f[i + j], f[i + j + mid]);
                f[i + j + mid] = DEL(f[i + j], ADD(f[i + j + mid], f[i + j + mid]));
                if (opt != 1) {
                    (f[i + j] *= mod + 1 >> 1) %= mod;
                    (f[i + j + mid] *= mod + 1 >> 1) %= mod;
                }
            }
        }
    }
}

分治FWT

分治FWT可以每次直接算两个子区间的异或卷积然后再直接卷起来，$O(n\log^2 n)$进行，但实际上可以做到$O(n\log n)$。
实际上，可以通过$2^{L-1}$长度的FWT计算$2^{L}$长度的FWT，且复杂度为$O(2^L)$。
以异或卷积为例，$n$个集合幂级数的异或卷积需要考虑取的数的个数是奇数还是偶数，同时也需要考虑高位和低位，记为$p_{0/1},q_{0/1}$，$p,q$表示低、高位，$0/1$表示取的数个数的奇偶。

考虑将异或卷积的FWT计算过程看成矩阵变换，设变换矩阵

现在已知$\mathcal{F}(p_0),\mathcal{F}(p_1),\mathcal{F}(q_0),\mathcal{F}(q_1)$，要求$\mathcal{F}(C)$。根据$\mathcal{F}$的线性性，可以将每一项卷积的FWT分开计算再合并。
考虑式子中每一项卷积构成的列向量分别为

将其分别与变换矩阵相乘，就得到

因此就有

最后将$\mathcal{F}(C_0)$和$\mathcal{F}(C_1)$用IFWT还原即可。

子集卷积（FST）

设集合幂级数$f(x)=\sum\limits_{i=0}^{2^{n-1}}a_ix^i,g(x)=\sum\limits_{i=0}^{2^{n-1}}b_ix^i$，定义卷积$h(x)=f(x)g(x)$，其中$h(x)=\sum\limits_{i=0}^{2^n}c_ix^i$满足

将$f(x)$扩展为二元多项式$f(x,y)=\sum\limits_{i=0}^{2^n-1}a_ix^iy^{\text{cnt}(i)}=\sum\limits_{i=0}^{2^n-1}\sum\limits_{j=0}^{n}a_{i,j}x^iy^j$，则以上表达式改写为$h(x)=\sum\limits_{i=0}^{2^n-1}\sum\limits_{j=0}^nc_{i,j}x^iy^j$，其中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <class T>
void FST(T ans[], T a[], T b[], int m, int n) {
    //结果的幂次在2^m内
    for (int i = 0; i < n; ++i)f[cnt[i]][i] = a[i];
    for (int i = 0; i < n; ++i)g[cnt[i]][i] = b[i];
    for (int i = 0; i < m; ++i) {
        Or_FWT(f[i], n, 1);
        Or_FWT(g[i], n, 1);
    }
    for (int i = 0; i <= m; ++i) {
        for (int j = 0; i + j <= m; ++j) {
            for (int k = 0; k < n; ++k) {
                h[i + j][k] = ADD(h[i + j][k], f[i][k] * g[j][k] % mod);
            }
        }
    }
    for (int i = 0; i < m; ++i)
        Or_FWT(h[i], n, -1);
    for (int i = 0; i < n; ++i)
        ans[i] = h[cnt[i]][i];
}