【概念】
点值：给定多项式 \(f(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}\) 和 \(x_1\sim x_m\)，求 \(f(x_1),f(x_2),\dots,f(x_m)\)。（\(m=n\)）
求点值的算法一般是 \(O(n^2)\) 的，但对于特殊的多项式，可以做到更快。
插值：给定 \((x_0,y_0),(x_1,y_1),\dots,(x_{n-1},y_{n-1})\)，其中 \(x_0\sim x_{n-1}\) 互不相同。求一个不超过 \(n-1\) 次的多项式 \(f(x)\)，使得 \(f(x_i)=y_i\)。可以观察到 \(f(x)\) 是存在且唯一的。
求插值的算法一般是拉格朗日插值，令多项式 \(P_i(x)=\dfrac{\displaystyle\prod_{j=0,j\neq i}^{n-1}(x-x_j)}{\displaystyle\prod_{j=0,j\neq i}^{n-1}(x_i-x_j)}\)。
容易观察到 \(P_i(x_i)=1,P_i(x_j)=0\text{（j 不等于 i）}\)。
则 \(f(x)=\displaystyle\prod P_i(x_i)\cdot y_i\)。这证明了 \(f(x)\) 是存在的。
下证唯一性。若有两个多项式 \(f(x),g(x)\) 均满足要求。
考虑 \(r(x)=f(x)-g(x)\)，则 \(r(x)\) 在 \(x_0\sim x_{n-1}\) 处值为 \(0\)。
\(r(x)\) 是 \(n-1\) 次多项式，却有 \(n\) 个不相同的根，所以 \(r(x)=0\)，所以 \(f(x)=g(x)\)。
【单位根的性质】
\(n\) 次单位根是所有满足 \(z^n=1\) 的 \(z\) 们。
考虑复数，记 \(n\) 次单位根们为 \(\varepsilon_n\)。（即在复单位圆上从 \(0i+1\) 逆时针转 \(\dfrac{360°}{n}\) 得到的复数）
因为单位根的定义，所以 \(\varepsilon_n^{0\sim n-1}\) 都满足 \(z^n=1\)，所以他们刚好构成 \(z^n=1\) 的所有解。
还有一个性质：\(\varepsilon_{n}^{k}=e^{i\cdot \frac{2\pi}{n}\cdot k}=\cos \dfrac{2\pi k}{n}+i\cdot \sin \dfrac{2\pi k}{n}\)。
复数的折半定理：\(\varepsilon_{2n}^{2i}=\varepsilon_n^{i}\)。
【FFT：快速傅里叶变换】
考虑这样一个问题：给定 \(f(x),g(x)\)，求 \(h(x)=f(x)\cdot g(x)\)。
多项式的乘积，其实就是系数的卷积。所以 FFT 解决的是卷积的问题。
令 \(n=\deg f(x) + \deg g(x) + 1\)，显然 \(\deg h(x)<n\)。
如果直接循环做，是 \(O(n^2)\) 的；但是 FFT 能做到 \(O(n\log n)\)。
为了确定 \(h(x)\)，只需要 \(h\) 在 \(n\) 个点 \(x_0\sim x_{n-1}\) 上的值即可。
基本思路是：① 求出 \(f(x_0)\sim f(x_{n-1})\)。 ② 求出 \(g(x_0)\sim g(x_{n-1})\)。 ③ \(h(x_i)=f(x_i)\cdot g(x_i)\) ④ 插值还原 \(h\)。
拉格朗日插值也是 \(O(n^2)\) 的，所以我们要用更快的插值方式，后面会说到。
这里我们取 \(x_i=\varepsilon_{n}^{i}\)。
（当 \(x_i\) 取单位根时，点值称作 DFT，插值称作 IDFT）
-
求 \(f(x)\) 在 \(\varepsilon_{n}^{0\sim n-1}\) 的值。
我们用分治的思路解决这个问题。但在这之前，我们假定 \(n\) 是二的幂。如果 \(n\) 不是二的幂，补若干个 \(0\) 系数使 \(n\) 是二的幂。
\[f(x)=a_0x^0+a_1x^1+\cdots+a_{n-1}x^{n-1} \]定义 \(f^{(0)}(x)=a_0x^0+a_2x^1+a_4x^2+\cdots+a_{n-2}x^{(n-2)/2}\)。
定义 \(f^{(1)}(x)=a_1x^0+a_3x^1+a_5x^3+\cdots+a_{n-1}x^{(n-2)/2}\)。
观察到 \(f(x)=f^{(0)}(x^2)=x\cdot f^{(1)}(x^2)\)。问题转化为计算 \(f^{(0)}(x)\) 和 \(f^{(1)}(x)\) 在 \(\varepsilon_{\frac{n}{2}}^{0\sim \frac{n}{2}-1}\) 的值（求平方项的值）。
（折半定理：\(\varepsilon_n^2=\varepsilon_{\frac{n}{2}}^{1}\)，除以 \(2\) 后再对 \(n/2\) 取模）
于是可以递归 \(f^{(0)}(x),f^{(1)}(x)\) 求解。则 \(f(x)\) 在 \(\varepsilon_n^k\) 的点值 \(y(\varepsilon_n^k)=y^{(0)}(\varepsilon_{\frac{n}{2}}^{k\bmod \frac{n}{2}})+\varepsilon_n^ky^{(1)}(\varepsilon_{\frac{n}{2}}^{k\bmod \frac{n}{2}})\)。可以 \(O(n)\) 求得。
-
求 \(g(x)\) 的点值。与上同理。
-
插值还原 \(h(x)\)。也同样采取递归的思路。
这里引入矩阵的角度理解点值。（\(\varepsilon_n^0=1\)）
\[\begin{bmatrix} y_0\\ y_1\\ y_2\\ y_{i}\\ y_{n-1}\\ \end{bmatrix}= \begin{bmatrix} 1&1&1&\cdots&1\\ 1&\varepsilon_n^1&\varepsilon_n^2&\cdots&\varepsilon_n^{n-1}\\ 1&\varepsilon_n^2&\varepsilon_n^4&\cdots&\varepsilon_n^{2(n-1)}\\ 1&\varepsilon_n^i&\varepsilon_n^{2i}&\cdots&\varepsilon_n^{i(n-1)}\\ 1&\varepsilon_n^{n-1}&\varepsilon_n^{2(n-1)}&\cdots&\varepsilon_n^{(n-1)(n-1)}\\ \end{bmatrix} \cdot \begin{bmatrix} a_0\\ a_1\\ \vdots\\ a_{n-1}\\ \end{bmatrix} \]记等号左边列向量为 \(\vec{Y}\)，矩阵为 \(V_n\)，右侧列向量为 \(\vec{A}\)。观察到 \(V_n[i][j]=\varepsilon_n^{i\cdot j}\)（编号从 \(0\) 开始）。
\(\vec{Y}=V_n\cdot \vec{A}\)。插值就是已知 \(\vec{Y}\) 求 \(\vec{A}\)，即求 \({V_n}^{-1}\)。那 \(V_n\) 的逆 \(V_n^{-1}\) 是什么呢？
形式也很简单：\({V_n}^{-1}[i][j]=\dfrac{1}{n}\cdot \varepsilon_n^{-i\cdot j}\)。编号也是从 \(0\) 开始。
验证的话只要证明他俩相乘等于单位矩阵（对角线 \(1\) 其余 \(0\)）。
观察到 \(V_n\) 和 \(V_n^{-1}\) 就是把每一个 \(\varepsilon\) 都换成了他的共轭。类似点值的递归公式 \(y(\varepsilon_n^k)=y^{(0)}(\varepsilon_{\frac{n}{2}}^{k\bmod \frac{n}{2}})+\varepsilon_n^ky^{(1)}(\varepsilon_{\frac{n}{2}}^{k\bmod \frac{n}{2}})\)，可以写出插值的递归公式 \(a(\varepsilon_n^{-k})=a^{(0)}(\varepsilon_{\frac{n}{2}}^{-k\bmod \frac{n}{2}})+\varepsilon_n^{-k}a^{(1)}(\varepsilon_{\frac{n}{2}}^{-k\bmod \frac{n}{2}})\)。
递归的写法常数巨大。但这个过程其实可以用非递归实现。观察我们递归时哪些值被处理。
（注意每次不是分首尾两半而是奇偶两半）
发现了吗？最下面一层的二进制数如果从右往左读，刚好是 \(0\sim 2^n-1\)。
还有一个优化：上面我们对 \(f,g\) 做了两次 DFT，对 \(h\) 做了一次 IDFT，共三次。但是如果 \(f,g\) 的系数都是实数，其实可以只做两次。
摘自知乎。
至此，FFT 的算法介绍完毕。
【FFT 应用】
大整数乘积
一个 \(n\) 位的整数其实可以看作是 \(n-1\) 次多项式的 \(x\) 取 \(10\) 的结果。两个整数的乘积也可以看作是两个多项式的卷积。
合法平行四边形
题意：
考虑一个合法的平行四边形，将它补全成一个正方形。
则它的面积可以表示为 \((a+c)(b+d)-ac-bd=ad+bc=n\)。问题即求有多少个四元组 \(a,b,c,d\in\mathbb{Z_+}\) 且 \(ad+bc = n\)。
令 \(s_i\) 为 \(i\) 的因数个数。枚举 \(ad\) 和 \(bc\)，\(a,d\) 的组数就是 \(s_{ad}\)，\(b,c\) 的组数就是 \(s_{bc}\)。
所以 \(f(n)=\displaystyle\sum_{i+j=n}s_i\cdot s_j\)，即 \(f\) 是 \(s\) 的卷积。
力
把很像卷积的形式变成标准卷积：考虑拆开两半，一半标准形式，另一半对称地求。
给出 \(n\) 个数 \(q_1,q_2, \dots q_n\)，定义
\[F_j~=~\sum_{i = 1}^{j - 1} \frac{q_i \times q_j}{(i - j)^2}~-~\sum_{i = j + 1}^{n} \frac{q_i \times q_j}{(i - j)^2} \]\[E_i~=~\frac{F_i}{q_i} \]对 \(1 \leq i \leq n\)，求 \(E_i\) 的值。
可以理解 \(q_1\sim q_n\) 为 \(n\) 个排成一排的电荷。\(F_j\) 就是根据万有引力公式算出的其他电荷对 \(j\) 电荷的合力。
\(E_j=\displaystyle\sum_{i<j}\dfrac{q_j}{(i-j)^2}-\sum_{i>j}\dfrac{q_j}{(i-j)^2}\)。怎么转化为卷积的形式？
定义
\[d_k=\begin{cases}\dfrac{1}{k^2}&k>0\\0&k=0\\-\dfrac{1}{k^2}&k<0\\ \end{cases} \]\(E_j=\sum_{i<j}q_i\cdot d_{j-i}+\sum_{i>j}q_i\cdot d_{j-i}=\sum_{i}q_i\cdot d_{j-i}\)。
但这不是标准卷积的形式，因为这里的 \(i\) 可以 \(>j\)，标准形式是不能 \(>j\) 的。这里有两种解法。
法一：考虑平移。
令 \(E'_{j+n}=E_j,d'_{k+n}=d_k,q_{i|i>n}=0\)。
则 \(E'_{j+n}=\sum_{i=1}^{j+n}q_i\cdot d'_{j-i+n}\)，是标准卷积形式。
法二：考虑对称。
令 \(U_j=\sum_{i<j}q_i\cdot d_{j-i},V_j=\sum_{i>j}q_i\cdot d_{i-j}\)。
\(U_j\) 是标准卷积形式，但是 \(V_j\) 中 \(i>j\)，不是标准形式。
考虑 \(V,q\) 进行翻转。\(V_i'=V_{n+1-i},q_i'=q_{n+1-i}\)。则 \(V_j'=\sum_{i<j}q_i\cdot d_{j-i}\)，是标准形式。
Super Rooks on Chessboard
普通的车能控制所在行列；超级车除此之外，还能控制所在的主对角线（左上-右下的对角线）。
棋盘 \(r\) 行 \(c\) 列，有 \(n\) 个超级车，超级车的位置预先给出。问：有多少个格子不被控制。
FFT + 容斥。
先反过来，求有多少个格子被至少一个控制到。
令 \(R\) 表示所有被同行的车控制的格子的集合，\(C\) 表示所有被同列的车控制的格子的集合，\(D\) 表示所有被主对角线的车控制的格子的集合。
即求 \(|R\cup C\cup D|=|R|+|C|+|D|-|R\cap C|-|R\cap D|-|C\cap D|+|R\cap C\cap D|\)。
难点在于求 \(|R\cap C\cap D|\)。
标签：varepsilon,frac,cdot,FFT,插值,NTT,笔记,卷积,sim From： https://www.cnblogs.com/FLY-lai/p/18132488