「算法笔记」快速沃尔什变换 FWT

快速沃尔什变换用于解决多项式位运算卷积。其计算过程和 $\text{FFT}$ 类似。


概述

首先我们回忆一下多项式卷积:

$$ C_k = \sum_{i + j = k} A_i\times B_j $$

「算法笔记」快速傅里叶变换 FFT 中我们将多项式 $A(x)$ 和 $B(x)$ 转化为点值表达,然后重新转化为系数表达。

接下来考虑如下卷积形式:

$$ \begin{align*} C_k &= \sum_{i | j = k} A_i\times B_j \\ C_k &= \sum_{i \& j = k} A_i\times B_j \\ C_k &= \sum_{i \oplus j = k} A_i\times B_j \end{align*} $$

其中 $|, \&, \oplus$ 分别表示按位或、按位与、按位异或。

这样就没法使用 $\text{FFT}​$ 解决了,我们需要引进新的方法:快速沃尔什变换

下文会分类介绍这 $3$ 类卷积的解决方法。其中定义部分是一种构造出来的变换方法,证明部分将使用数学归纳法证明一些引理或定理,代码部分为该卷积的实现。


符号表示

首先我们认为下文提及的多项式的长度均为 $2$ 的非负整数次幂。为了方便表述,我们定义如下如下符号及其含义,下文不再赘述。

$$ \begin{array}{} A, B & \text{多项式,其长度为}\ n\text{,次数为}\ n - 1 \\ A_0, A_1 & \text{多项式}\ A\ \text{的前}\ \frac{n}{2}\ \text{位、后}\ \frac{n}{2}\ \text{位} \\ A + B & \text{将多项式}\ A, B\ \text{对应位加(减、乘),} \\ & \text{其系数表达式为}\ (A_0 + B_0, A_1 + B_1, \cdots, A_{n - 1} + B_{n - 1}) \\ A \oplus B & \text{将多项式}\ A, B\ \text{异或(与、或)卷积,} \\ & \text{其系数表达式为}\ (\sum_{i \oplus j = 0} A_i \times B_j, \sum_{i \oplus j = 1} A_i \times B_j, \cdots, \sum_{i \oplus j = n - 1} A_i \times B_j) \\ \text{FWT}(A) & \text{多项式}\ A\ \text{的 FWT 变换} \\ (A, B) & \text{将多项式}\ A, B\ \text{前后拼接起来} \end{array} $$

其中需要尤其注意:这里定义的多项式异或、与、或均为卷积形式!并不是对应系数位运算!


或卷积

定义

$$ \text{FWT}(A) = \begin{cases} (\text{FWT}(A_0), \text{FWT}(A_0 + A_1)) & n > 1 \\ A & n = 1 \end{cases} $$

证明

  1. 两个多项式相加后的 $\text{FWT}$ 变换等于分别 $\text{FWT}$ 的和:$\text{FWT}(A + B) = \text{FWT}(A) + \text{FWT}(B)$

    • 当 $n = 1$ 时

$$ \begin{align*} \text{FWT}(A + B) & = A + B \\ & = \text{FWT}(A) + \text{FWT}(B) \end{align*} $$

  • 当 $n > 1$ 时

$$ \begin{align*} \text{FWT}(A + B) & = (\text{FWT}(A_0 + B_0), \text{FWT}(A_0 + A_1 + B_0 + B_1)) \\ & = (\text{FWT}(A_0) + \text{FWT}(B_0), \text{FWT}(A_0) + \text{FWT}(A_1) + \text{FWT}(B_0) + \text{FWT}(B_1)) \\ & = (\text{FWT}(A_0) , \text{FWT}(A_0) + \text{FWT}(A_1)) + (\text{FWT}(B_0), \text{FWT}(B_0) + \text{FWT}(B_1)) \\ & = \text{FWT}(A) + \text{FWT}(B) \end{align*} $$

  1. 两个多项式或卷积的 $\text{FWT}$ 变换等于分别 $\text{FWT}$ 的积:$\text{FWT}(A | B) = \text{FWT}(A)\times FWT(B)$

    • 当 $n = 1$ 时

$$ \begin{align*} \text{FWT}(A | B) & = A \times B \\ & = \text{FWT}(A) \times \text{FWT}(B) \end{align*} $$

  • 当 $n > 1$ 时

