欧拉公式： e x i = c o s x i s i n x e^{xi}=cosx i~sinx exi=cosx isinx
当x取2π的时候 有
e π i = c o s 2 π i s i n 2 π = 1 e^{\pi i}=cos2\pi i~sin2\pi=1 eπi=cos2π isin2π=1
所以对于 x n = 1 x^n=1 xn=1
x x x 可能的一个解是 e 2 π i n \frac{e^{2\pi i}}{n} ne2πi
w n = e 2 π i n w_n=e^{\frac{2\pi i}{n}} wn=en2πi
那么解集是 w n k ∣ k ∈ [ 0 , n ) {w_n^k|k\in[0,n)} wnk∣k∈[0,n) (证明考虑欧拉公式） 别忘了是n次方，之所以范围是[0,n) 是因为等于n的时候 可以整体减去2π 答案不变
w n n = 1 w_n^n=1 wnn=1
有以下性质：
① w n k w_n^k wnk是互异的，保证用于插值的个数是对的
② w 2 n 2 k = w n k w_{2n}^{2k}=w_{n}^k w2n2k=wnk (一分两半值不变 可以分治)
③ w n n 2 + k = − w n k w_{n}^{\frac{n}{2}+k}=-w_n^k wn2n+k=−wnk （直角坐标系上单位圆） （前半可以推后半）
以上都是在fft求点值的过程中用的 最后还需要从点值变回系数
④ k ≠ 0 , ∑ i = 0 n − 1 ( w n k ) i = 0 k\neq0,\sum\limits_{i=0}^{n-1}(w_n^k)^i=0 k=0,i=0∑n−1(wnk)i=0 (感性理解 奇数次数和偶数次数相同)
两个复数相乘，模等于两个模相乘，辅角相加
具体来说 例如两个模是 a 2 + b 2 \sqrt{a^2+b^2} a2+b2 c 2 + d 2 \sqrt{c^2+d^2} c2+d2
那么新的模式 a 2 + b 2 × c 2 + d 2 \sqrt{a^2+b^2} \times \sqrt{c^2+d^2} a2+b2 ×c2+d2
逆矩阵里是取倒数
之所以FFT时 ab数组是对应位置相乘 原因在于 本质上ab相乘对应卷积没有实际含义，只是为了求逆的方便，因此对应位置相乘
写代码的时候之所以写的是 π / m i d \pi/mid π/mid 是因为本来应该是 ( 2 π ) / ( 2 m i d ) (2\pi)/(2mid) (2π)/(2mid) 刚好约一下
NTT的时候 则 g n k = x k ( p − 1 ) / n g_n^k=x^{k(p-1)/n} gnk=xk(p−1)/n,其中 n是长度，k是幂 p是质数，x是p的一个原根
NTT常用质数：998244353,469762049,1004535809 原根都是3
多项式开根
证明
当 a [ 0 ] ! = 1 a[0]!=1 a[0]!=1 的时候需要用二次剩余求出最后一个数
一句话总结
G ( x ) = F ( x ) + H 2 ( x ) 2 H ( x ) G(x)=\frac{F(x)+H^2(x)}{2H(x)} G(x)=2H(x)F(x)+H2(x)
多项式相加直接对应系数相加就好
注意 G ( x ) + 1 G(x)+1 G(x)+1 是把 G ( x ) G(x) G(x) 的常数位置+1，不是所有项都+1
多项式全家桶
牛顿迭代
G ( x ) = G ∗ ( x ) − F ( G ∗ ( x ) ) F ′ ( G ∗ ( x ) ) G(x)=G_*(x)-\frac{F(G_*(x))}{F'(G_*(x))} G(x)=G∗(x)−F′(G∗(x))F(G∗(x))
复合函数求导的链式法则
( F ( G ( x ) ) ) ′ = F ′ ( G ( x ) ) G ( x ) (F(G(x)))'=F'(G(x))G(x) (F(G(x)))′=F′(G(x))G(x)
F ( G ( x ) ) ′ F(G(x))' F(G(x))′ 是对整个复合函数求导 自变量是 x x x
F ′ ( G ( x ) ) F'(G(x)) F′(G(x)) 则相当于是对 F ( x ) F(x) F(x) 求了个导之后把 G ( x ) G(x) G(x) 代了进去
差卷积
对于 G [ k ] = ∑ i = k n ( − 1 ) ( i − k ) ( i − k ) ! F [ i ] G[k]=\sum\limits_{i=k}^n\frac{(-1)^{(i-k)}}{(i-k)!}F[i] G[k]=i=k∑n(i−k)!(−1)(i−k)F[i]
即 G [ k ] = A [ i − k ] B [ i ] G[k]=A[i-k]B[i] G[k]=A[i−k]B[i]
我们发现 k k k 这个位置会受到 2 i − k 2i-k 2i−k 的贡献
如果我们反一下
令 B ′ [ i ] = B [ n − i ] B'[i]=B[n-i] B′[i]=B[n−i]
那么 将 A ( x ) , B ′ ( x ) A(x),B'(x) A(x),B′(x) 做卷积
n − i 1 + i 2 n-i_1+i_2 n−i1+i2 会相当于原序列 B [ i 1 ] ∗ A [ i 2 ] B[i_1]*A[i_2] B[i1