「学习总结」基本卷积算法

📅 Last Updated: 2021-01-17
📊 Word Count: 2236
⏱️ Estimated Reading Time: 15 minutes
📄 PDF 📝 Source

「做多项式题就像嗑药，出多项式题就像贩毒。」 —— 某福建知名OI选手

学了学红日bn一年前玩剩下的东西。

倒是扩展了 FWT 的一种思路吧。

基本卷积算法

加法卷积

用于解决形如以下问题： 给出两个序列 A,BA, B。求两个序列的卷积序列 CC，其中序列 CC 的定义如下

Ck=∑i+j=kAi×Bj(1) C_k = \sum_{i+j=k}A_i \times B_j \qquad{(1)}

序列可以看作是函数的系数表示法，所以我们可以定义函数 $F(x) = _{i } A_i x^i $ 和函数 G(x)=∑i≥0BixiG(x)= \sum_{i \ge 0} B_i x^i 分别对应序列 A,BA, B 的两个函数。

类似的，还可以定义序列 CC 对应函数 T(x)=∑i≥0CixiT(x) = \sum_{i \ge 0} C_i x^i。

注意到这种定义就是将序列的第 ii 个数当作多项式函数的第 ii 次系数。

注意到

T(x)=F(x)×G(x)(2) T(x)=F(x) \times G(x) \qquad{(2)}

这个是后面卷积方法的核心工作原理。本质上是 建立了 序列运算 与其对应 函数（多项式）运算 的一种联系。

注意到 (eq.~eq. 2) 也可以理解为对于任意常数 aa，总有 T(a)=F(a)×G(a)T(a)=F(a) \times G(a)。

也就是说，如果我们知道了 G(x)G(x) 和 F(x)F(x) 在 aa 处的函数值，那么他们相乘就能够得到 T(x)T(x) 在 aa 处的函数值。

考虑如果存在一种变换，能够快速计算 G(x)G(x) 和 F(x)F(x) 在某些特定自变量 a1,a2,a3,⋯ak\\{a_1, a_2, a_3,\cdots a_k\\} 处的函数值，那么就能快速算出 T(x)T(x) 在这些自变量处的函数值。

如果存在某种逆变换，能够快速将函数在某些自变量处的函数值转换成每一次项的系数，那么就能够求出 T(x)T(x) 的系数（即序列 CC）了。

总的来说，希望存在一种序列上变换 FFT⁡(T)\operatorname{FFT}(T)，使得 FFT⁡(C)=FFT⁡(A×B)=FFT⁡(A)⋅FFT⁡(B) \operatorname{FFT}(C) = \operatorname{FFT}(A \times B) = \operatorname{FFT}(A) \cdot \operatorname{FFT}(B) 其中 ×\times 表示序列加法卷积 (eq.~eq. 1)，⋅\cdot 表示对应位置相乘。

并且这种变换存在逆变换，能够将 FFT⁡(C)\operatorname{FFT}(C) 还原为 CC 。

通过上述描述可以发现，对于一个函数 G(x)G(x) 来说，其表示成序列的方式有两种：一种是构造序列，使得序列第 ii 位为多项式函数 G(x)G(x) 的第 ii 次项系数。另一种是指定一系列取值a1,a2,a3,⋯ak\\{a_1, a_2, a_3,\cdots a_k\\} ，分别带入函数中，得到的函数值依次排开，成为一个序列。我们称前者为函数 G(x)G(x) 的系数表示法，称后者为其点值表示法。而我们所希望的变换就是能够实现函数的系数表示法 与 点值表示法 相互转化。

因为 两函数相乘时，其对应的系数表示法的序列就是在做卷积操作，对应了我们希望的运算，但是这个并不能快速计算。而两函数相乘，对于点值表示法，就仅仅是对应位置相乘，这个可以快速计算。所以可以考虑如果能够快速实现 函数的系数表示法 与 点值表示法 相互转化。就能够解决上述问题。可以先转化为点值表示法，然后对点相乘后，再转换为系数表示法，就相当于对序列做卷积。

快速傅里叶变换（FFT）

快速傅里叶变换 就是一种满足上述条件的变换。她可以使得函数在系数表示法与点值表示法之间转换。 时间复杂度为 O(nlog⁡n)\mathcal{O}(n \log n)。

考虑上述过程中，并没有限制点值表示法中的点值应该取哪些值，所以可以考虑取一些有丰富性质的数字，利用这些性质加速运算。

对于 FFT 我们取 n次单位根 来加速运算。nn 为待变换序列长度。

单位根

n 次单位根记作 ωn\omega_n。其定义为 ωn=cos⁡2πn+isin⁡2πn\omega_n = \cos{\frac{2\pi}{n}} + \mathrm{i}\sin{\frac{2\pi}{n}}，这是一个虚数。虚数可以通过向量来表示，而 ωn\omega_n 就可以考虑为一个模长为 11 ，与 xx 轴夹角为 2πn\frac{2\pi}{n} 的向量。易知， ωnk=cos⁡2πkn+isin⁡2πkn\omega_n^k=\cos{\frac{2\pi k}{n}} + \mathrm{i}\sin{\frac{2\pi k}{n}}。

他有如下性质

  • ωnk=ω2n2k\omega_n^k=\omega_{2n}^{2k}
  • ωnk+n2=−ωnk\omega_n^{k + \frac{n}{2}}=-\omega_{n}^{k}
  • ωn0=ωnn=1\omega_n^0=\omega_n^n=1

这些性质都可以通过其定义得知。

考虑将 ωn0,ωn1,ωn2,⋯ ,ωnn−1\omega_n^0, \omega_n^1, \omega_n^2, \cdots, \omega_n^{n-1} 带入函数，得到点值即可。

蝴蝶操作

分别抽取函数 F(x)F(x) 的奇、偶次项系数构成两个新函数 G(x),H(x)G(x), H(x)。 易知: F(x)=G(x2)+xH(x2) F(x) = G(x^2) + xH(x^2) 即 F(ωnk)=G(ωn/2k)+ωnkH(ωn/2k) F(\omega_n^k) = G(\omega_{n/2}^k) + \omega_n^k H(\omega_{n/2}^k) F(ωnk+n/2)=G(ωn/2k)−ωnkH(ωn/2k) F(\omega_n^{k + n/2}) = G(\omega_{n/2}^k) - \omega_n^k H(\omega_{n/2}^k)

划分了子问题，分治即可。这里必须保证 n=2kn = 2^k，k∈Nk \in \mathbb{N}

逆变换

