阅读理解之【模数未知FWT】

· · 算法·理论

_Kenma_问我的 XOR 卷积人生的题解是什么意思。作为 Yau 的忠实粉丝，我对于 Yau 落选校花一事耿耿于怀，遂严肃阅读理解上述博客，以表忠心。

回顾 xor FWT 的做法

事实上我记得我写的 FWT 好像要两次变换啊，这人把正变换和逆变换放到一次递归进行了？下面复述这个人所谓的经典款 FWT 的一种理解方式。

假如我们有 A=\{a_0,a_1,\dots,a_{2^n-1}\}，B=\{b_0,b_1,\dots,b_{2^n-1}\}，欲计算 C=\{c_0,c_1,\dots,c_{2^n-1}\}，其中 c_i=\sum_{j\oplus k=i}a_jb_k。为了方便，这种异或卷积下面记作 C=A\times B，简写为 C=AB。

令 A_0=\{a_0,a_1,\dots,a_{2^{n-1}-1}\} 为 A 的前半部分，A_1=\{a_{2^{n-1}},a_{2^{n-1}+1},\dots,a_{2^n-1}\} 为 A 的后半部分，类似定义 B_0,B_1,C_0,C_1。根据异或卷积的定义，我们知道 C_0=A_0\times B_0+A_1\times B_1,C_1=A_0\times B_1+A_1\times B_0（这里 + 表示两个长度相同的数组对应位置分别相加）。

如何快速计算 C_0,C_1 呢？FWT 通过引入形式变元 x 来实现。

令 \mathcal A=A_0+xA_1=\{a_0+a_{2^{n-1}}x,a_1+a_{2^{n-1}+1}x,\dots,a_{2^{n-1}-1}+a_{2^n-1}x\},\mathcal B=B_0+xB_1=\{b_0+b_{2^{n-1}}x,b_1+b_{2^{n-1}+1}x,\dots,b_{2^{n-1}-1}+b_{2^n-1}x\}，也就是通过 x 把 A_0,A_1 压缩一下，叠在同一个较短的数组上，我们计算 \mathcal A\times \mathcal B，得到一个长度为 2^{n-1} 的数组，数组的每个元素都是 x 的二次多项式。

\mathcal C &=\mathcal A\times\mathcal B=A_0B_0+(A_0B_1+A_1B_0)x+A_1B_1x^2 \\ &=\{f_0x^2+g_0x+h_0,f_1x^2+g_1x+h_1,\dots,f_{2^{n-1}-1}x^2+g_{2^{n-1}-1}x+h_{2^{n-1}-1}\} \end{aligned}

相比之下（其中 [x^k]\mathcal C 表示一个数组，数组元素是 \mathcal C 中各元素的 x^k 项系数）：

C_0=A_0B_0+A_1B_1=[x^0]\mathcal C+[x^2]\mathcal C,C_1=A_0B_1+A_1B_0=[x^1]\mathcal C

诶，我们发现想得到 C_0，要把 \mathcal C 的常数项和二次项合并，那怎么合并呢？其实我们只需要把 \mathcal C 的每一项对 F(x)=x^2-1 取模就好了（多项式带余除法，有 ax^2+bx+c\mod F(x)=bx+(a+c)）。

取模后，

\mathcal C' &=(A_0B_0+A_1B_1)+(A_0B_1+A_1B_0)x \\ &=\{g_0x+f_0+h_0,g_1x+f_1+h_1,\dots,g_{2^{n-1}-1}x+f_{2^{n-1}-1}+h_{2^{n-1}-1}\} \end{aligned}

也即

C_0=[x^0]\mathcal C',C_1=[x^1]\mathcal C'

分别提取 \mathcal C' 的常数项和一次项系数，就可以得到 C_0 和 C_1。提取方法就是拉插，说人话就是两点确定一条直线。

传统 xor FWT 的代入法

我们分别令 x=x_1,x_2 递归计算得到（方法见下） \mathcal C'(x_1),\mathcal C'(x_2)（由于给 x 代了具体值，这两个数组的元素都是数，而不是一次多项式），根据小学二年级学过的两点确定一条直线，我们有

