洛谷P3803 fft模板

1. 1. 1.只确定系数表示法 n n n多项式需要每个项的系数，从低项到高项依次写成向量形式，这是唯一确定多项式的向量。 r = [ a 0 , a 1 , . . . . . , a n ] r=[a_{0},a_{1},...,a_{n}] r=[a0,a1,...,an]，只能确定多项式 f ( x ) = a 0 a 1 x a 2 x 2 . . . a n x n f(x)=a_{0} a_{1}x a_{2}x^{2} ... a_{n}x^{n} f(x)=a0 +a1​x+a2​x2+...+an​xn。

此时计算一次 f ( x ) f(x) f(x)的时间复杂度是 O ( n ) O(n) O(n)。多项式相加结果即向量相加，复杂度为 O ( n ) O(n) O(n)，多项式相乘即向量相乘，时间复杂度是 O ( n 2 ) O(n^{2}) O(n2)。

等长度向量相乘的方法：

设向量 x = [ a 0 , a 1 , . . . , a n ] x=[a_{0},a_{1},...,a_{n}] x=[a0​,a1​,...,an​]与向量 y = [ b 0 , b 1 , . . . , b n ] y=[b_{0},b_{1},...,b_{n}] y=[b0​,b1​,...,bn​]相乘，得到的还是长度为 n n n的向量 z = [ c 0 , c 1 , . . . , c n ] z=[c_{0},c_{1},...,c_{n}] z=[c0​,c1​,...,cn​]， c k c_{k} ck​为 x , y x,y x,y中所有下标之和为 k k k的对的积的和，即 c k = ∑ i = 0 k a i b k − i c_{k}=\sum_{i=0}^{k}a_{i}b_{k-i} ck​=∑i=0k​ai​bk−i​。

2. 2. 2.点值表示法，唯一确定一个 n n n次的多项式需要 n + 1 n+1 n+1个点（可以理解为解 n + 1 n+1 n+1元方程需要 n + 1 n+1 n+1个方程，每一个点可以确定所有系数的一组关系，有 n + 1 n+1 n+1个系数，就是 n + 1 n+1 n+1元方程）。点是二维的，所以需要一对列表（此处非向量）来表示这个多项式，即 [ x 1 , x 2 , . . . , x n ] [x_{1},x_{2},...,x_{n}] [x1​,x2​,...,xn​]，与 [ y 1 , y 2 , . . . , y n ] [y_{1},y_{2},...,y_{n}] [y1​,y2​,...,yn​]就可以唯一确定。此时多项式相加依然满足 y y y直接相加，乘法直接相乘即可。此时多项式加减法的时间复杂度都是 O ( n ) O(n) O(n)。

满足方程 z n = 1 z^{n}=1 zn=1的复数解 z z z即 n n n次单位根。

性质 1 1 1：单位根的模一定是 1 1 1，并且 n θ = 2 k π n\theta=2k\pi nθ=2kπ

由欧拉定理 e i θ = c o s θ + i s i n θ e^{i\theta}=cos\theta+isin\theta eiθ=cosθ+isinθ可知，任意一个右式形式的复数都可以被写成左式的形式，同时注意到，右式的模 c o s 2 θ + s i n 2 θ = 1 \sqrt{cos^{2}\theta+sin^{2}\theta=1} cos2θ+sin2θ=1 ​，这是一个长度为 1 1 1的向量的形式，更一般的，假设长度为 r r r，那么形式应是 r e i θ = r c o s θ + r i s i n θ re^{i\theta}=rcos\theta+risin\theta reiθ=rcosθ+risinθ的形式（在复平面， r r r即是向量的模， θ \theta θ是向量的辐角）。因此，设 z = r e i θ = r c o s θ + r i s i n θ ⇒ z n = r n e i n θ = r n c o s n θ + r n i s i n n θ = 1 ⇒ r n ( c o s n θ + i s i n n θ ) = 1 z=re^{i\theta}=rcos\theta+risin\theta\Rightarrow z^{n}=r^{n}e^{in\theta}=r^{n}cosn\theta+r^{n}isin n\theta=1 \Rightarrow r^{n}(cosn\theta+isin n\theta)=1 z=reiθ=rcosθ+risinθ⇒zn=rneinθ=rncosnθ+rnisinnθ=1⇒rn(cosnθ+isinnθ)=1，右式不存在有虚数，因此 s i n n n θ = 0 ⇒ n θ = 2 k π sin^{n}n\theta=0 \Rightarrow n\theta=2k\pi sinnnθ=0⇒nθ=2kπ，代入有 r n = 1 ⇒ r = 1 r^{n}=1\Rightarrow r=1 rn=1⇒r=1。

性质 2 ： n 2：n 2：n次单位根有 n n n个，并且第 k k k个单位根写作 w n k w_{n}^{k} wnk​，有 w n k = r e 2 π k n w_{n}^{k}=re^{2\pi\frac{k}{n}} wnk​=re2πnk​，单位根是从 0 0 0标号到 n − 1 n-1 n−1的。

注意到每个单位根与自己相乘就是让自己的辐角翻倍，因此，单位根是逆时针顺序在单位圆上排序的，间隔角度是 2 π / n 2\pi/n 2π/n，那么第 k k k个就是原命题的形式了。