任意模数 NTT 和 DFT 的优化
可能就存个板子，而且先咕了
来更了
参考 毛啸《再探快速傅里叶变换》
三模数 NTT
不说了
拆系数 FFT
描述
令 $M=2^{15}=32768$，对于需要卷积的数列 $A_i$ 和 $B_i$ 中的每个数 $x$，拆成 $x=k\times M+b$ 的形式
当长度是 $10^5$ ，模数在 $10^9$ 左右时，最大的数字大约在 $10^{14}$，单位根处理得好一点就不会爆 double 的精度
把 $A_i$ 拆出的两个数列和 $B_i$ 拆出的两个数列 DFT 后各选一个相乘，最终的系数分别是 $1,2^{15},2^{15},2^{30}$，相同的两项可以一起 IDFT
总共需要 7 次 DFT
已经挺快的了
代码
就是下面的模板题
1 |
|
DFT 的优化
描述
假设 $n$ 是 $2$ 的整数次幂，现在需要对长度为 $n$ 的多项式 $A(x)$ 和 $B(x)$ 进行 DFT，我们可以合并只做一次
做法
令
$$
\begin{align}
P(x)=A(x)+iB(x) \
Q(x)=A(x)-iB(x)
\end{align}
$$
设 $P’[k]$ 和 $Q’[k]$ 分别是 $P(x)$ 和 $Q(x)$ 进行 DFT 后的序列
有 $P’[k]=P(\omega_n^k),Q’[j]=Q(\omega_n^k)$，即代入 $n$ 次单位根的幂后的点值
推导直接拉了
令 $\text{conj}(x)$ 表示 $x$ 的共轭复数，$A_i$ 即 $A(x)$ 的 $i$ 次项系数
$$
\begin{align}
P’[k] &= A(\omega_{n}^{k}) + i B(\omega_{n}^{k}) \
& = \sum_{j=0}^{n-1} A_{j} \omega_{n}^{jk} + i B_{j} \omega_{n}^{jk} \
& = \sum_{j=0}^{n-1} (A_{j} + i B_{j}) \left(\cos \left(\frac{2 \pi jk}{n}\right) + i \sin \left(\frac{2 \pi jk}{n}\right)\right) \
\
Q’[k] &= A(\omega_{n}^{k}) - i B(\omega_{n}^{k}) \
& = \sum_{j=0}^{n-1} A_{j} \omega_{n}^{jk} - i B_{j} \omega_{n}^{jk} \
& = \sum_{j=0}^{n-1} (A_{j} - i B_{j}) \left(\cos \left(\frac{2 \pi jk}{n}\right) + i \sin \left(\frac{2 \pi jk}{n}\right)\right) \
& = \sum_{j=0}^{n-1} \left(A_{j} \cos \left(\frac{2 \pi jk}{n}\right) + B_{j} \sin \left(\frac{2 \pi jk}{n}\right)\right) + i \left(A_{j} \sin \left(\frac{2 \pi jk}{n}\right) - B_{j} \cos \left(\frac{2 \pi jk}{n}\right)\right) \
& = \text{conj} \left( \sum_{j=0}^{n-1} \left(A_{j} \cos \left(\frac{2 \pi jk}{n}\right) + B_{j} \sin \left(\frac{2 \pi jk}{n}\right)\right) - i \left(A_{j} \sin \left(\frac{2 \pi jk}{n}\right) - B_{j} \cos \left(\frac{2 \pi jk}{n}\right)\right) \right) \
& = \text{conj} \left( \sum_{j=0}^{n-1} \left(A_{j} \cos \left(\frac{-2 \pi jk}{n}\right) - B_{j} \sin \left(\frac{-2 \pi jk}{n}\right)\right) + i \left(A_{j} \sin \left(\frac{-2 \pi jk}{n}\right) + B_{j} \cos \left(\frac{-2 \pi jk}{n}\right)\right) \right) \
& = \text{conj} \left( \sum_{j=0}^{n-1} (A_{j} + i B_{j}) \left(\cos \left(\frac{-2 \pi jk}{n}\right) + i \sin \left(\frac{-2 \pi jk}{n}\right)\right)\right) \
& = \text{conj} \left( \sum_{j=0}^{n-1} (A_{j} + i B_{j}) \omega_{n}^{-jk} \right) \
& = \text{conj} \left( \sum_{j=0}^{n-1} (A_{j} + i B_{j}) \omega_{n}^{(n-k)j} \right) \
& = \text{conj} (P’[n-k])
\end{align}
$$
于是我们可以通过 $P(x)$ 得到 $Q(x)$
注意最后得到的 $n-k$ 是模 $n$ 意义下的，当 $k=0$ 时需要特殊处理
设 $A’[k]$ 和 $B’[k]$ 分别是 $A(x)$ 和 $B(x)$ 进行 DFT 后的序列
有
$$
\begin{align}
A’[k]=\frac{P’[k]+Q’[k]}{2} \
B’[k]=\frac{P’[k]-Q’[k]}{2i}
\end{align}
$$
通过这种方法可以用一次长度不变的 DFT 同时计算两个序列 DFT 后的结果
假设对 $P’[k]$ 进行了 IDFT，实部和虚部分别就是 $A(x)$ 和 $B(x)$ 了
单个 DFT 的优化
可以分奇次项和偶次项拆成两个序列，可以用一次原先一半长度的 DFT 来得到 DFT 的结果，我就不学了
update: 来学了
半次 DFT
DFT
考虑把多项式 $f(x)$ 的偶次系数和奇次系数分开得到两个一半长度的序列，当做多项式分别是 $f_0(x)$ 和 $f_1(x)$
于是
$$
\begin{align}
f(x) &= f_0(x^2)+x \times f_1(x^2) \
\
f(\omega_n^k) &= f_0(\omega_n^{2k})+\omega_n^k \times f_1(\omega_n^{2k}) \
&= f_0(\omega_{\frac{n}{2}}^k)+\omega_n^k \times f_1(\omega_{\frac{n}{2}}^k)
\end{align}
$$
我们把两个一半长度的多项式合并做 DFT，通过上式可以算出原多项式 DFT 的结果
IDFT
几乎是反的，用 $f(\omega_n^k)$ 和 $f(\omega_n^{k+\frac{n}{2}})$ 可以解出 $f_0(\omega_{\frac{n}{2}}^k)$ 和 $f_1(\omega_{\frac{n}{2}}^k)$
然后那样塞回一半长度的序列，做 IDFT 后实部和虚部分别就是偶次和奇次的系数了
实现可以参考 $3.5$ 次的模板
应用
在上面的拆系数 FFT 中可以优化到 $4$ 次或者所谓的 $3.5$ 次的 DFT
模板
代码
$4$ 次 DFT
1 |
|
$3.5$ 次 DFT
1 |
|
例题
贴代码，方便以后拉
多项式求逆
代码
1 |
|
传球
代码
1 |
|
Flair
LOJ #6132. 「2017 山东三轮集训 Day1」Flair
性质
令最大的两个数的乘积为 $a$，所有数的 $\gcd$ 为 $b$，选择了 $i$ 个的浪费是 $f_i$
对于 $i\ge a$ 有 $f_i=f_{i+b}$
那么我们做长度为 $b$ 的循环卷积快速幂，对于 $a$ 以内的特判就好了
考试的时候没带脑子
有些细节不管复杂度就是 $\mathcal O(b\log b\log n + m\times a)$
代码
1 |
|
任意模数 NTT 和 DFT 的优化