数学小记 #3：从 CF1103E 浅谈异或卷积

· · 算法·理论

\gdef \xor {\operatorname{xor}} \gdef \and {\operatorname{and}} \gdef \or {\operatorname{or}} \gdef \popcnt {\operatorname{popcount}}

我们先简要概括一下 FWT。

FWT 是用来解决 XOR 卷积的工具：

f(i)=\sum_{j \xor k = i} g(j)h(k)

构造是记 f 变换后的序列 \hat f 满足

\hat f(i)=\sum_{j} (-1)^{\popcnt(i \and j)}

然后我们就有

\hat f(i)=\hat g(i)\cdot \hat h(i)

逆变换后即得 f。如果我们能在较快的时间内做到变换，那么就可以解决 XOR 卷积的问题。

我们可以平凡地做到 \Theta(n\cdot 2^n)，从而 XOR 卷积的复杂度与之相同。

以上是一般的介绍 FWT 的文章内都会有的内容。下面我们从另一种角度来理解（和证明）这么做是对的。

我们将长度为 2^n 的序列视为一个 n 元，每元的指数都 \in \{0,1\} 的多项式的系数。

例如，f=[1,1,4,5]，那么对应的多项式就是 F(x_1,x_2)=1+x_1+4x_2+5x_1x_2。

我们断言：FWT 的过程实际上就是对这个 n 元多项式，求出它的 \left|\{\omega_2^0,\omega_2^1\}^n\right|=2^n 个点值（意思是，代入 x_1=a_1,x_2=a_2,\ldots,x_n=a_n，这里 a_i\in \{\omega_2^0,\omega_2^1\}）。

因为写 \omega_2 太麻烦了，所以下文统一将 \omega_2 用 -1 代替。

举个具体的例子，f=[1,1,4,5] 变换后是 \hat f=[1+1+4+5,1-1+4-5,1+1-4-5,1-1-4+5]=[11,-1,-7,1]。对应地，\hat f=[F(1,1),F(-1,1),F(1,-1),F(-1,-1)]。这与我们刚才的分析是一致的。（而且可以注意到，如果令 1\to 0，-1\to 1，那么 \hat f\to [\overline{00}_2,\overline{01}_2,\overline{10}_2,\overline{11}_2]，这与二进制表示是一致的。）

for (int l=1; l<n; l<<=1)
  for (int i=0; i<n; i+=l<<1)
      for (int j=i; j<i+l; ++j) {
          auto g=f[j], h=f[j+l];
          f[j]=(g+h)*sgn;
          f[j+l]=(g-h)*sgn;
      }

既可以把这段代码理解为按照最高位分治求解，也可以将这段代码理解为对每一维做长度为 2 的 DFT。这就说明了我们刚才的结论是正确的。

那么，用这个做 XOR 卷积的正确性就是不言自明的了：XOR 卷积可以视为对每一维做长度为 2 的循环卷积，而 DFT 自然就给出了循环卷积。（至于为什么 DFT 是循环卷积，直接考虑单位根的性质即可。）

利用形式幂级数的语言，我们可以叙述为：

F(x_1,\ldots,x_n)=G(x_1,\ldots,x_n)H(x_1,\ldots,x_n) \bmod (x_1^2-1)\bmod (x_2^2-1)\cdots \bmod (x_n^2-1)

DFT 是线性变换，从而我们的 FWT 也自然是线性变换。

有时候 n 很大，但是形式比较好看。我们不能接受 \Theta(n\cdot 2^n) 的复杂度，但是可以通过好看的形式，结合 FWT 变换的两个意义来求解。

例如，超立方体就是要求我们求出

[x_1x_2\ldots x_l] (x_1+x_2+\cdots+x_n)^m \bmod (x_1^2-1)\bmod (x_2^2-1)\cdots \bmod (x_n^2-1)

这里 n\le 2^{21}，但是结合上述性质我们可以做到 \Theta(n\log n)。由于形式过于好看，存在利用整式递推做到接近线性的方法。

注记：我们可以将变换用矩阵描述，对于 XOR 卷积自然就是二阶 Vardermonde 矩阵。当然有时候也需要自己构造矩阵来解题，比如 3^N Minesweeper 这题。

