FWT 入门

First Post:

Last Update:

Word Count:
673

Read Time:
3 min

Page View: loading...

FWT 用于解决位运算卷积，即形如

的递推。这里 是二元位运算的某一种。

其核心思想与 FFT 类似，希望找到一个变换 用于将卷积转化为点积。

通常要求 FWT 的数组长度为 的整数次幂，可以使用 n & (n - 1) 检查，示例代码中没有检查。

OR

令 ，则容易验证

满足要求。

考虑将 递推出来，令 表示 的前半段， 表示 的后半段，显然有

因此可以在 的复杂度内完成递推。

反演形式也是显然的

给出一个实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <bool inv = false, uint64_t mod = 0> void FWT_or(vector<uint64_t> &arr) {
  size_t n = arr.size();
  for (size_t k = 1; k < n; k <<= 1) {
    for (size_t i = 0; i < n; i += k << 1) {
      for (size_t j = 0; j < k; ++j) {
        if constexpr (!inv)
          arr[i + j + k] += arr[i + j];
        else
          arr[i + j + k] += mod - arr[i + j];
        if constexpr (mod != 0)
          arr[i + j + k] %= mod;
      }
    }
  }
}

AND

类比 的构造方式，令 ，这里不对正确性进行验证。

容易得到递推

也可以从 和 的对称性理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <bool inv = false, uint64_t mod = 0> void FWT_and(vector<uint64_t> &arr) {
  size_t n = arr.size();
  for (size_t k = 1; k < n; k <<= 1) {
    for (size_t i = 0; i < n; i += k << 1) {
      for (size_t j = 0; j < k; ++j) {
        if constexpr (!inv)
          arr[i + j] += arr[i + j + k];
        else
          arr[i + j] += mod - arr[i + j + k];
        if constexpr (mod != 0)
          arr[i + j] %= mod;
      }
    }
  }
}

XOR

构造不易。

令 表示 ，则 。

令 ，下证构造的正确性：

容易得到递推

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
template <uint64_t mod> constexpr uint64_t inverse(uint64_t x) {
  uint64_t res = 1, b = mod - 2;
  for (x %= mod; b; b >>= 1, x = x * x % mod)
    if (b & 1)
      res = res * x % mod;
  return res;
}

template <bool inv = false, uint64_t mod = 0> void FWT_xor(vector<uint64_t> &arr) {
  size_t n = arr.size();
  for (size_t k = 1; k < n; k <<= 1) {
    for (size_t i = 0; i < n; i += k << 1) {
      for (size_t j = 0; j < k; ++j) {
        uint64_t u = arr[i + j], v = arr[i + j + k];
        arr[i + j] = u + v;
        arr[i + j + k] = mod + u - v;
        if constexpr (mod != 0)
          arr[i + j] %= mod, arr[i + j + k] %= mod;
        if constexpr (inv) {
          if constexpr (mod == 0)
            arr[i + j] >>= 1, arr[i + j + k] >>= 1;
          else {
            static constexpr uint64_t inv2 = inverse<mod>(2);
            arr[i + j] = arr[i + j] * inv2 % mod;
            arr[i + j + k] = arr[i + j + k] * inv2 % mod;
          }
        }
      }
    }
  }
}

这里假定模数 mod 总是质数，如果不能保证，需要修改 inv 函数。

进一步抽象

设 为 对 的贡献系数，即

因为

可以证明

同时， 函数可以按位处理，因此可以直接写出递推

记变换矩阵为

由于需要逆变换，要求矩阵 可逆，即要求矩阵 任意一行或任意一列不能全为零。

OR

可以构造

同样可以

其中

AND

XOR

FWT 存在 维形式，这里不展开了。

≡