\begin{cases} \mathcal C'(x_1)=C_0+x_1C_1 \\ \mathcal C'(x_2)=C_0+x_2C_1 \end{cases} \Rightarrow \begin{cases} C_0=\frac{x_1\mathcal C'(x_2)-x_2\mathcal C'(x_1)}{x_1-x_2} \\ C_1=\frac{\mathcal C'(x_1)-\mathcal C'(x_2)}{x_1-x_2} \end{cases}

这样就解出了 C_0,C_1。注意这个过程要求 x_1-x_2 可逆，在实数域上就是 x_1\ne x_2。

你也许注意到了，我们递归下去计算的其实应该是 \mathcal C(x_1),\mathcal C(x_2)，我们如何得到本节开始加粗处的 \mathcal C'(x_1),\mathcal C'(x_2) 呢？

传统 FWT 是通过代入特殊的 x_1,x_2 实现的。具体地，我们令 x_1,x_2 是 F(x) 的两根（即\pm 1），那么对于 \mathcal C(x_1) 中的某个元素有

\mathcal C(x_1)_i=f_ix_1^2+g_ix_1+h_i=f_iF(x_1)+g_ix_1+f_i+h_i=g_ix_1+f_i+h_i=\mathcal C'(x_1)_i

也就是说通过代入特殊值，我们隐式地实现了取模，这样我们递归得到的 \mathcal C(x_1),\mathcal C(x_2) 其实就是 \mathcal C'(x_1),\mathcal C'(x_2)。

原文指出，其他类型的 FWT 只不过是更换了 F(x)，例如在 \text{and} 卷积中我们希望把 x^2 的系数合并到 x 处，那么 F(x) 就得是 x^2-x。

文章所述 FWT 做法

传统 FWT 有时会遇到一个尴尬的情况，那就是 F(x) 在数域（严格来说不算数域，因为可以没有交换律，但暂且这么叫）里两根之差不可逆（例如在模 2 的剩余系下，x^2-1 的根是 x_1=x_2=1 而 x_2-x_1=0 不可逆），那么插值法就失效了。

怎么办呢？那就别代入 x_2 了呗。我们引入形式记号 y（原文叫 \varepsilon）用来代替性质不好的 x_2。记号与之前相同，只不过数域由原数域扩充为数域上关于 y 的多项式。

我们分别令 x=x_1,y 递归计算得到 \mathcal C(x_1),\mathcal C(y)（由于给 x 代了具体值，这两个数组的元素都是关于 y 的多项式，而不是关于 x,y 的多项式）。

原来，我们有 \mathcal C(x_1)=\mathcal C'(x_1),\mathcal C(x_2)=\mathcal C'(x_2)。现在，我们仍有 \mathcal C(x_1)=\mathcal C'(x_1)，但 F(y)\ne 0 从而 \mathcal C(y)\ne\mathcal C'(y)。

怎么办呢？我们令 y\to x_2，这样我们仍然可以认为 \mathcal C(y)=\mathcal C'(y)。于是照常解出 C_0,C_1（其元素都是关于 y 的多项式）即可。注意现在解 C_0,C_1 时需要让某多项式除以 (x_1-y)，我断言必然能整除，因若不然令 y\to x_1 则结果 \to\infty，这不可能。但其实我并未严谨证明，有人要具体实现的时候可以告诉我。

最后得到的结果自然也是关于 y 的多项式，答案就是令 y\to x_2 时这些元素的值，也即这些多项式在 y=x_2 处的点值。

这样我们就把奇怪数域上的 FWT 换成了奇怪数域上多项式的 FWT，原文指出，这其实也是一类经典 FWT。例如子集卷积就是令 F(x)=x^2，此时两根重叠，子集卷积通过引入一个形式变元来实现，这就是这里的 y。

由于现在参与计算的每个元素都是长度为 O(n) 的多项式了，乘法得换成多项式的卷积，时间复杂度由原版的 O(n2^n) 增至 O(nM(n)2^n)，其中 M(n) 是多项式卷积的时间复杂度，暴力实现就是 M(n)=O(n^2)。

更高进制的推广与 FFT

