posted on 2022-08-02 23:57:12 | under 模板 | source
膜拜，抄写
problem
\[c_k=\sum_{i+j=k}a_ib_j. \]\(a,b\) 已知，要求 \(O(n\log n)\)。
prework：复数
定义
初中数学中 Soso 教我们说负数没有平方根，我们发现这是错误的，并在高中数学书中给负数的平方根下了定义：复数。
一个复数 \(z=a+bi\) 其中 \(i=\sqrt{-1}\)。好的我们并不关心复数的代数意义，更不关心 \(i\) 是什么，我们研究一下几何意义。
我们可以把 \(z=a+bi\) 当作平面直角坐标系（这时它升级成复平面）中的一个点 \((a,b)\)，更离谱的把它当作一个向量 \((a,b)\)，这三者是一一对应的。
我们可以定义这个复数的模长 \(|z|=\sqrt{a^2+b^2}\) 为它到原点的距离，和向量一模一样。
它的辐角为 \(\theta=\arctan(b/a)\)，与 \(x\) 轴的夹角（\(x\) 轴转到 \(z\) 的角），与向量一模一样。
运算法则
加减法：\((a_1+b_1i)\pm(a_2+b_2i)=(a_1\pm a_2)+(b_1\pm b_2)i\)。满足平行四边形法则。
乘法：这里和向量有点区别，复数乘复数还是复数，我们首先看代数意义：
\[(a_1+b_1i)\cdot(a_2+b_2i)=(a_1a_2-b_1b_2)+(a_1b_2+a_2b_1)i. \]然后是几何意义：模长相乘，辐角相加。（重要）
除法丢个式子吧：
\[(a_1+b_1i)/(a_2+b_2i)=\frac{(a_1+b_1i)(a_2-b_2i)}{(a_2+b_2i)(a_2-b_2i)}=\frac{(a_1a_2+b_1b_2)+(-a_1b_2+a_2b_1)i}{a_2^2+b_2^2}=\frac{(a_1a_2+b_1b_2)}{a_2^2+b_2^2}+\frac{-a_1b_2+a_2b_1}{a_2^2+b_2^2}i. \]共轭复数
一个复数 \(z=a+bi\) 的共轭复数为 \(\overline{z}=a-bi\)（实部不变，虚部取反）。
若 \(|z|=1\)，这时它与它的共轭复数互为倒数。证明：在单位圆上绕了一圈回来。
单位圆、单位根
将复平面上的一个单位圆等分成 \(n\) 份，记其中一份为 \(w_n=(\cos\frac{2\pi}{n},\sin\frac{2\pi}{n})\)。我们贺个图吧：
图中 \(w2,w3\) 代表 \(w_8^2,w_8^3\)，请注意这里 \(w_8^2=(w_8)^2\)，为什么呢？你乘了两次，在几何意义上转了两次，就是两份。同理一共有 \(8\) 份。
我们寻找一些重要性质：
- \(w_n^0=w_n^n=1\)：转回来了。
- \(w_n^k=w_{2n}^{2k}\)：在分为 \(2n\) 份的圆上一次跳两步。
- \(w_n^k=-w_n^{k+n/2}\)：转了半圈转到相反数。
prework：多项式乘法
两个多项式 \(a,b\) 按照代数意义相乘，有什么好的做法吗？
一种做法是，找到 \(n\) 个值 \(x_0,x_1,x_2,\cdots\) 代入 \(a,b\) 求值，将这两个多项式的值对应位相乘，再反演回去。
为什么正确呢？因为 \(n\) 个点能唯一插出一个 \(n\) 次多项式，反过来也如此。
这就是所谓的系数表示法和点值表示法的互换。注意到点值表示法相乘为 \(O(n)\)，我们可以试图优化一下两种方法之间的互换。
离散傅里叶变换：DFT
铺垫这么久我们还是不会多项式乘法，怎么办呢？
伟大的数学家傅里叶在 \(a,b\) 中代入了 \(n\) 个 \(n\) 次单位根，并说这有很好的性质，我们开始研究这有什么性质。
快速傅里叶变换：FFT
我们就只看一个多项式 \(F(x)\)，现在要代入 \(n\) 个单位根求值。
将 \(F\) 按下标奇偶分为两类：例如 \(F(x)=f_0x^0+f_1x^1+f_2x^2+f_3x^3+\cdots\)，我们拆成 \(F_0(x)=f_0x^0+f_2x^1+f_4x^2+\cdots\) 和 \(F_1(x)=f_1x^0+f_3x^1+f_5x^2+\cdots\)。那么 \(F(x)=F_0(x^2)+xF_1(x^2)\)。
我们递归下去，假设我们已知 \(F_0(w_{n/2}^0),F_0(w_{n/2}^1),\cdots,F_0(w_{n/2}^{n/2-1})\) 与 \(F_1(w_{n/2}^0),F_1(w_{n/2}^1),\cdots,F_1(w_{n/2}^{n/2-1})\).
考虑 \(F(w_n^k)\)，其中 \(0\leq k<n/2\)，我们开始利用信息：
\[\begin{aligned} F(w_n^k)&=F_0((w_n^k)^2)+w_n^k\cdot F_1((w_n^k)^2)\\ &=F_0(w_n^{2k})+w_n^k\cdot F_1(w_n^{2k})\\ &=F_0(w_{n/2}^k)+w_n^k\cdot F_1(w_{n/2}^k)\\ \end{aligned}\]这些东西都求过了可以直接用，那么 \(k\geq n/2\) 呢？
\[\begin{aligned} F(w_n^{k+n/2})&=F_0((w_n^{k+n/2})^2)+w_n^{k+n/2}\cdot F_1((w_n^{k+n/2})^2)\\ &=F_0(w_n^{2k+n})+w_n^{k+n/2}\cdot F_1(w_n^{2k+n})\\ &=F_0(w_{n/2}^{k+n/2})-w_n^k\cdot F_1(w_{n/2}^{k+n/2})\\ &=F_0(w_{n/2}^k)-w_n^k\cdot F_1(w_{n/2}^k)\\ \end{aligned}\] 标签：cdot,多项式,FFT,cdots,1b,复数,2i,模板 From： https://www.cnblogs.com/caijianhong/p/template-fft.html