$$ \begin{align*} \text{FWT}(A | B) & = \text{FWT}((A | B)_0, (A | B)_1) \\ & = \text{FWT}(A_0 | B_0, A_0 | B_1 + A_1 | B_0 + A_1 | B_1) \\ & = (\text{FWT}(A_0 | B_0), \text{FWT}(A_0 | B_0 + A_0 | B_1 + A_1 | B_0 + A_1 | B_1)) \\ & = (\text{FWT}(A_0) \times \text{FWT}(B_0), \\ & \qquad \text{FWT}(A_0) \times \text{FWT}(B_0) + \text{FWT}(A_0) \times \text{FWT}(B_1) + \text{FWT}(A_1) \times \text{FWT}(B_0) + \text{FWT}(A_1) \times \text{FWT}(B_1)) \\ & = (\text{FWT}(A_0) \times \text{FWT}(B_0), (\text{FWT}(A_0) + \text{FWT}(A_1)) \times (\text{FWT}(B_0) + \text{FWT}(B_1))) \\ & = (\text{FWT}(A_0) \times \text{FWT}(B_0), \text{FWT}(A_0 + A_1) \times \text{FWT}(B_0 + B_1)) \\ & = (\text{FWT}(A_0), \text{FWT}(A_0 + A_1)) \times (\text{FWT}(B_0), \text{FWT}(B_0 + B_1)) \\ & = \text{FWT}(A)\times \text{FWT}(B) \end{align*} $$

逆变换

$$ \text{FWT}(A) = (\text{FWT}(A_0), \text{FWT}(A_0) + \text{FWT}(A_1)) \\ \text{IFWT}(A) = (\text{IFWT}(A_0), \text{IFWT}(A_1) - \text{IFWT}(A_0)) $$

代码

void FWTor(std::vector<int> &a, bool rev) {
    int n = a.size();
    for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
        for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
            if (!rev) add(a[i + j + m], a[i + j]);
            else sub(a[i + j + m], a[i + j]);
        }
    }
}

与卷积

定义

$$ \text{FWT}(A) = \begin{cases} (\text{FWT}(A_0 + A_1), \text{FWT}(A_1)) & n > 1 \\ A & n = 1 \end{cases} $$

证明

  1. 两个多项式相加后的 $\text{FWT}$ 变换等于分别 $\text{FWT}$ 的和:$\text{FWT}(A + B) = \text{FWT}(A) + \text{FWT}(B)$

    • 当 $n = 1$ 时

$$ \begin{align*} \text{FWT}(A + B) & = A + B \\ & = \text{FWT}(A) + \text{FWT}(B) \end{align*} $$

  • 当 $n > 1$ 时

$$ \begin{align*} \text{FWT}(A + B) & = (\text{FWT}(A_0 + A_1 + B_0 + B_1), \text{FWT}(A_1 + B_1)) \\ & = (\text{FWT}(A_0) + \text{FWT}(A_1) + \text{FWT}(B_0) + \text{FWT}(B_1), \text{FWT}(A_1) + \text{FWT}(B_1)) \\ & = (\text{FWT}(A_0) + \text{FWT}(A_1), \text{FWT}(A_1)) + (\text{FWT}(B_0) + \text{FWT}(B_1), \text{FWT}(B_1)) \\ & = \text{FWT}(A) + \text{FWT}(B) \end{align*} $$

  1. 两个多项式与卷积的 $\text{FWT}$ 变换等于分别 $\text{FWT}$ 的积:$\text{FWT}(A \& B) = \text{FWT}(A)\times FWT(B)$

    • 当 $n = 1​$ 时

$$ \begin{align*} \text{FWT}(A \& B) & = A \times B \\ & = \text{FWT}(A) \times \text{FWT}(B) \end{align*} $$

  • 当 $n > 1​$ 时

$$ \begin{align*} \text{FWT}(A \& B) & = \text{FWT}((A \& B)_0, (A \& B)_1) \\ & = \text{FWT}(A_0 \& B_0 + A_1 \& B_0 + A_0 \& B_1, A_1 \& B_1) \\ & = (\text{FWT}(A_0 \& B_0 + A_1 \& B_0 + A_0 \& B_1 + A_1 \& B_1), \text{FWT}(A_1 \& B_1)) \\ & = (\text{FWT}(A_0) \times \text{FWT}(B_0) + \text{FWT}(A_0) \times \text{FWT}(B_1) + \text{FWT}(A_1) \times \text{FWT}(B_0) + \text{FWT}(A_1) \times \text{FWT}(B_1), \\ & \qquad \text{FWT}(A_1) \times \text{FWT}(B_1)) \\ & = ((\text{FWT}(A_0) + \text{FWT}(A_1)) \times (\text{FWT}(B_0) + \text{FWT}(B_1)), \text{FWT}(A_1) \times \text{FWT}(B_1)) \\ & = (\text{FWT}(A_0 + A_1) \times \text{FWT}(B_0 + B_1), \text{FWT}(A_1) \times \text{FWT}(B_1)) \\ & = (\text{FWT}(A_0 + A_1), \text{FWT}(A_1)) \times (\text{FWT}(B_0 + B_1), \text{FWT}(B_1)) \\ & = \text{FWT}(A)\times \text{FWT}(B) \end{align*} $$