回顾本文做法，容易发现可以推广到更高进制，例如三进制不进位加法卷积：

\begin{aligned} \mathcal A&=A_0+xA_1+x^2A_2 \\ \mathcal B&=B_0+xB_1+x^2B_2 \\ \mathcal C&=\mathcal A\times\mathcal B \\ &=A_0B_0+(A_0B_1+A_1B_0)x+(A_0B_2+A_1B_1+A_2B_0)x^2+(A_1B_2+A_2B_1)x^3+A_2B_2x^4 \end{aligned}

把 \mathcal C 对 x^3-1 取模，提取常数项、一次项、二次项系数就可以分别得到 C_0,C_1,C_2。仍然是将 F(x) 的根 x_1,x_2,x_3 代入并递归计算，再使用插值法解出 C_0,C_1,C_2。

在一般的情况下，F(x) 的根两两之差都可逆，那么就不需要像之前一样扩域，只是进行元素的计算。对于 k 进制，长为 m 的数组来说，时间复杂度就是 O(km\log_km)，带有 k 是因为每层要进行 O(\frac mk) 次拉插。

诶，注意到取 k=m，就是 m 进制不进位加法，那就是循环卷积，取 k\ge2m-1，那就是和卷积，于是我们得到了一个 O(m^2) 计算和卷积的算法。这个算法的过程就是将 A,B 视作多项式，代入 F(x)=x^k-1 的 k 个根再插值。

孩子们，想我了吗？没错！此时 F(x) 的 k 个根正是所有的 k 次单位根，所以，此时 FWT 和 FFT 在做相同的事情，只是 FFT 加速了代入和插值的过程。至此某种意义上我们得到了 FWT 和 FFT 之间的联系。

在其他运算上的进一步推广？

再看 FWT 计算的东西，c_i=\sum_{j\otimes k=i}a_jb_k，其中 \otimes 是某种对于每一 k 进制位独立的运算符。

例如 \otimes 是 \text{xor} 时，对每一位有 0\otimes0=0,0\otimes1=1,1\otimes0=1,1\otimes1=1。这对应多项式 F(x)=x^2-1。

又如 \otimes 是子集卷积时，对每一位有 0\otimes0=0,0\otimes1=1,1\otimes0=1，而 1\otimes1 的运算则是不允许的。这对应多项式 F(x)=x^2。

再如 \otimes 是三进制不进位加法时，对每一位有 0\otimes0=0,0\otimes1=1,0\otimes2=2,1\otimes0=1,1\otimes1=2,1\otimes2=0,2\otimes0=2,2\otimes1=0,2\otimes2=1。这对应多项式 F(x)=x^3-1。

我们据此可以定义一些其他运算，例如让 \otimes 在奇数位是 \text{xor}，在偶数位是 \text{and}，这样我们只需要在递归时每层对不同 F(x) 取模（即代入不同的根递归）即可。

也可以定义一些更加奇怪的运算，例如定义三进制下的运算：0\otimes0=0,0\otimes1=1,0\otimes2=1,1\otimes0=1,1\otimes1=2,1\otimes2=0,2\otimes0=2,2\otimes1=0,2\otimes2=2。这里的数是我瞎填的（具体来说是圆周率前九位模 3）。

遗憾的是，我未能找出表示上述运算的多项式，看来这种办法也不是万能的，也可能是我太菜了没注意到。这个时候把这个问题丢给读者就好了。

另外，目前大部分博客用线性变换及其逆来表示 FWT 和 IFWT，可以解决 k 进制 \max 卷积，但目前我没有想到如何用本方法实现更高进制的 \max 卷积。等我学了特征多项式再回来看看这两者是否有关系吧。

总结

本文基于对开头那篇博客的阅读理解，但事实上，原博客并未使用“取模”的字眼，因此我不能保证我的理解和博客作者相同。本文所述的内容足以实现那篇博客所述的各种 FWT 并可推广到高进制，但取模这种手法在处理高进制的其他卷积时似乎有些乏力。

在高进制下，或许可以通过构造更复杂的 \mathcal C 或带有多个高次项的模多项式来完成 FWT，但限于我的水平未能实现。希望有大手子能教教我。