标签： 循环卷积
-
再探 FFT – DIT 与 DIF，另种推导和优化
本文将简单推导两种方式进行的离散傅里叶变换，用另种视角解释并优化算法。参考了 Seniorious yhx-12243 的 NTT 到底写了些什么（详细揭秘） 一文、OI Wiki 快速傅里叶变换 条目 和 rushcheyo 转置原理及其应用 讲稿。
离散傅里叶变换
我们计算数列 $\{a_n\}$ 的离散傅里叶变换
$$
\newcommand\DFT{\operatorname{DFT}}\DFT(a,n)_k=\sum_{j=0}^{n-1}a_j\mathrm{e}^{\frac{-2\pi\mathrm{i}}{n}kj}
$$由卷积定理和循环卷积得到，我们对同样长为 $n$ 的数列 $\{b_n\}$ 作 $\DFT$，并令数列 $c_k=\DFT(a,n)_k\DFT(b,n)_k$，则有
$$
\newcommand\IDFT{\operatorname{IDFT}}\IDFT(c,n)_k=\sum_{j+q\equiv k\pmod n}a_jb_q
$$于是我们可以利用该原理实现常规意义下的数列卷积：有长为 $n$ 的数列 $\{a_n\}$，长 $m$ 的数列 $\{b_m\}$，则将 $a,b$ 高位补 $0$，分别作 $n+m-1$ 位的 $\DFT$，点值相乘后 $\IDFT$ 即可得到 $c_k=\sum_{i+j\equiv k\pmod{n+m-1}}a_ib_j=\sum_{\substack{i+j=k\\0\leq i<n\\0\leq j<m}}a_ib_j$。
为行文方便，下文采用 $\DFT(a,n)_k=\sum_{i=0}^{n-1}a_i\omega_n^{ik}$ 的定义，其中 $\omega_n=\exp(2\pi\mathrm{i}/n)$，即 $n$ 阶单位根。 （更多…）
-
分治FFT与循环卷积
给定数列 $g_{1\cdots n}$，求解满足如下形式的数列 $f$：$f_0=1,f_i=\sum_{j=0}^{i-1}f_jg_{i-j},\forall i \in \{1,2,\cdots,n\}$，对 $998244353$ 取模。
这道题可以通过多项式求逆解决。我们在此不作讨论。
考虑其转移形式，全部都是依赖于前序已求出项的、固定系数的线性转移。则可以考虑CDQ分治。如果你愿意，也可以叫作“分治FFT”。
假设正处理区间 $[l, r]$；令 $\text{mid}=\lceil (l+r)/2\rceil$，我们已经计算好 $f_{l,\cdots,\text{mid}}$。现统一处理左半区间对右半的贡献。
则令考虑的乘积项为 $f_i, i \in [l, \text{mid}]$，要向 $f_j, j \in (\text{mid}, r]$ 作贡献。有 $f_j \leftarrow g_{j-i}f_i$。故而对于 $i \in [l, \text{mid}]$，其将分别与 $g_{\text{mid}+1-l, \cdots, r-l}, g_{\text{mid}-l, \cdots, r-l-1}, \cdots, g_{1, \cdots, r-\text{mid}}$ 作卷积。其二者下标的和即为贡献对象。故而我们构造两个多项式 $F(x), G(x)$，有 $[x^i]F(x)=f_{i+l}, [x^j]G(x)=g_{j-1}$，将其二者作卷积，他们对 $f_j, j \in (\text{mid}, r]$ 的贡献即为 $[x^{j-l-1}]F(x)G(x)$。