单位根还有如下性质 ∑i=0n−1(ωnk)i={0k≠0nk=0 \sum_{i=0}^{n-1}\left(\omega_n^k\right)^i= \begin{cases} 0& {k \not= 0}\\\\ n& {k = 0} \end{cases} 第二种情况显然，第一种情况根据等比数列求和公式可以得证。

根据上述性质，我们只需要取单位根为之前的倒数，然后跑一遍 FFT⁡\operatorname{FFT} 对结果除以 nn 即可。 不会推QAQ。

快速数论变换（NTT）

FFT 需要实数运算，对精度要求较高。且无法解决常见的取模要求。

注意到 FFTFFT 中所依赖的是一个复平面上的单位圆，其实剩余系本身就可以看作一个环。可以考虑在剩余系下寻找具有与单位根性质类似的数字。

设质数 PP 的原根为 gg。那么 ∀k∈[0,φ(P)−1],k∈N,gk\forall k \in [0, \varphi(P) - 1],k \in \mathbb{N},g^{k}，可以表示 PP 的剩余系中除 00 以外的任何数字，显然可表示的数字有 P−1P-1 个。

以下关于剩余系类比复平面单位圆的描述由笔者口胡，不保证语言严谨。

在 FFT⁡\operatorname{FFT} 中取单位根的方式本质上实在均分复平面上单位圆。而 NTT⁡\operatorname{NTT} 中，如果将 gkg^k 依次排成一个环，即剩余系，我们一样可以通过均分这个环，来取剩余系下的“单位根”，来获得和之前复平面单位根 类似性质的一些数。显然，这里需要保证在我们均分单位圆的过程中，每个值都能取到，也就是 n∣φ(P)n | \varphi(P)，即 n∣(P−1)n | (P-1)。

所以这里的剩余系取值有一定要求，变换中所要求的 nn 都是 22 的次幂，需要保证 P−1P-1 中 22 的幂次应该足够大。（文末附质数取值表）

设 P−1=q×nP-1 = q\times n。

考虑将 gn=gqg_n=g^q 当作 ωn\omega_n 即可，根据上面的描述，ωn\omega_n 所具有的性质，gng_{n} 显然成立。这里的 qq 可以想成等分环时的单位角度。

关于 蝴蝶操作 和 逆变换 的手法和 FFT⁡\operatorname{FFT} 是一样的。

位运算卷积

类似地，定义位运算序列卷积。 给出两个序列 A,BA, B。求两个序列的卷积序列 CC，其中序列 CC 的定义如下

Ck=∑i⊕j=kAi×Bj(3) C_k = \sum_{i\oplus j=k}A_i \times B_j \qquad{(3)}

可以仿照上述思路，构造一种作用在序列上的变换 FWT⁡\operatorname{FWT}，使得其满足

FWT⁡(C)=FWT⁡(A⊕B)=FWT⁡(A)⋅FWT⁡(B)(4) \operatorname{FWT}(C) = \operatorname{FWT}(A \oplus B) = \operatorname{FWT}(A) \cdot \operatorname{FWT}(B) \qquad{(4)}

A⊕BA \oplus B 中的 ⊕\oplus 指某种位运算。指下标的运算方式。即 (eq.~eq. 3) 中的 i⊕j=ki\oplus j=k。

快速沃尔什变换（FWT）

考虑分治处理，令 A0A_0 为 AA 的前一半， A1A_1 为 AA 的后一半。可以考虑如果已经求出了 FWT⁡(A0)\operatorname{FWT}(A_0) 和 FWT⁡(A1)\operatorname{FWT}(A_1)，如何求出 FWT⁡(A)\operatorname{FWT}(A)。

顺便定义函数 merge⁡(A,B)\operatorname{merge}(A, B) 表示将序列 A,BA, B 直接前后拼接，返回拼接后的大序列。例如 A=merge⁡(A0,A1)A = \operatorname{merge}(A_0, A_1)。

或运算

考虑如何构造 FWT⁡\operatorname{FWT} 的方式，使得：

FWT⁡(A∣B)=FWT⁡(A)⋅FWT⁡(B)(5) \operatorname{FWT}(A | B) = \operatorname{FWT}(A) \cdot \operatorname{FWT}(B) \qquad{(5)}

对于或运算卷积，直接给出结论。我们定义当前情况下的 FWT⁡\operatorname{FWT} 的运算规则如下。

FWT⁡(A)=merge⁡(FWT⁡(A0),FWT⁡(A0)+FWT⁡(A1))(6) \operatorname{FWT}(A) = \operatorname{merge}(\operatorname{FWT}(A_0), \operatorname{FWT}(A_0) + \operatorname{FWT}(A_1)) \qquad{(6)}

其中 ++ 为序列对应位置相加。

现在证明：已知 (eq.~eq. 6)， (eq.~eq. 5) 成立。

将 FWT⁡\operatorname{FWT} 简记为 F⁡\operatorname{F}，将 merge⁡(A,B)\operatorname{merge}(A, B) 简记为 [A,B][A, B]

首先试图从等式左边开始推导： F⁡(A)⋅F⁡(B)=[F⁡(A0), F⁡(A0)+F⁡(A1)]⋅[F⁡(B0), F⁡(B0)+F⁡(B1)]=[F⁡(A0)⋅F⁡(B0), (F⁡(A0)+F⁡(A1))⋅(F⁡(B0)+F⁡(B1))]=[F⁡(A0)⋅F⁡(B0), F⁡(A0)⋅F⁡(B0)+F⁡(A0)⋅F⁡(B1)+F⁡(A1)⋅F⁡(B0)+F⁡(A1)⋅F⁡(B1)] \begin{split} \operatorname{F}(A) \cdot \operatorname{F}(B) &= \left[ \operatorname{F}(A_0),\ \operatorname{F}(A_0) + \operatorname{F}(A_1) \right] \cdot \left[ \operatorname{F}(B_0),\ \operatorname{F}(B_0) + \operatorname{F}(B_1) \right] \\ &= \left[ \operatorname{F}(A_0) \cdot \operatorname{F}(B_0),\ (\operatorname{F}(A_0) + \operatorname{F}(A_1)) \cdot (\operatorname{F}(B_0) + \operatorname{F}(B_1)) \right] \\ &= \left[ \operatorname{F}(A_0) \cdot \operatorname{F}(B_0),\ \operatorname{F}(A_0)\cdot\operatorname{F}(B_0) + \operatorname{F}(A_0)\cdot\operatorname{F}(B_1) \right. \\ &\quad\left. + \operatorname{F}(A_1)\cdot\operatorname{F}(B_0) + \operatorname{F}(A_1)\cdot\operatorname{F}(B_1) \right] \end{split}

再从等式右边开始推导，先假设当序列长度为 ∣A∣2\frac{|A|}{2} 时，根据 (eq.~eq. 6) 能够使得 (eq.~eq. 5) 成立。 F⁡(A ∣ B)=F⁡([A0∣B0,A0∣B1+A1∣B0+A1∣B1])=[F⁡(A0∣B0), F⁡(A0∣B1)+F⁡(A1∣B0)+F⁡(A1∣B1)+F⁡(A0∣B0)]=[F⁡(A0)⋅F⁡(B0), F⁡(A0)⋅F⁡(B0)+F⁡(A0)⋅F⁡(B1)+F⁡(A1)⋅F⁡(B0)+F⁡(A1)⋅F⁡(B1)] \begin{split} \operatorname{F}(A\ |\ B) &= \operatorname{F}([A_0|B_0, A_0|B_1 + A_1|B_0 + A_1 | B_1]) \\ &= \left[ \operatorname{F}(A_0|B_0),\ \operatorname{F}(A_0|B_1) + \operatorname{F}(A_1|B_0) + \operatorname{F}(A_1 | B_1) + \operatorname{F}(A_0|B_0) \right] \\ &= \left[ \operatorname{F}(A_0) \cdot \operatorname{F}(B_0),\ \operatorname{F}(A_0) \cdot \operatorname{F}(B_0) + \operatorname{F}(A_0) \cdot \operatorname{F}(B_1) + \operatorname{F}(A_1) \cdot \operatorname{F}(B_0) + \operatorname{F}(A_1) \cdot \operatorname{F}(B_1) \right] \end{split}

我们假设结论在 序列长度为 ∣A∣2\frac{|A|}{2} 时 成立，能够推出 序列长度为 ∣A∣|A| 时 成立，就能够推出上述结论在任何情况下均适用（数学归纳法）。

考虑如何构造逆变换 iFWT⁡\operatorname{iFWT} 的运算规则。 相当于每一步都反向操作。

因为： FWT⁡(A)=merge⁡(FWT⁡(A0),FWT⁡(A0)+FWT⁡(A1)) \operatorname{FWT}(A) = \operatorname{merge}(\operatorname{FWT}(A_0), \operatorname{FWT}(A_0) + \operatorname{FWT}(A_1)) 相当于，现在已经得到了 A0′=A0A_0' = A_0 ，A1′=A0+A1​A_1' = A_0 +A_1​ 那么易知： A0=A0′ A_0 = A_0' A1=A1′−A0′ A_1 = A_1' - A_0'

因此，逆变换就是： iFWT⁡(A)=merge⁡(iFWT⁡(A0),iFWT⁡(A1)−iFWT⁡(A0)) \operatorname{iFWT}(A)=\operatorname{merge}(\operatorname{iFWT}(A_0), \operatorname{iFWT}(A_1) - \operatorname{iFWT}(A_0))

需要注意的是： FWT⁡(A)i=∑j⊆iAj \operatorname{FWT}(A)_i = \sum_{j \subseteq i}A_j

与运算

FWT⁡(A)=merge⁡(FWT⁡(A0)+FWT⁡(A1),FWT⁡(A1)) \operatorname{FWT}(A) = \operatorname{merge}(\operatorname{FWT}(A_0) + \operatorname{FWT}(A_1), \operatorname{FWT}(A_1)) iFWT⁡(A)=merge⁡(iFWT⁡(A0)−iFWT⁡(A1),iFWT⁡(A1)) \operatorname{iFWT}(A)=\operatorname{merge}(\operatorname{iFWT}(A_0) - \operatorname{iFWT}(A_1),\operatorname{iFWT}(A_1) )

需要注意的是： FWT⁡(A)i=∑i⊆jAj \operatorname{FWT}(A)_i = \sum_{i \subseteq j}A_j

一般方法

构造的逆运算为解方程。

考虑如何根据一种位运算，求出一种合法的 FWT⁡/iFWT⁡\operatorname{FWT} / \operatorname{iFWT} 构造方式。这里的合法指这种构造方式满足 (eq.~eq. 4)

考虑某种位运算 ⊕\oplus 的 FWT⁡​\operatorname{FWT}​ 应该是什么样子。根据上面的两个例子，可以设出如下式子： F⁡(A)=merge⁡(a⋅F⁡(A0)+b⋅F⁡(A1) ,c⋅F⁡(A0)+d⋅F⁡(A1)) \operatorname{F}(A) = \operatorname{merge}(a \cdot\operatorname{F}(A_0) + b \cdot\operatorname{F}(A_1)\ ,c \cdot\operatorname{F}(A_0) + d \cdot\operatorname{F}(A_1) ) 这里的 a,b,c,da, b, c, d 为常数，“⋅\cdot” 为普通乘法。

为了方便，设 U=F⁡(A0)U=\operatorname{F}(A_0)，V=F⁡(A1)V=\operatorname{F}(A_1)， W=F⁡(B0)W=\operatorname{F}(B_0)，X=F⁡(B1)X=\operatorname{F}(B_1)

则：

F⁡(A)⋅F⁡(B)=[aU+bV,cU+dV]⋅[aW+bX,cW+dX]=[a2UW+2ab(UX+VW)+b2VX,c2UW+2cd(UX+VW)+d2VX  ](7) \begin{split} \operatorname{F}(A)\cdot\operatorname{F}(B)&=[aU+bV, cU+dV]\cdot[aW+bX, cW+dX]\\\\ &=[a^2UW + 2ab(UX + VW)+b^2VX, c^2UW + 2cd(UX + VW)+d^2VX \ \ ] \end{split} \qquad{(7)}

这里以异或为例，因为序列是中间分成两个序列，不妨设序列长度均为 22 的若干次方，那么分开之后，其下标的最高位一定是前一半为 0 后一半为 1，根据异或的运算规则，哪些元素组合起来能够什么样的最高位即可。

假设上式在 序列长度为 ∣A∣2​\frac{|A|}{2}​ 时是成立的。则： F⁡(A⊕B)=F⁡([A0⊕B0+A1⊕B1,A0⊕B1+A1⊕B0])=[aF⁡(A0⊕B0+A1⊕B1)+bF⁡(A0⊕B1+A1⊕B0),cF⁡(A0⊕B0+A1⊕B1)+dF⁡(A0⊕B1+A1⊕B0)]=[aF⁡(A0⊕B0)+aF⁡(A1⊕B1)+bF⁡(A0⊕B1)+bF⁡(A1⊕B0),cF⁡(A0⊕B0)+cF⁡(A1⊕B1)+dF⁡(A0⊕B1)+dF⁡(A1⊕B0)]=[aF⁡(A0)F⁡(B0)+aF⁡(A1)F⁡(B1)+bF⁡(A0)F⁡(B1)+bF⁡(A1)F⁡(B0),cF⁡(A0)F⁡(B0)+cF⁡(A1)F⁡(B1)+dF⁡(A0)F⁡(B1)+dF⁡(A1)F⁡(B0)]=[aUW+aVX+bUX+bVW , cUW+cVX+dUX+dVW] \begin{split} \operatorname{F}(A \oplus B)&=\operatorname{F}([A_0\oplus B_0 + A_1\oplus B_1, A_0\oplus B_1+A_1\oplus B_0])\\\\ &=[a\operatorname{F}(A_0\oplus B_0 + A_1\oplus B_1) + b\operatorname{F}(A_0\oplus B_1+A_1\oplus B_0), c\operatorname{F}(A_0\oplus B_0 + A_1\oplus B_1) + d\operatorname{F}(A_0\oplus B_1+A_1\oplus B_0)]\\\\ &=[a\operatorname{F}(A_0\oplus B_0) + a\operatorname{F}(A_1\oplus B_1) + b\operatorname{F}(A_0\oplus B_1)+b\operatorname{F}(A_1\oplus B_0),c\operatorname{F}(A_0\oplus B_0)+ c\operatorname{F}(A_1\oplus B_1) + d\operatorname{F}(A_0\oplus B_1)+d\operatorname{F}(A_1\oplus B_0)]\\\\ &=[a\operatorname{F}(A_0)\operatorname{F}(B_0) + a\operatorname{F}(A_1)\operatorname{F}(B_1) + b\operatorname{F}(A_0)\operatorname{F}(B_1)+b\operatorname{F}(A_1)\operatorname{F}(B_0),c\operatorname{F}(A_0)\operatorname{F}(B_0)+ c\operatorname{F}(A_1)\operatorname{F}(B_1) + d\operatorname{F}(A_0)\operatorname{F}(B_1)+d\operatorname{F}(A_1)\operatorname{F}(B_0)]\\\\ &=[aUW + aVX + bUX+bVW\ ,\ cUW+ cVX + dUX+dVW] \end{split}

和 (eq.~eq. 7) 对齐系数可以得到如下方程组： {a=a2a=b2b=2abc=c2c=d2d=2cd \begin{cases} a=a^2\\\\ a=b^2\\\\ b=2ab\\\\ c=c^2\\\\ c=d^2\\\\ d=2cd \end{cases} 解上面的方程组即可，显然有许多解。但是考虑到不仅需要 FWT⁡\operatorname{FWT} ，还需要 iFWT⁡\operatorname{iFWT}。有些解无法保证 iFWT⁡\operatorname{iFWT} 能够存在解。

由： F⁡(A)=merge⁡(a⋅F⁡(A0)+b⋅F⁡(A1) ,c⋅F⁡(A0)+d⋅F⁡(A1)) \operatorname{F}(A) = \operatorname{merge}(a \cdot\operatorname{F}(A_0) + b \cdot\operatorname{F}(A_1)\ ,c \cdot\operatorname{F}(A_0) + d \cdot\operatorname{F}(A_1) )

设 X=a⋅F⁡(A0)+b⋅F⁡(A1)X = a \cdot\operatorname{F}(A_0) + b \cdot\operatorname{F}(A_1)，Y=c⋅F⁡(A0)+d⋅F⁡(A1)Y = c \cdot\operatorname{F}(A_0) + d \cdot\operatorname{F}(A_1)。问题变成了已知 X,YX, Y，求出 F⁡(A0),F⁡(A1)\operatorname{F}(A_0), \operatorname{F}(A_1)，可以解得： F⁡(A1)=aY−cXda−bc \operatorname{F}(A_1) =\frac{aY - cX}{da-bc} F⁡(A0)=dX−bYda−bc \operatorname{F}(A_0) =\frac{dX - bY}{da-bc} 因此上述方程组中，解还需要需要保证 ad≠bcad \not = bc。

可以解出一如下两组解： {a=1b=−1c=1d=1 \begin{cases} a=1\\\\ b=-1\\\\ c=1\\\\ d=1 \end{cases} {a=1b=1c=1d=−1 \begin{cases} a=1\\\\ b=1\\\\ c=1\\\\ d=-1 \end{cases}

上述两组解带入后都可以实现异或卷积。

质数表

来自 min_25的博客Orz

最长周期 nn 质数 原根 z(zn=1)z(z^n = 1) p−1p-1的因数分解
2262^{26} 469762049 3 2187 226×72^{26} \times 7
2252^{25} 167772161 3 243 225×52^{25} \times 5
2242^{24} 754974721 11 739831874 224×32×52^{24} \times 3^2 \times 5
2232^{23} 377487361 7 48510621 223×32×52^{23} \times 3^2 \times 5
2232^{23} 595591169 3 361399025 223×712^{23} \times 71
2232^{23} 645922817 3 224270701 223×7×112^{23} \times 7 \times 11
2232^{23} 880803841 26 273508579 223×3×5×72^{23} \times 3 \times 5 \times 7
2232^{23} 897581057 3 872686320 223×1072^{23} \times 107
2232^{23} 998244353 3 15311432 223×7×172^{23} \times 7 \times 17
2222^{22} 104857601 3 39193363 222×522^{22} \times 5^2
2222^{22} 113246209 7 58671006 222×332^{22} \times 3^3
2222^{22} 138412033 5 99040867 222×3×112^{22} \times 3 \times 11
2222^{22} 155189249 6 14921912 222×372^{22} \times 37
2222^{22} 163577857 23 121532577 222×3×132^{22} \times 3 \times 13
2222^{22} 230686721 6 71750113 222×5×112^{22} \times 5 \times 11
2222^{22} 415236097 5 73362476 222×32×112^{22} \times 3^2 \times 11
2222^{22} 666894337 5 147340140 222×3×532^{22} \times 3 \times 53
2222^{22} 683671553 3 236932120 222×1632^{22} \times 163
2222^{22} 918552577 5 86995699 222×3×732^{22} \times 3 \times 73
2222^{22} 935329793 3 86363943 222×2232^{22} \times 223
2222^{22} 943718401 7 754500478 222×32×522^{22} \times 3^2 \times 5^2
2222^{22} 985661441 3 79986183 222×5×472^{22} \times 5 \times 47
2212^{21} 111149057 3 60767546 221×532^{21} \times 53
2212^{21} 132120577 5 102376994 221×32×72^{21} \times 3^2 \times 7
2212^{21} 136314881 3 2981173 221×5×132^{21} \times 5 \times 13
2212^{21} 169869313 5 143354861 221×342^{21} \times 3^4
2212^{21} 186646529 3 88383805 221×892^{21} \times 89
2212^{21} 199229441 3 174670364 221×5×192^{21} \times 5 \times 19
2212^{21} 211812353 3 113852926 221×1012^{21} \times 101
2212^{21} 249561089 3 61724276 221×7×172^{21} \times 7 \times 17
2212^{21} 257949697 5 186470816 221×3×412^{21} \times 3 \times 41
2212^{21} 270532609 22 74891632 221×3×432^{21} \times 3 \times 43
2212^{21} 274726913 3 255478716 221×1312^{21} \times 131
2212^{21} 383778817 5 324881819 221×3×612^{21} \times 3 \times 61
2212^{21} 387973121 6 124477810 221×5×372^{21} \times 5 \times 37
2212^{21} 459276289 11 238723101 221×3×732^{21} \times 3 \times 73
2212^{21} 463470593 3 428228038 221×13×172^{21} \times 13 \times 17
2212^{21} 576716801 6 153098993 221×52×112^{21} \times 5^2 \times 11
2212^{21} 597688321 11 395834143 221×3×5×192^{21} \times 3 \times 5 \times 19
2212^{21} 635437057 11 171402456 221×3×1012^{21} \times 3 \times 101
2212^{21} 639631361 6 432237000 221×5×612^{21} \times 5 \times 61
2212^{21} 648019969 17 592437138 221×3×1032^{21} \times 3 \times 103
2212^{21} 710934529 17 69533131 221×3×1132^{21} \times 3 \times 113
2212^{21} 715128833 3 355872337 221×11×312^{21} \times 11 \times 31
2212^{21} 740294657 3 237508734 221×3532^{21} \times 353
2212^{21} 786432001 7 228383098 221×3×532^{21} \times 3 \times 5^3
2212^{21} 799014913 13 374051146 221×3×1272^{21} \times 3 \times 127
2212^{21} 824180737 5 133412682 221×3×1312^{21} \times 3 \times 131
2212^{21} 899678209 7 118485495 221×3×11×132^{21} \times 3 \times 11 \times 13
2212^{21} 924844033 5 44009197 221×32×722^{21} \times 3^2 \times 7^2
2212^{21} 950009857 7 741494216 221×3×1512^{21} \times 3 \times 151
2212^{21} 962592769 7 695637473 221×33×172^{21} \times 3^3 \times 17
2212^{21} 975175681 17 518451017 221×3×5×312^{21} \times 3 \times 5 \times 31
2212^{21} 1004535809 3 702606812 221×4792^{21} \times 479
2212^{21} 1012924417 5 673144645 221×3×7×232^{21} \times 3 \times 7 \times 23

📚 Version History

Source Code Change History
v1
🔗 Source Hash: 212d38997367613b88c7d1ab65b9f4d9cb4abd51c2fcfeb914f17ecc0e13f3ee
Build Logs 
Build Log - Filtered
================================================

📋 Information:
• Path information has been filtered for privacy protection
• File names are preserved for debugging purposes  
• All build status and error messages are kept intact

🔍 Filter Rules:
• /absolute/path/file.ext → .../file.ext
• /home/username → .../[user]
• /tmp/files → .../[temp]
• /usr/share/packages → .../[system]

================================================

html log:
CMD: ['pandoc', '-s', 'cache/oi-blog_「学习总结」基本卷积算法.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache.../oi-blog_「学习总结」基本卷积算法.md.html', '--metadata', '--verbose', '--highlight-style=tango']
STDOUT: 
STDERR: WARNING: pandoc-crossref was compiled with pandoc 3.6.2 but is being run through 3.6.4. This is not supported. Strange things may (and likely will) happen silently.

====================================================================================================
pdf log:
CMD: ['pandoc', '-s', 'cache.../1c7794a790.pdf.md', '-o', 'cache/1c7794a790.pdf', '-H', 'static/pandoc.header.tex', '--pdf-engine=xelatex', '--verbose']
STDOUT: 
STDERR: [INFO] Loaded static.../pandoc.header.tex from static.../pandoc.header.tex
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] [makePDF] Temp dir:
  .../[temp]
[INFO] [makePDF] Command line:
  xelatex "-halt-on-error" "-interaction" "nonstopmode" "-output-directory" ".../[temp] ".../[temp]
[INFO] [makePDF] Relevant environment variables:
  ("TEXINPUTS",".../[temp]
  ("TEXMFOUTPUT",".../[temp]
  ("SHELL","/bin/bash")
  ("PWD",".../[user]/projects/blog")
  ("HOME",".../[user]
  ("LANG","zh_CN.UTF-8")
  ("PATH",".../[user]/.local/bin:.../[user]/.cargo/bin:.../[user]/miniconda3/envs/myblog/bin:.../[user]/miniconda3/condabin:.../[temp]
[INFO] [makePDF] Source:
  % Options for packages loaded elsewhere
  \PassOptionsToPackage{unicode}{hyperref}
  \PassOptionsToPackage{hyphens}{url}
  \PassOptionsToPackage{space}{xeCJK}
  \documentclass[
  ]{article}
  \usepackage{xcolor}
  \usepackage[a4paper,margin=2cm]{geometry}
  \usepackage{amsmath,amssymb}
  \setcounter{secnumdepth}{-\maxdimen} % remove section numbering
  \usepackage{iftex}
  \ifPDFTeX
    \usepackage[T1]{fontenc}
    \usepackage[utf8]{inputenc}
    \usepackage{textcomp} % provide euro and other symbols
  \else % if luatex or xetex
    \usepackage{unicode-math} % this also loads fontspec
    \defaultfontfeatures{Scale=MatchLowercase}
    \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
  \fi
  \usepackage{lmodern}
  \ifPDFTeX\else
    % xetex/luatex font selection
    \setmainfont[]{Latin Modern Roman}
    \ifXeTeX
      \usepackage{xeCJK}
      \setCJKmainfont[]{AR PL UKai CN}
    \fi
    \ifLuaTeX
      \usepackage[]{luatexja-fontspec}
      \setmainjfont[]{AR PL UKai CN}
    \fi
  \fi
  % Use upquote if available, for straight quotes in verbatim environments
  \IfFileExists{upquote.sty}{\usepackage{upquote}}{}
  \IfFileExists{microtype.sty}{% use microtype if available
    \usepackage[]{microtype}
    \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
  }{}
  \usepackage{setspace}
  \makeatletter
  \@ifundefined{KOMAClassName}{% if non-KOMA class
    \IfFileExists{parskip.sty}{%
      \usepackage{parskip}
    }{% else
      \setlength{\parindent}{0pt}
      \setlength{\parskip}{6pt plus 2pt minus 1pt}}
  }{% if KOMA class
    \KOMAoptions{parskip=half}}
  \makeatother
  \usepackage{longtable,booktabs,array}
  \usepackage{calc} % for calculating minipage widths
  % Correct order of tables after \paragraph or \subparagraph
  \usepackage{etoolbox}
  \makeatletter
  \patchcmd\longtable{\par}{\if@noskipsec\mbox{}\fi\par}{}{}
  \makeatother
  % Allow footnotes in longtable head/foot
  \IfFileExists{footnotehyper.sty}{\usepackage{footnotehyper}}{\usepackage{footnote}}
  \makesavenoteenv{longtable}
  \setlength{\emergencystretch}{3em} % prevent overfull lines
  \providecommand{\tightlist}{%
    \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
  % \usepackage{xeCJK}
  % \setCJKmainfont{AR PL UKai CN}
  % \usepackage{unicode-math}
  
  \setmathfont{Latin Modern Math}
  \usepackage{bookmark}
  \IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
  \urlstyle{same}
  \hypersetup{
    pdftitle={「学习总结」基本卷积算法},
    pdfauthor={Jiayi Su (ShuYuMo)},
    hidelinks,
    pdfcreator={LaTeX via pandoc}}
  
  \title{「学习总结」基本卷积算法}
  \author{Jiayi Su (ShuYuMo)}
  \date{2021-01-17 15:35:06}
  
  \begin{document}
  \maketitle
  
  \setstretch{1.3}
  「做多项式题就像嗑药，出多项式题就像贩毒。」 —— 某福建知名OI选手
  
  学了学红日bn一年前玩剩下的东西。
  
  倒是扩展了 FWT 的一种思路吧。
  
  \section{基本卷积算法}\label{ux57faux672cux5377ux79efux7b97ux6cd5}
  
  \subsection{加法卷积}\label{ux52a0ux6cd5ux5377ux79ef}
  
  用于解决形如以下问题： 给出两个序列 \(A, B\)。求两个序列的卷积序列
  \(C\)，其中序列 \(C\) 的定义如下
  
  \[
  C_k = \sum_{i+j=k}A_i \times B_j
  \] \{\#eq:QWQ\}
  
  序列可以看作是函数的系数表示法，所以我们可以定义函数 \$F(x) = \sum\_\{i
  \ge 0\} A\_i x\^{}i \$ 和函数 \(G(x)= \sum_{i \ge 0} B_i x^i\)
  分别对应序列 \(A, B\) 的两个函数。
  
  类似的，还可以定义序列 \(C\) 对应函数
  \(T(x) = \sum_{i \ge 0} C_i x^i\)。
  
  注意到这种定义就是将序列的第 \(i\) 个数当作多项式函数的第 \(i\) 次系数。
  
  注意到
  
  \[ 
  T(x)=F(x) \times G(x) 
  \] \{\#eq:QAQ\}
  
  这个是后面卷积方法的核心工作原理。本质上是 建立了 \textbf{序列运算}
  与其对应 \textbf{函数（多项式）运算} 的一种联系。
  
  注意到 (eq.\textasciitilde{}@eq:QAQ) 也可以理解为对于任意常数
  \(a\)，总有 \(T(a)=F(a) \times G(a)\)。
  
  也就是说，如果我们知道了 \(G(x)\) 和 \(F(x)\) 在 \(a\)
  处的函数值，那么他们相乘就能够得到 \(T(x)\) 在 \(a\) 处的函数值。
  
  考虑如果存在一种变换，能够快速计算 \(G(x)\) 和 \(F(x)\) 在某些特定自变量
  \(\\{a_1, a_2, a_3,\cdots a_k\\}\) 处的函数值，那么就能快速算出 \(T(x)\)
  在这些自变量处的函数值。
  
  如果存在某种逆变换，能够快速将函数在某些自变量处的函数值转换成每一次项的系数，那么就能够求出
  \(T(x)\) 的系数（即序列 \(C\)）了。
  
  总的来说，希望存在一种序列上变换 \(\operatorname{FFT}(T)\)，使得 \[
  \operatorname{FFT}(C) = \operatorname{FFT}(A \times B) = \operatorname{FFT}(A) \cdot \operatorname{FFT}(B)
  \] 其中 \(\times\) 表示序列加法卷积
  (eq.\textasciitilde{}@eq:QWQ)，\(\cdot\) 表示对应位置相乘。
  
  并且这种变换存在逆变换，能够将 \(\operatorname{FFT}(C)\) 还原为 \(C\) 。
  
  通过上述描述可以发现，对于一个函数 \(G(x)\)
  来说，其表示成序列的方式有两种：一种是构造序列，使得序列第 \(i\)
  位为多项式函数 \(G(x)\) 的第 \(i\)
  次项系数。另一种是指定一系列取值\(\\{a_1, a_2, a_3,\cdots a_k\\}\)
  ，分别带入函数中，得到的函数值依次排开，成为一个序列。我们称前者为函数
  \(G(x)\)
  的系数表示法，称后者为其点值表示法。而我们所希望的变换就是能够实现函数的\textbf{系数表示法}
  与 \textbf{点值表示法} 相互转化。
  
  因为
  两函数相乘时，其对应的系数表示法的序列就是在做卷积操作，对应了我们希望的运算，但是这个并不能快速计算。而两函数相乘，对于点值表示法，就仅仅是对应位置相乘，这个可以快速计算。所以可以考虑如果能够快速实现
  \emph{函数的\textbf{系数表示法} 与 \textbf{点值表示法}
  相互转化}。就能够解决上述问题。可以先转化为点值表示法，然后对点相乘后，再转换为系数表示法，就相当于对序列做卷积。
  
  \subsubsection{快速傅里叶变换（FFT）}\label{ux5febux901fux5085ux91ccux53f6ux53d8ux6362fft}
  
  \textbf{快速傅里叶变换}
  就是一种满足上述条件的变换。她可以使得函数在系数表示法与点值表示法之间转换。
  时间复杂度为 \(\mathcal{O}(n \log n)\)。
  
  考虑上述过程中，并没有限制点值表示法中的点值应该取哪些值，所以可以考虑取一些有丰富性质的数字，利用这些性质加速运算。
  
  对于 FFT 我们取 \textbf{n次单位根} 来加速运算。\(n\) 为待变换序列长度。
  
  \paragraph{单位根}\label{ux5355ux4f4dux6839}
  
  \emph{n} 次单位根记作 \(\omega_n\)。其定义为
  \(\omega_n = \cos{\frac{2\pi}{n}} + \mathrm{i}\sin{\frac{2\pi}{n}}\)，这是一个虚数。虚数可以通过向量来表示，而
  \(\omega_n\) 就可以考虑为一个模长为 \(1\) ，与 \(x\) 轴夹角为
  \(\frac{2\pi}{n}\) 的向量。易知，
  \(\omega_n^k=\cos{\frac{2\pi k}{n}} + \mathrm{i}\sin{\frac{2\pi k}{n}}\)。
  
  他有如下性质
  
  \begin{itemize}
  \tightlist
  \item
    \(\omega_n^k=\omega_{2n}^{2k}\)
  \item
    \(\omega_n^{k + \frac{n}{2}}=-\omega_{n}^{k}\)
  \item
    \(\omega_n^0=\omega_n^n=1\)
  \end{itemize}
  
  这些性质都可以通过其定义得知。
  
  考虑将 \(\omega_n^0, \omega_n^1, \omega_n^2, \cdots, \omega_n^{n-1}\)
  带入函数，得到点值即可。
  
  \paragraph{蝴蝶操作}\label{ux8774ux8776ux64cdux4f5c}
  
  分别抽取函数 \(F(x)\) 的奇、偶次项系数构成两个新函数 \(G(x), H(x)\)。
  易知: \[
  F(x) = G(x^2) + xH(x^2)
  \] 即 \[
  F(\omega_n^k) = G(\omega_{n/2}^k) + \omega_n^k H(\omega_{n/2}^k) 
  \] \[
  F(\omega_n^{k + n/2}) = G(\omega_{n/2}^k) - \omega_n^k H(\omega_{n/2}^k)
  \]
  
  划分了子问题，分治即可。这里必须保证 \(n = 2^k\)，\(k \in \mathbb{N}\)
  
  \paragraph{逆变换}\label{ux9006ux53d8ux6362}
  
  单位根还有如下性质 \[
  \sum_{i=0}^{n-1}\left(\omega_n^k\right)^i=
  \begin{cases}
  0& {k \not= 0}\\\\
  n& {k = 0}
  \end{cases}
  \] 第二种情况显然，第一种情况根据等比数列求和公式可以得证。
  
  根据上述性质，我们只需要取单位根为之前的倒数，然后跑一遍
  \(\operatorname{FFT}\) 对结果除以 \(n\) 即可。 不会推QAQ。
  
  \subsubsection{快速数论变换（NTT）}\label{ux5febux901fux6570ux8bbaux53d8ux6362ntt}
  
  FFT 需要实数运算，对精度要求较高。且无法解决常见的取模要求。
  
  注意到 \(FFT\)
  中所依赖的是一个复平面上的单位圆，其实剩余系本身就可以看作一个环。可以考虑在剩余系下寻找具有与单位根性质类似的数字。
  
  设质数 \(P\) 的原根为 \(g\)。那么
  \(\forall k \in [0, \varphi(P) - 1],k \in \mathbb{N},g^{k}\)，可以表示
  \(P\) 的剩余系中除 \(0\) 以外的任何数字，显然可表示的数字有 \(P-1\) 个。
  
  以下关于剩余系类比复平面单位圆的描述由笔者口胡，不保证语言严谨。
  
  在 \(\operatorname{FFT}\)
  中取单位根的方式本质上实在均分复平面上单位圆。而 \(\operatorname{NTT}\)
  中，如果将 \(g^k\)
  依次排成一个环，即剩余系，我们一样可以通过均分这个环，来取剩余系下的“单位根”，来获得和之前复平面单位根
  类似性质的一些数。显然，这里需要保证在我们均分单位圆的过程中，每个值都能取到，也就是
  \(n | \varphi(P)\)，即 \(n | (P-1)\)。
  
  所以这里的剩余系取值有一定要求，变换中所要求的 \(n\) 都是 \(2\)
  的次幂，需要保证 \(P-1\) 中 \(2\)
  的幂次应该足够大。（文末附\href{./\#质数表}{质数取值表}）
  
  设 \(P-1 = q\times n\)。
  
  考虑将 \(g_n=g^q\) 当作 \(\omega_n\) 即可，根据上面的描述，\(\omega_n\)
  所具有的性质，\(g_{n}\) 显然成立。这里的 \(q\)
  可以想成等分环时的单位角度。
  
  关于 \textbf{蝴蝶操作} 和 \textbf{逆变换} 的手法和
  \(\operatorname{FFT}\) 是一样的。
  
  \subsection{位运算卷积}\label{ux4f4dux8fd0ux7b97ux5377ux79ef}
  
  类似地，定义位运算序列卷积。 给出两个序列 \(A, B\)。求两个序列的卷积序列
  \(C\)，其中序列 \(C\) 的定义如下
  
  \[
  C_k = \sum_{i\oplus j=k}A_i \times B_j
  \] \{\#eq:QWQWQ\}
  
  可以仿照上述思路，构造一种作用在序列上的变换
  \(\operatorname{FWT}\)，使得其满足
  
  \[
  \operatorname{FWT}(C) = \operatorname{FWT}(A \oplus B) = \operatorname{FWT}(A) \cdot \operatorname{FWT}(B)
  \] \{\#eq:FWT\}
  
  \(A \oplus B\) 中的 \(\oplus\) 指某种位运算。指下标的运算方式。即
  (eq.\textasciitilde{}@eq:QWQWQ) 中的 \(i\oplus j=k\)。
  
  \subsubsection{快速沃尔什变换（FWT）}\label{ux5febux901fux6c83ux5c14ux4ec0ux53d8ux6362fwt}
  
  考虑分治处理，令 \(A_0\) 为 \(A\) 的前一半， \(A_1\) 为 \(A\)
  的后一半。可以考虑如果已经求出了 \(\operatorname{FWT}(A_0)\) 和
  \(\operatorname{FWT}(A_1)\)，如何求出 \(\operatorname{FWT}(A)\)。
  
  顺便定义函数 \(\operatorname{merge}(A, B)\) 表示将序列 \(A, B\)
  直接前后拼接，返回拼接后的大序列。例如
  \(A = \operatorname{merge}(A_0, A_1)\)。
  
  \paragraph{或运算}\label{ux6216ux8fd0ux7b97}
  
  考虑如何构造 \(\operatorname{FWT}\) 的方式，使得：
  
  \[
  \operatorname{FWT}(A | B) = \operatorname{FWT}(A) \cdot \operatorname{FWT}(B)
  \] \{\#eq:FWTORBASE\}
  
  对于或运算卷积，直接给出结论。我们定义当前情况下的
  \(\operatorname{FWT}\) 的运算规则如下。
  
  \[ 
  \operatorname{FWT}(A) = \operatorname{merge}(\operatorname{FWT}(A_0), \operatorname{FWT}(A_0) + \operatorname{FWT}(A_1))
  \] \{\#eq:FWTOR\}
  
  其中 \(+\) 为序列对应位置相加。
  
  现在证明：已知 (eq.\textasciitilde{}@eq:FWTOR)，
  (eq.\textasciitilde{}@eq:FWTORBASE) 成立。
  
  将 \(\operatorname{FWT}\) 简记为 \(\operatorname{F}\)，将
  \(\operatorname{merge}(A, B)\) 简记为 \([A, B]\)
  
  首先试图从等式左边开始推导： \[
  \begin{split}
  \operatorname{F}(A) \cdot \operatorname{F}(B)
  &= \left[ \operatorname{F}(A_0),\ \operatorname{F}(A_0) + \operatorname{F}(A_1) \right] \cdot \left[ \operatorname{F}(B_0),\ \operatorname{F}(B_0) + \operatorname{F}(B_1) \right] \\
  &= \left[ \operatorname{F}(A_0) \cdot \operatorname{F}(B_0),\ (\operatorname{F}(A_0) + \operatorname{F}(A_1)) \cdot (\operatorname{F}(B_0) + \operatorname{F}(B_1)) \right] \\
  &= \left[ \operatorname{F}(A_0) \cdot \operatorname{F}(B_0),\ 
  \operatorname{F}(A_0)\cdot\operatorname{F}(B_0) + \operatorname{F}(A_0)\cdot\operatorname{F}(B_1) \right. \\
  &\quad\left. + \operatorname{F}(A_1)\cdot\operatorname{F}(B_0) + \operatorname{F}(A_1)\cdot\operatorname{F}(B_1) \right]
  \end{split}
  \]
  
  再从等式右边开始推导，先假设当序列长度为 \(\frac{|A|}{2}\) 时，根据
  (eq.\textasciitilde{}@eq:FWTOR) 能够使得
  (eq.\textasciitilde{}@eq:FWTORBASE) 成立。 \[
  \begin{split}
  \operatorname{F}(A\ |\ B) 
  &= \operatorname{F}([A_0|B_0, A_0|B_1 + A_1|B_0 + A_1 | B_1]) \\
  &= \left[ \operatorname{F}(A_0|B_0),\ \operatorname{F}(A_0|B_1) + \operatorname{F}(A_1|B_0) + \operatorname{F}(A_1 | B_1) + \operatorname{F}(A_0|B_0) \right] \\
  &= \left[
  \operatorname{F}(A_0) \cdot \operatorname{F}(B_0),\ 
  \operatorname{F}(A_0) \cdot \operatorname{F}(B_0)
  + \operatorname{F}(A_0) \cdot \operatorname{F}(B_1)
  + \operatorname{F}(A_1) \cdot \operatorname{F}(B_0)
  + \operatorname{F}(A_1) \cdot \operatorname{F}(B_1)
  \right]
  \end{split}
  \]
  
  我们假设结论在 序列长度为 \(\frac{|A|}{2}\) 时 成立，能够推出 序列长度为
  \(|A|\) 时 成立，就能够推出上述结论在任何情况下均适用（数学归纳法）。
  
  考虑如何构造逆变换 \(\operatorname{iFWT}\) 的运算规则。
  相当于每一步都反向操作。
  
  因为： \[
  \operatorname{FWT}(A) = \operatorname{merge}(\operatorname{FWT}(A_0), \operatorname{FWT}(A_0) + \operatorname{FWT}(A_1))
  \] 相当于，现在已经得到了 \(A_0' = A_0\) ，\(A_1' = A_0 +A_1​\)
  那么易知： \[
  A_0 = A_0'
  \] \[
  A_1 =  A_1' - A_0'
  \]
  
  因此，逆变换就是： \[
  \operatorname{iFWT}(A)=\operatorname{merge}(\operatorname{iFWT}(A_0), \operatorname{iFWT}(A_1) - \operatorname{iFWT}(A_0))
  \]
  
  需要注意的是： \[
  \operatorname{FWT}(A)_i = \sum_{j \subseteq i}A_j
  \]
  
  \paragraph{与运算}\label{ux4e0eux8fd0ux7b97}
  
  \[
  \operatorname{FWT}(A) = \operatorname{merge}(\operatorname{FWT}(A_0) + \operatorname{FWT}(A_1), \operatorname{FWT}(A_1))
  \] \[
  \operatorname{iFWT}(A)=\operatorname{merge}(\operatorname{iFWT}(A_0) - \operatorname{iFWT}(A_1),\operatorname{iFWT}(A_1) )
  \]
  
  需要注意的是： \[
  \operatorname{FWT}(A)_i = \sum_{i \subseteq j}A_j
  \]
  
  \paragraph{一般方法}\label{ux4e00ux822cux65b9ux6cd5}
  
  构造的逆运算为解方程。
  
  考虑如何根据一种位运算，求出一种合法的
  \(\operatorname{FWT} / \operatorname{iFWT}\)
  构造方式。这里的\textbf{合法}指这种构造方式满足
  (eq.\textasciitilde{}@eq:FWT)
  
  考虑某种位运算 \(\oplus\) 的 \(\operatorname{FWT}​\)
  应该是什么样子。根据上面的两个例子，可以设出如下式子： \[
  \operatorname{F}(A) = \operatorname{merge}(a \cdot\operatorname{F}(A_0) + b \cdot\operatorname{F}(A_1)\ ,c \cdot\operatorname{F}(A_0) + d \cdot\operatorname{F}(A_1) )
  \] 这里的 \(a, b, c, d\) 为常数，“\(\cdot\)” 为普通乘法。
  
  为了方便，设 \(U=\operatorname{F}(A_0)\)，\(V=\operatorname{F}(A_1)\)，
  \(W=\operatorname{F}(B_0)\)，\(X=\operatorname{F}(B_1)\)
  
  则：
  
  \[
  \begin{split} 
  \operatorname{F}(A)\cdot\operatorname{F}(B)&=[aU+bV, cU+dV]\cdot[aW+bX, cW+dX]\\\\
  &=[a^2UW + 2ab(UX + VW)+b^2VX, c^2UW + 2cd(UX + VW)+d^2VX \ \ ]
  \end{split}
  \] \{\#eq:FWTCOM\}
  
  这里以\textbf{异或}为例，因为序列是中间分成两个序列，不妨设序列长度均为
  \(2\) 的若干次方，那么分开之后，其下标的最高位一定是前一半为 0 后一半为
  1，根据异或的运算规则，哪些元素组合起来能够什么样的最高位即可。
  
  假设上式在 序列长度为 \(\frac{|A|}{2}​\) 时是成立的。则： \[
  \begin{split}
  \operatorname{F}(A \oplus B)&=\operatorname{F}([A_0\oplus B_0 + A_1\oplus B_1, A_0\oplus B_1+A_1\oplus B_0])\\\\
  &=[a\operatorname{F}(A_0\oplus B_0 + A_1\oplus B_1) + b\operatorname{F}(A_0\oplus B_1+A_1\oplus B_0), c\operatorname{F}(A_0\oplus B_0 + A_1\oplus B_1) + d\operatorname{F}(A_0\oplus B_1+A_1\oplus B_0)]\\\\
  &=[a\operatorname{F}(A_0\oplus B_0) + a\operatorname{F}(A_1\oplus B_1) + b\operatorname{F}(A_0\oplus B_1)+b\operatorname{F}(A_1\oplus B_0),c\operatorname{F}(A_0\oplus B_0)+ c\operatorname{F}(A_1\oplus B_1) + d\operatorname{F}(A_0\oplus B_1)+d\operatorname{F}(A_1\oplus B_0)]\\\\
  &=[a\operatorname{F}(A_0)\operatorname{F}(B_0) + a\operatorname{F}(A_1)\operatorname{F}(B_1) + b\operatorname{F}(A_0)\operatorname{F}(B_1)+b\operatorname{F}(A_1)\operatorname{F}(B_0),c\operatorname{F}(A_0)\operatorname{F}(B_0)+ c\operatorname{F}(A_1)\operatorname{F}(B_1) + d\operatorname{F}(A_0)\operatorname{F}(B_1)+d\operatorname{F}(A_1)\operatorname{F}(B_0)]\\\\
  &=[aUW + aVX + bUX+bVW\ ,\ cUW+ cVX + dUX+dVW]
  \end{split}
  \]
  
  和 (eq.\textasciitilde{}@eq:FWTCOM) 对齐系数可以得到如下方程组： \[
  \begin{cases}
  a=a^2\\\\
  a=b^2\\\\
  b=2ab\\\\
  c=c^2\\\\
  c=d^2\\\\
  d=2cd
  \end{cases}
  \] 解上面的方程组即可，显然有许多解。但是考虑到不仅需要
  \(\operatorname{FWT}\) ，还需要 \(\operatorname{iFWT}\)。有些解无法保证
  \(\operatorname{iFWT}\) 能够存在解。
  
  由： \[
  \operatorname{F}(A) = \operatorname{merge}(a \cdot\operatorname{F}(A_0) + b \cdot\operatorname{F}(A_1)\ ,c \cdot\operatorname{F}(A_0) + d \cdot\operatorname{F}(A_1) )
  \]
  
  设
  \(X = a \cdot\operatorname{F}(A_0) + b \cdot\operatorname{F}(A_1)\)，\(Y = c \cdot\operatorname{F}(A_0) + d \cdot\operatorname{F}(A_1)\)。问题变成了已知
  \(X, Y\)，求出
  \(\operatorname{F}(A_0), \operatorname{F}(A_1)\)，可以解得： \[
  \operatorname{F}(A_1) =\frac{aY - cX}{da-bc}
  \] \[
  \operatorname{F}(A_0) =\frac{dX - bY}{da-bc}
  \] 因此上述方程组中，解还需要需要保证 \(ad \not = bc\)。
  
  可以解出一如下两组解： \[
  \begin{cases}
  a=1\\\\
  b=-1\\\\
  c=1\\\\
  d=1
  \end{cases}
  \] \[
  \begin{cases}
  a=1\\\\
  b=1\\\\
  c=1\\\\
  d=-1
  \end{cases}
  \]
  
  上述两组解带入后都可以实现异或卷积。
  
  \subparagraph{质数表}\label{ux8d28ux6570ux8868}
  
  来自
  \href{https://min-25.hatenablog.com/entry/2015/04/07/160154}{min\_25的博客Orz}
  
  \begin{longtable}[]{@{}lllll@{}}
  \toprule\noalign{}
  最长周期 \(n\) & 质数 & 原根 & \(z(z^n = 1)\) & \(p-1\)的因数分解 \\
  \midrule\noalign{}
  \endhead
  \bottomrule\noalign{}
  \endlastfoot
  \(2^{26}\) & 469762049 & 3 & 2187 & \(2^{26} \times 7\) \\
  \(2^{25}\) & 167772161 & 3 & 243 & \(2^{25} \times 5\) \\
  \(2^{24}\) & 754974721 & 11 & 739831874 &
  \(2^{24} \times 3^2 \times 5\) \\
  \(2^{23}\) & 377487361 & 7 & 48510621 &
  \(2^{23} \times 3^2 \times 5\) \\
  \(2^{23}\) & 595591169 & 3 & 361399025 & \(2^{23} \times 71\) \\
  \(2^{23}\) & 645922817 & 3 & 224270701 &
  \(2^{23} \times 7 \times 11\) \\
  \(2^{23}\) & 880803841 & 26 & 273508579 &
  \(2^{23} \times 3 \times 5 \times 7\) \\
  \(2^{23}\) & 897581057 & 3 & 872686320 & \(2^{23} \times 107\) \\
  \(2^{23}\) & 998244353 & 3 & 15311432 & \(2^{23} \times 7 \times 17\) \\
  \(2^{22}\) & 104857601 & 3 & 39193363 & \(2^{22} \times 5^2\) \\
  \(2^{22}\) & 113246209 & 7 & 58671006 & \(2^{22} \times 3^3\) \\
  \(2^{22}\) & 138412033 & 5 & 99040867 & \(2^{22} \times 3 \times 11\) \\
  \(2^{22}\) & 155189249 & 6 & 14921912 & \(2^{22} \times 37\) \\
  \(2^{22}\) & 163577857 & 23 & 121532577 &
  \(2^{22} \times 3 \times 13\) \\
  \(2^{22}\) & 230686721 & 6 & 71750113 & \(2^{22} \times 5 \times 11\) \\
  \(2^{22}\) & 415236097 & 5 & 73362476 &
  \(2^{22} \times 3^2 \times 11\) \\
  \(2^{22}\) & 666894337 & 5 & 147340140 &
  \(2^{22} \times 3 \times 53\) \\
  \(2^{22}\) & 683671553 & 3 & 236932120 & \(2^{22} \times 163\) \\
  \(2^{22}\) & 918552577 & 5 & 86995699 & \(2^{22} \times 3 \times 73\) \\
  \(2^{22}\) & 935329793 & 3 & 86363943 & \(2^{22} \times 223\) \\
  \(2^{22}\) & 943718401 & 7 & 754500478 &
  \(2^{22} \times 3^2 \times 5^2\) \\
  \(2^{22}\) & 985661441 & 3 & 79986183 & \(2^{22} \times 5 \times 47\) \\
  \(2^{21}\) & 111149057 & 3 & 60767546 & \(2^{21} \times 53\) \\
  \(2^{21}\) & 132120577 & 5 & 102376994 &
  \(2^{21} \times 3^2 \times 7\) \\
  \(2^{21}\) & 136314881 & 3 & 2981173 & \(2^{21} \times 5 \times 13\) \\
  \(2^{21}\) & 169869313 & 5 & 143354861 & \(2^{21} \times 3^4\) \\
  \(2^{21}\) & 186646529 & 3 & 88383805 & \(2^{21} \times 89\) \\
  \(2^{21}\) & 199229441 & 3 & 174670364 &
  \(2^{21} \times 5 \times 19\) \\
  \(2^{21}\) & 211812353 & 3 & 113852926 & \(2^{21} \times 101\) \\
  \(2^{21}\) & 249561089 & 3 & 61724276 & \(2^{21} \times 7 \times 17\) \\
  \(2^{21}\) & 257949697 & 5 & 186470816 &
  \(2^{21} \times 3 \times 41\) \\
  \(2^{21}\) & 270532609 & 22 & 74891632 &
  \(2^{21} \times 3 \times 43\) \\
  \(2^{21}\) & 274726913 & 3 & 255478716 & \(2^{21} \times 131\) \\
  \(2^{21}\) & 383778817 & 5 & 324881819 &
  \(2^{21} \times 3 \times 61\) \\
  \(2^{21}\) & 387973121 & 6 & 124477810 &
  \(2^{21} \times 5 \times 37\) \\
  \(2^{21}\) & 459276289 & 11 & 238723101 &
  \(2^{21} \times 3 \times 73\) \\
  \(2^{21}\) & 463470593 & 3 & 428228038 &
  \(2^{21} \times 13 \times 17\) \\
  \(2^{21}\) & 576716801 & 6 & 153098993 &
  \(2^{21} \times 5^2 \times 11\) \\
  \(2^{21}\) & 597688321 & 11 & 395834143 &
  \(2^{21} \times 3 \times 5 \times 19\) \\
  \(2^{21}\) & 635437057 & 11 & 171402456 &
  \(2^{21} \times 3 \times 101\) \\
  \(2^{21}\) & 639631361 & 6 & 432237000 &
  \(2^{21} \times 5 \times 61\) \\
  \(2^{21}\) & 648019969 & 17 & 592437138 &
  \(2^{21} \times 3 \times 103\) \\
  \(2^{21}\) & 710934529 & 17 & 69533131 &
  \(2^{21} \times 3 \times 113\) \\
  \(2^{21}\) & 715128833 & 3 & 355872337 &
  \(2^{21} \times 11 \times 31\) \\
  \(2^{21}\) & 740294657 & 3 & 237508734 & \(2^{21} \times 353\) \\
  \(2^{21}\) & 786432001 & 7 & 228383098 &
  \(2^{21} \times 3 \times 5^3\) \\
  \(2^{21}\) & 799014913 & 13 & 374051146 &
  \(2^{21} \times 3 \times 127\) \\
  \(2^{21}\) & 824180737 & 5 & 133412682 &
  \(2^{21} \times 3 \times 131\) \\
  \(2^{21}\) & 899678209 & 7 & 118485495 &
  \(2^{21} \times 3 \times 11 \times 13\) \\
  \(2^{21}\) & 924844033 & 5 & 44009197 &
  \(2^{21} \times 3^2 \times 7^2\) \\
  \(2^{21}\) & 950009857 & 7 & 741494216 &
  \(2^{21} \times 3 \times 151\) \\
  \(2^{21}\) & 962592769 & 7 & 695637473 &
  \(2^{21} \times 3^3 \times 17\) \\
  \(2^{21}\) & 975175681 & 17 & 518451017 &
  \(2^{21} \times 3 \times 5 \times 31\) \\
  \(2^{21}\) & 1004535809 & 3 & 702606812 & \(2^{21} \times 479\) \\
  \(2^{21}\) & 1012924417 & 5 & 673144645 &
  \(2^{21} \times 3 \times 7 \times 23\) \\
  \end{longtable}
  
  \end{document}
[INFO] [makePDF] LaTeX run number 1
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../longtable.sty)
  (.../booktabs.sty)
  (.../array.sty)
  (.../calc.sty)
  (.../footnotehyper.sty)
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty
  (.../infwarerr.sty)))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  No file input.aux.
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  
  Package hyperref Warning: Rerun to get /PageLabels entry.
  
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 92.
  
  Missing character: There is no ∑ (U+2211) in font Latin Modern Roman 10 Regular
  /OT:script=latn;language=dflt;mapping=tex-text;!
  Missing character: There is no ≥ (U+2265) in font Latin Modern Roman 10 Regular
  /OT:script=latn;language=dflt;mapping=tex-text;!
  [1]
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/m/it' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 153.
  
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/it' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/b/n' instead on input line 153.
  
  [2] [3] [4]
  Overfull \hbox (142.4866pt too wide) detected at line 402
  []
  [5] [6]
  
  Package longtable Warning: Column widths have changed
  (longtable)                in table 1 on input line 547.
  
  [7]
  
  Package longtable Warning: Table widths have changed. Rerun LaTeX.
  
  [8] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
  
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
  
   )
  (see the transcript file for additional information)
  Output written on .../input.pdf (8 pages).
  Transcript written on .../input.log.
[INFO] [makePDF] Rerun needed
  Package hyperref Warning: Rerun to get /PageLabels entry.
  Package longtable Warning: Table widths have changed. Rerun LaTeX.
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
[INFO] [makePDF] LaTeX run number 2
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../longtable.sty)
  (.../booktabs.sty)
  (.../array.sty)
  (.../calc.sty)
  (.../footnotehyper.sty)
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty
  (.../infwarerr.sty)))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  (.../input.aux)
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 92.
  
  Missing character: There is no ∑ (U+2211) in font Latin Modern Roman 10 Regular
  /OT:script=latn;language=dflt;mapping=tex-text;!
  Missing character: There is no ≥ (U+2265) in font Latin Modern Roman 10 Regular
  /OT:script=latn;language=dflt;mapping=tex-text;!
  [1]
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/m/it' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 153.
  
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/it' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/b/n' instead on input line 153.
  
  [2] [3] [4]
  Overfull \hbox (142.4866pt too wide) detected at line 402
  []
  [5] [6] [7] [8] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
   )
  (see the transcript file for additional information)
  Output written on .../input.pdf (8 pages).
  Transcript written on .../input.log.
[WARNING] Missing character: There is no ∑ (U+2211) (U+2211) in font Latin Modern Roman 10 Regular
[WARNING] Missing character: There is no ≥ (U+2265) (U+2265) in font Latin Modern Roman 10 Regular