「Note」FWT

emm…

$\mathtt{Problem}$

$$ c_i = \sum_{i = j \otimes k} a_j b_k $$

$\mathtt{Solutions}$

$\mathtt{or \mid}$

$$ \begin{aligned} c_i &= \sum_{i = j \mid k} a_j b_k \\ \because j \mid i = i, k \mid i &= i \rightarrow (j \mid k) \mid i = i \\ fwt(a)_i &= \sum_{j \mid i = i} a_j \\ \Rightarrow fwt(a) \times fwt(b) &= (\sum_{j \mid i = i} a_j) (\sum_{k \mid i = i} b_k) \\ &=\sum_{j \mid i = i}\sum_{k \mid i = i} a_j b_k \\ &=\sum_{(j \mid k) \mid i = i} a_jb_k \\ &=fwt(c) \end{aligned} $$

目标变成求 $fwt(a)_i = \sum_{j \mid i}a_j$ 。

两个性质，二进制下每 $2^i$ 的前 $i$ 位相同，$x \equiv x+2^i \mod{2^{i}}$ ，二进制下相差 $2^i$ 的两个数的第 $i$ 位不同， $\lfloor \frac{x + 2^i}{2^i} \equiv \frac{x \oplus 2^i}{2^i} \rfloor \mod{2}$ 。

考虑分治，按下标中最高位为 $0$ 和 $1$ 分成两段，记为 $a_0, a_1$ ，此时假设已知了前 $i - 1$ 位的答案， $fwt(a) = (fwt(a_0), fwt(a_0) + fwt(a_1))$ 。
因为对于前 $2^{i - 1}$ 个数，最高位为 $0$ ，子集不会有最高位为 $1$ 的数，所以答案和后面无关，对于后面的 $2^{i - 1}$ 个数，在任意的 $x$ 的情况下，最高位为 $1$ ,是 $x-2^i$ 子集的也一定是 $x$ 的子集，所以要加上 $x-2^i$ 的答案。对于逆操作，很显然 $a = (a_0, a_1 - a_0)$

void fwtor(LL* f, int n, int type = 1) {
  for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
    for (int i = 0; i < n; i += o)
      for (int j = 0; j < k; j++)
        f[i + j + k] = (f[i + j] * type + f[i + j + k]) % Mod;
}

$\mathtt{and \ \&}$

与 $or \mid$ 同理（子集改成超集）。
$$ fwt(a)_i = \sum_{j \& i}a_j \\ fwt(a) = fwt(a_0) + fwt(a_1), fwt(a_1) \\ a = (a_0 - a_1, a_1) \\ $$

void fwtand(LL* f, int n, int type = 1) {
  for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
    for (int i = 0; i < n; i += o)
      for (int j = 0; j < k; j++)
        f[i + j] = (f[i + j + k] * type + f[i + j]) % Mod;
}

$\mathtt{xor \ \oplus}$

推导过程比较复杂，略。

$$ fwt(a) = fwt(a_0) + fwt(a_1), fwt(a_0) - fwt(a_1) \\ a = \frac{a_0 + a_1}{2} + \frac{a_0 - a_1}{2} $$

void fwtxor(LL* f, int n, int type = 1) {
  for (int w = 2, k = 1; w <= n; w <<= 1, k <<= 1)
    for (int i = 0; i < n; i += w)
      for (int j = 0; j < k; j++) {
        f[i + j] = (f[i + j] + f[i + j + k]) % Mod,
        f[i + j + k] = (f[i + j] - f[i + j + k] - f[i + j + k] + Mod + Mod) % Mod,
        f[i + j] = (f[i + j] * type + Mod) % Mod, f[i + j + k] = (f[i + j + k] * type + Mod) % Mod;
      }
}