0%

FFT

前置知识

复数域的运算,基础运算记号。

引入

FFT-快速傅里叶变换是一种能够快速实现 DFT 和 IDFT 的算法,常用于快速求多项式相乘。

简单来说,它先将多项式由系数表示法转换成点值表示法(多项式的多点求值),然后快速相乘,接着再由点值表示法转换回系数表示法(多项式的插值)。

点值表示法

一般我们见到的多项式都是由系数表示法来记录的,也就是用一个序列 \(\{a_n\}\),表示 \(a_0+a_1x+a_2x^2+\cdots\)

然而多项式还可以用点值表示法来记录,简单来说就是在函数图像上确定 \(n+1\) 个不同的点\(\{(x_1,y_1),(x_2,y_2),\cdots,(x_{n+1},y_{n+1})\}\)(不包含倍数点),可以证明对于 \(n\) 次的多项式,点集和多项式是唯一对应的。针对点集表示法的相乘非常简单,只要对应值相乘就好了,复杂度 \(O(n)\)。但是两种表示法之间的转换是个问题。

拉格朗日插值

拉格朗日插值是一种多项式插值(点值转系数表示)的方法。

给出 \(n\) 个点 \(P_i(x_i,y_i)\),将过这 \(n\) 个点的最多 \(n-1\) 次的多项式记为 \(f(x)\),求 \(f(k)\) 的值。

有:

\(f(x)\equiv f(a)\pmod {(x-a)}\)

这是显然的,因为 \(f(x)-f(a)=(a_0-a_0)+a_1(x-a)+a_2(x^2-a^2)+\cdots\),这个式子显然有 \((x-a)\) 这个因式,所以得证。

这样我们就可以列一个关于 \(f(x)\) 的多项式线性同余方程组:

\[ \begin{cases} f(x)\equiv y_1\pmod{(x-x_1)}\\ f(x)\equiv y_n\pmod{(x-x_2)}\\ \cdots\\ f(x)\equiv y_n\pmod{(x-x_n)} \end{cases} \]

我们根据中国剩余定理,有:

\[ M=\prod_{i=1}^n{(x-x_i)},m_i=\dfrac M{x-x_i}=\prod_{j\ne i}{(x-x_j)} \]

\(m_i\)\((x-x_i)\) 意义下的逆元就是:

\[ m_i^{-1}=\prod_{j\ne i}{\dfrac 1{x_i-x_j}} \]

所以就有:

\[ f(x)\equiv\sum_{i=1}^n{y_im_im_i^{-1}}\equiv\sum_{i=1}^n{y_i\prod_{j\ne i}{\dfrac {x-x_j}{x_i-x_j}}}\pmod M \]

所以在模意义下 \(f(x)\) 就是唯一的,即:

\[ f(x)=\sum_{i=1}^n{y_i\prod_{j\ne i}{\dfrac {x-x_j}{x_i-x_j}}} \]

这就是拉格朗日插值的表达式。

如果要将每一项的系数都算出来,时间复杂度仍为 \(O(n^2)\),但是本题中只用求出 \(f(k)\) 的值,所以在计算上式的过程中直接将 \(k\) 代入即可。

\[ f(k)=\sum_{i=1}^{n} y_i\prod_{j\neq i }\frac{k-x_j}{x_i-x_j} \]

本题中,还需要求解逆元。如果先分别计算出分子和分母,再将分子乘进分母的逆元,累加进最后的答案,时间复杂度的瓶颈就不会在求逆元上,时间复杂度为 \(O(n^2)\)