Polynomials Techniques - Some Genius Tricks

这已经是彻头彻尾的 trick 了。

主要讲的是魔改 FFT 的优化,和可以来实现的东西。

有一些优化技巧被人称作 FMT, Fast Maoyeye Transform. 我觉得海星。

[TOC]

Arbitrary Length Cyclic Convolution & Bluestein's Algorithm

考虑我们在做 FFT 的实质,是在计算

$$ a_m=\sum_{k=0}^{n-1}\omega^{mk}b_k $$

其中 $ n $ 是 $ 2 $ 的幂,$ \omega:=\omega_n $ 是主 $ n $ 次单位根,我们可以用蝴蝶操作快速计算。

注意到单位根的循环性 $ \omega_n^j=\omega_n^{j\bmod n} $ ,计算出来的结果实际上实在模 $ n $ 长度下的循环卷积。

这时一个自然的问题是:任意长度的循环卷积该怎么做?即 $ n $ 不再是 $ 2 $ 的幂。

Method 1 使用超过两倍 $ n $ 的 $ 2 $ 的幂作为长度,计算出来后暴力将多余项 $ c_{k+n} $ 循环回去加到 $ c_k $。

这种方法只能做单次循环卷积,多次循环卷积的话需要一次次来,计算快速幂时需要 $ \mathcal O(\log p) $ 次,我们希望避免。

我们想要知道在特殊的存在任意 $ n $ 次单位根的域(如 $ \mathbb R, \mathbb C, $ 一些特殊的 $ \mathbb F_p $)是否可以直接做长度为 $ n $ 的循环卷积。

Method 2 我们继续考察上式。

$$ \begin{align} a_m&=\sum_{k=0}^{n-1}\omega^{mk}b_k \\ &=\sum_{k=0}^{n-1}\omega^{-{(m-k)^2-m^2-k^2\over 2} }b_k\\ &=\omega^{-{m^2 \over 2}}\sum_{k=0}^{n-1}\omega^{-{(m-k)^2\over2}}\omega^{-{k^2\over2}}b_k \end{align} $$

可以看出这很像是一个卷积的式子,唯一的差别是上下界。但注意到只有当 $ i=0..n-1 $ 时 $ b_i $ 才有可能非零。具体做法,考虑 $ B_i=\omega^{-{(i-n)^2\over2}} $

$$ \begin{align} A_{m+n}&= \omega^{-{m^2\over2}}a_m \\ &=\sum_{k=0}^{n-1}B_{m+n-k}\omega^{-{k^2\over2}}b_k \\ &=\sum_{k=0}^{m+n}B_{m+n-k}\omega^{-{k^2\over2}}b_k \end{align} $$

NTT with 3 Moduli

选三个 $ 10^9 $ 级别的模数分别做 NTT. 算出来用 CRT 合并答案,就可以保证 $ 10^{23} $ 内的精度。

| Modulo | Primitive Root |
|-|:-|
|998244353|3|
| 1004535809 | 3 |
| 46976204 | 3 |
| 9985661441=235*2^22+1 | 3 |

Using Imaginary up

记 $ P(x)=A(x)+iB(x), Q(x)=A(x)-iB(x) $ . 并令

$$ \begin{align} F_p[k]&=\sum_{j=0}^{2L-1}A_j\omega_{2L}^k+iB_j\omega_{2L}^k \\ &= \sum_{j=0}^{2L-1}(A_j+iB_j)(\cos X+i\sin X) \end{align} $$

$$ \begin{align} F_q[k]&=\sum_{j=0}^{2L-1}A_j\omega_{2L}^k-iB_j\omega_{2L}^k \\ &= \text{conj}\left(\sum_{j=0}^{2L-1}(A_j\cos X+B_j\sin X)+i(-A_j\sin X+B_j\cos X) \right) \\ &= \text{conj}(F_p[2L-k]) \end{align} $$

而注意到 $ \mathcal FA[k]={F_p[k]+F_q[k]\over2}, \mathcal F B[k] = i{F_p[k]-F_q[k]\over2} $ .

这样我们就将两次 DFT 减少为了一次。

Coefficient Separation

同样是用来解决任意模数或者大数统计的问题。比起三模数 NTT 快到不知道哪里去。

记模数为 $ M $ ,且 $ M_0:=\lceil\sqrt M\rceil $ . 容易知道所有整数都可以表示成 $ x=k[x]M_0+b[x] $ 其中 $ k[x], b[x] \le M_0 $ .

那我们只需要对 $ k_A[x],b_A[x],k_B[x],b_B[x] $ 两两卷积即可求出答案。使用上虚部只需做 4 次。

Reference

[1] 毛啸: "再探快速傅里叶变换". In: 2016年信息学奥林匹克中国国家候选队员论文. 中国计算机学会.

标签: none

添加新评论