逆变换

$$ \text{FWT}(A) = (\text{FWT}(A_0) + \text{FWT}(A_1), \text{FWT}(A_1)) \\ \text{IFWT}(A) = (\text{IFWT}(A_0) - \text{IFWT}(A_1), \text{IFWT}(A_1)) $$

代码

void FWTand(std::vector<int> &a, bool rev) {
    int n = a.size();
    for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
        for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
            if (!rev) add(a[i + j], a[i + j + m]);
            else sub(a[i + j], a[i + j + m]);
        }
    }
}

异或卷积

定义

$$ \text{FWT}(A) = \begin{cases} (\text{FWT}(A_0 + A_1), \text{FWT}(A_0 -A_1)) & n > 1 \\ A & n = 1 \end{cases} $$

证明

  1. 两个多项式相加后的 $\text{FWT}$ 变换等于分别 $\text{FWT}$ 的和:$\text{FWT}(A + B) = \text{FWT}(A) + \text{FWT}(B)$

    • 当 $n = 1$ 时

$$ \begin{align*} \text{FWT}(A + B) & = A + B \\ & = \text{FWT}(A) + \text{FWT}(B) \end{align*} $$

  • 当 $n > 1$ 时

$$ \begin{align*} \text{FWT}(A + B) & = (\text{FWT}(A_0 + A_1 + B_0 + B_1), \text{FWT}(A_0 - A_1 + B_0 - B_1)) \\ & = (\text{FWT}(A_0) + \text{FWT}(A_1) + \text{FWT}(B_0) + \text{FWT}(B_1), \text{FWT}(A_0) - \text{FWT}(A_1) + \text{FWT}(B_0) - \text{FWT}(B_1)) \\ & = (\text{FWT}(A_0) + \text{FWT}(A_1), \text{FWT}(A_0) - \text{FWT}(A_1)) + (\text{FWT}(B_0) + \text{FWT}(B_1), \text{FWT}(B_0) - \text{FWT}(B_1)) \\ & = \text{FWT}(A) + \text{FWT}(B) \end{align*} $$

  1. 两个多项式异或卷积的 $\text{FWT}​$ 变换等于分别 $\text{FWT}​$ 的积:$\text{FWT}(A \oplus B) = \text{FWT}(A)\times FWT(B)​$

    • 当 $n = 1​$ 时

$$ \begin{align*} \text{FWT}(A \oplus B) & = A \times B \\ & = \text{FWT}(A) \times \text{FWT}(B) \end{align*} $$

  • 当 $n > 1$ 时

$$ \begin{align*} \text{FWT}(A \oplus B) & = \text{FWT}((A \oplus B)_0, (A \oplus B)_1) \\ & = \text{FWT}(A_0 \oplus B_0 + A_1 \oplus B_1, A_0 \oplus B_1 + A_1 \oplus B_0) \\ & = (\text{FWT}(A_0 \oplus B_0 + A_1 \oplus B_1 + A_0 \oplus B_1 + A_1 \oplus B_0), \text{FWT}(A_0 \oplus B_0 + A_1 \oplus B_1 - A_0 \oplus B_1 - A_1 \oplus B_0)) \\ & = (\text{FWT}(A_0) \times \text{FWT}(B_0) + \text{FWT}(A_1) \times \text{FWT}(B_1) + \text{FWT}(A_0) \times \text{FWT}(B_1) + \text{FWT}(A_1) \times \text{FWT}(B_0), \\ & \qquad \text{FWT}(A_0) \times \text{FWT}(B_0) + \text{FWT}(A_1) \times \text{FWT}(B_1) - \text{FWT}(A_0) \times \text{FWT}(B_1) - \text{FWT}(A_1) \times \text{FWT}(B_0)) \\ & = ((\text{FWT}(A_0) + \text{FWT}(A_1)) \times (\text{FWT}(B_0) + \text{FWT}(B_1)), (\text{FWT}(A_0) - \text{FWT}(A_1)) \times (\text{FWT}(B_0) - \text{FWT}(B_1))) \\ & = (\text{FWT}(A_0 + A_1) \times \text{FWT}(B_0 + B_1), \text{FWT}(A_0 - A_1) \times \text{FWT}(B_0 - B_1)) \\ & = (\text{FWT}(A_0 + A_1), \text{FWT}(A_0 - A_1)) \times (\text{FWT}(B_0 + B_1), \text{FWT}(B_0 - B_1)) \\ & = \text{FWT}(A)\times \text{FWT}(B) \end{align*} $$