既然我们可以做二进制异或卷积，那么当然也应该可以做 k 进制 FWT（对应的是 k 进制不进位加法）！如果题目允许使用浮点数的话，直接用浮点数做就可以了。也就是 Set。

由于 \mathbb{C} 下的单位根有着很好的性质，这导致问题很简单。所以接下来我们要在不那么平凡的代数结构上做 k 进制 FWT。

以算力训练为例，这题要求我们在 \mathbb F_{p}（p=998\, 244\, 353）下做 k\in \{5,6\} 进制的 FWT。

然而 \omega_5 和 \omega_6 在模 p 意义下均不存在，事情就变得麻烦了起来。下文为了行文方便令 \omega 表示 \omega_k。

考虑到最后答案都是整数，一个常见的处理方法就是扩域——构造一个新的域 \mathbb F_p[\omega]，满足 1 和 \omega 都在域中（等价的表述：域中的元素为 \{\sum_{0\le i\lt k} c_i\omega^i : c_i\in \mathbb F_p\}）。元素的乘法显然是一个长度为 k 的循环卷积（我们这里已经可以将每个元素视为一个占位多项式），这里 k 很小可以暴力做。然后就做完了...吗？

第一个问题是：每次乘法的复杂度是 \Theta(k^2) 的。FWT 本身的复杂度为 m\cdot k^m，这部分就是 \Theta(nm\cdot k^{m+2})，无法通过。

这题也是所谓「性质很好」的问题：多项式 F(x_1,x_2,\cdots,x_m) 中要么有两项为 1，要么是一个常数 2。是常数 2 的情况是平凡的；否则答案肯定是 1+\omega^i，这里 i\in [0,k)。这两种情况都可以被统一为 1+\omega^i。

我们将这 n 个 FWT 后的序列点乘起来。对于 k^m 个位置，每个位置都可以被表示为 \displaystyle\prod_{0\le i\lt k}(1+\omega^i)^{c_i}，这里显然有 \displaystyle \sum_{0\le i\lt k} c_i=n。我们只需要把每个位置的 [c_i] 序列求出来，最后再逆变换回去，就可以完成这题了。

如何求 [c_i]？考虑一个这样的事情：将多项式 F(x_1,\ldots,x_m)=x_{a_1}x_{a_2}\ldots x_{a_p}（1\le a_1\lt a_2\lt \cdots \lt a_p\le m）做一下 FWT 会发生什么。

我们会得到，FWT 后，每个位置都是 \omega^i，这里 i 具体是多少是好算的。我们将 n 个这样的多项式 FWT 后加起来就可以得到每个位置的 [c_i]；根据线性性，我们也可以先把所有位置都加起来再 FWT，这样复杂度就可接受了。

从而，我们将复杂度优化到了 \Theta(mk^{m+2})。

前面我们提到：只需要再逆变换回来就做完了。逆变换之后的常数项真的是真实答案吗？

考虑到，x^k-1 不是素多项式，从而多项式环 \mathbb F_p[X] / (x^k-1) 不是整环。这意味着一个数的表示形式并不是唯一的。怎么办/ll

复读 EI 老师的话：我们知道分圆多项式 \Phi_k(x) 是素多项式，且 \Phi_k(x)\mid x^k-1，那么我们将最后的结果对 \Phi_k(x) 取模。模素多项式是一个整环，而有限整环即为域，这样最后的常数项一定为答案。

概括一下跟鱼鱼的讨论：从线性代数的角度来理解，(\omega_k^0,\omega_k^1,\ldots,\omega_k^{k-1}) 并不是一组基，因为这组向量线性相关。从而方程可以有多解。

我们对 \Phi_k(x) 取模后，相当于：用这组基中的元素替换了方程中的各个元素，使得最终方程的解唯一。以 k=6 举例，一组基是 1,\omega_6。

感谢鱼鱼的帮助/qq

从而，我们已经完成了 \mathbb F_p 的情况。

现在我们已经有了充足的准备来看一下 CF1103E 了。

现在唯一的问题就是无法除以 10^5=2^55^5。5^5 不用管，对于 2^5，不妨干脆直接在模 2^{64} 意义下计算，最后再模 2^{58}，不难证明这是对的。

从而，我们解决了 CF1103E。

感谢 NaCly_Fish 姐姐的指教，感谢可爱的小圆的陪伴。