逆变换

$$ \text{FWT}(A) = (\text{FWT}(A_0) + \text{FWT}(A_1), \text{FWT}(A_0) - \text{FWT}(A_1)) \\ \text{IFWT}(A) = \left(\frac{\text{IFWT}(A_0) + \text{IFWT}(A_1)}{2}, \frac{\text{IFWT}(A_0) - \text{IFWT}(A_1)}{2}\right) $$

代码

void FWTxor(std::vector<int> &a, bool rev) {
    int n = a.size(), inv2 = (P + 1) >> 1;
    for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
        for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
            int x = a[i + j], y = a[i + j + m];
            if (!rev) {
                a[i + j] = (x + y) % P;
                a[i + j + m] = (x - y + P) % P;
            } else {
                a[i + j] = 1LL * (x + y) * inv2 % P;
                a[i + j + m] = 1LL * (x - y + P) * inv2 % P;
            }
        }
    }
}

完整代码

#include <cstdio>
#include <algorithm>
#include <vector>

const int P = 998244353;

void add(int &x, int y) {
    (x += y) >= P && (x -= P);
}
void sub(int &x, int y) {
    (x -= y) < 0 && (x += P);
}
struct FWT {
    int extend(int n) {
        int N = 1;
        for (; N < n; N <<= 1);
        return N;
    }
    void FWTor(std::vector<int> &a, bool rev) {
        int n = a.size();
        for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
            for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
                if (!rev) add(a[i + j + m], a[i + j]);
                else sub(a[i + j + m], a[i + j]);
            }
        }
    }
    void FWTand(std::vector<int> &a, bool rev) {
        int n = a.size();
        for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
            for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
                if (!rev) add(a[i + j], a[i + j + m]);
                else sub(a[i + j], a[i + j + m]);
            }
        }
    }
    void FWTxor(std::vector<int> &a, bool rev) {
        int n = a.size(), inv2 = (P + 1) >> 1;
        for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
            for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
                int x = a[i + j], y = a[i + j + m];
                if (!rev) {
                    a[i + j] = (x + y) % P;
                    a[i + j + m] = (x - y + P) % P;
                } else {
                    a[i + j] = 1LL * (x + y) * inv2 % P;
                    a[i + j + m] = 1LL * (x - y + P) * inv2 % P;
                }
            }
        }
    }
    std::vector<int> Or(std::vector<int> a1, std::vector<int> a2) {
        int n = std::max(a1.size(), a2.size()), N = extend(n);
        a1.resize(N), FWTor(a1, false);
        a2.resize(N), FWTor(a2, false);
        std::vector<int> A(N);
        for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
        FWTor(A, true);
        return A;
    }
    std::vector<int> And(std::vector<int> a1, std::vector<int> a2) {
        int n = std::max(a1.size(), a2.size()), N = extend(n);
        a1.resize(N), FWTand(a1, false);
        a2.resize(N), FWTand(a2, false);
        std::vector<int> A(N);
        for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
        FWTand(A, true);
        return A;
    }
    std::vector<int> Xor(std::vector<int> a1, std::vector<int> a2) {
        int n = std::max(a1.size(), a2.size()), N = extend(n);
        a1.resize(N), FWTxor(a1, false);
        a2.resize(N), FWTxor(a2, false);
        std::vector<int> A(N);
        for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
        FWTxor(A, true);
        return A;
    }
} fwt;

int main() {
    int n;
    scanf("%d", &n);
    std::vector<int> a1(n), a2(n);
    for (int i = 0; i < n; i++) scanf("%d", &a1[i]);
    for (int i = 0; i < n; i++) scanf("%d", &a2[i]);
    std::vector<int> A;
    A = fwt.Or(a1, a2);
    for (int i = 0; i < n; i++) {
        printf("%d%c", A[i], " \n"[i == n - 1]);
    }
    A = fwt.And(a1, a2);
    for (int i = 0; i < n; i++) {
        printf("%d%c", A[i], " \n"[i == n - 1]);
    }
    A = fwt.Xor(a1, a2);
    for (int i = 0; i < n; i++) {
        printf("%d%c", A[i], " \n"[i == n - 1]);
    }
    return 0;
}

吐槽

为什么网络上的 $\text{FWT}$ 文章里证明这么简略啊?害得我花了一个上午才证明完,因此本文可能是证明最详细的一篇了吧!


习题

发表评论