噔 噔 噔。
你说的对，但是确实挺基础的说。
很多东西避开了严谨的描述。
文章内容非常浅（che）显（dan）。
prework
卷积 ：\(a，b\)为两个数列，两个数列的卷积 \(c\) 有 \(c_k=\sum\limits_{i=1}^{k} a_{i}b_{k-i}\)。
多项式的点值表示：\(n+1\) 个坐标确定一个 \(\le n\) 次的多项式，我们可以用这 \(n+1\) 个坐标表示。
注意到直接用点值表示出来的话，能快速的得到相乘的多项式的点值表示。
我们实际上是计算特殊的点值。
单位根：\(x^n-1 =0\) 我们称 \(x\) 为 \(n\) 次单位根，其中 $n \in \mathbb{C} $。我们设 $ \omega $，根据代数基本定理，它在复数集下显然有 \(n\) 个解。我们分别记最小解为 $ \omega_1，\omega_2，\omega_3 \ldots \omega_n$，实际上就是每个角为 \(\frac{2\pi}{n}\)，这个东西定义为 \(\omega_{n} = e^{\frac{2\pi i}{n}}\)
$ \because e^{i x } = \cos x+ i\sin x $(欧拉公式)
\(\therefore \omega_n = \cos \frac{2\pi}{n} + i\sin \frac{2\pi}{n}\)
FFT的推导过程
离散傅里叶变换（DFT）
是长这样的，\(a\)是一个数列，对于 \(0 \le k < n\)，我们令
\[ b_k=\sum\limits_{i=0}^{n-1} a_i \omega_n^{ki} \]我们记 \(b=F(a)\)
离散傅里叶变换的逆变换（IDFT）
顾名思义，直接给出式子
\[ a_k=\frac{1}{n}\sum\limits_{i=0}^{n-1} b_i \omega_n^{-ki}(0 \le k < n) \]证明有点长，大概就是根据定义去推。
意思就是说如果我们知道单位根的点值，就能推出原多项式的系数了。
循环卷积
有 \(a,b\) 两个数列，
\(c_k=\sum\limits_{i+j \mod n=k} a_{i}b_{k-i}\)
我们记作 $ c = a * b$
我们有一个性质 \(F(a*b)=F(a) \times F(b)\)
补充单位根的两个性质
Lemma 1:\(({\omega_{2n}}^k)^2={\omega_{n}}^k\)
Lemma 2:\({\omega_{2n}}^{n+k}={\omega_{2n}}^{-k}\)
你把复平面建立出来证明式容易的。
我们对多项式 \(A(x)\) 开始进行操作，我们记 \(n=2m\)。
\[A(x)=\sum\limits_{0\le i < n} a_ix^i = \sum\limits_{0\le i < m} a_{2i}x^{2i} +\sum\limits_{0\le i < m} a_{2i+1}x^{2i+1} \]\[=\sum\limits_{0\le i < m} a_{2i}x^{2i} +x \sum\limits_{0\le i < m} a_{2i+1}x^{2i} \]注意到有相同的，这是好事。
那我们定义\(A_0(x)=\sum\limits_{0\le i < m} a_{2i}x^{2i} ，A_1(x)= x\sum\limits_{0\le i < m} a_{2i+1}x^{2i}\)
蝴蝶变换
考虑将前面的东西结合一下？下面还是有 \(0 \le k < m\)
\[A(\omega{_n}^k) = A_0(\omega{_n}^k)+A_1(\omega{_n}^k) \]\[A(\omega{_n}^k) = A_0(({\omega_{2n}}^k)^2)+A_1(({\omega_{2n}}^k)^2) \]\[A(\omega{_n}^k) = A_0(({\omega_{n}}^k)^2)+ \omega{_n}^k A_1(({\omega_{n}}^k)^2) \]\[A(\omega{_n}^k) = A_0({\omega_{m}}^{k})+ \omega{_n}^k A_1({\omega_{m}}^{k}) \]\[A(\omega{_n}^{m+k}) = A_0(({\omega_{n}}^{m+k})^2)+ \omega{_n}^{m+k} A_1(({\omega_{n}}^{m+k})^2) \]\[A(\omega{_n}^{m+k}) = A_0({\omega_{m}}^{k})- \omega{_n}^k A_1({\omega_{m}}^{k}) \]通过蝴蝶操作的过程可以看出，如果我们得到了 \(A_0(x),A_1(x)\)
在点\({\omega_{m}}^0,{\omega_{m}}^1 \ldots {\omega_{m}}^{m-1}\)，我们可以在 \(O(n)\) 时间内
计算出 \(A(x)\) 在 \({\omega_{m}}^0,{\omega_{m}}^1 \ldots {\omega_{m}}^{m-1}\)，我们可以在 \(O(n)\)处的点值。
而计算 \(A_0,A_1\) 的点值的过程可以递归分治进行。
根据主定理，我们可以在 \(O(n\log n)\) 的时间内求出所要的 \(A(x)\) 的点值表示。
为了快速的进行 IDFT，对比 DFT与 IDFT的表达式，可以发
现我们只需要将FFT过程中用到的 \(\omega_{n}\) 全部替换为 \({\omega_{n}}^{-1}\)，最后再乘以 \(\frac{1}{n}\) 即可。
令 \(rev(x)\) 表示将x的二进制位的顺序反转之后得到的数字，我们每次 将 \(a_i = a_{rev(i)}\) 则每次需要对a进行的蝴蝶操作在a′中变成了对两个相邻的序列的操作。方便多了。我觉得你记忆模板就行。
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+6,mod=1e9+7,INF=2e9;
// 省略了缺省源，想看找我要就行了
struct CP{
db x,y;
CP(db X=0.0,db Y=0.0){x=X,y=Y;}
inline CP operator +(const CP &p){return CP(x+p.x,y+p.y);}
inline CP operator -(const CP &p){return CP(x-p.x,y-p.y);}
inline CP operator *(const CP &p){return CP(x*p.x-y*p.y,y*p.x+x*p.y);}
}f[N<<1],g[N<<1];
int rev[N<<1];
int n,m;
const db pi=acos(-1);
void FFT(CP *f,db opt){
rep(i,0,n-1) if(i<rev[i]) swap(f[i],f[rev[i]]);
for(int p=2;p<=n;p<<=1){
int len=(p>>1);
CP wd(cos(2*pi/p),sin(2*pi/p)*opt);
static CP w[N];
w[0]={1,0};
rep(i,1,len) w[i]=w[i-1]*wd;
for(int k=0;k<n;k+=p){
rep(l,k,k+len-1){
CP now=f[l+len]*w[l-k];
f[l+len]=f[l]-now,f[l]=f[l]+now;
}
}
}
}
int main(){
cin>>n>>m;
rep(i,0,n) cin>>f[i].x;
rep(i,0,m) cin>>g[i].x;
for(m+=n,n=1;n<=m;n<<=1);
rep(i,0,n) rev[i]=(rev[i>>1]>>1)|((i&1)?(n>>1):0);
FFT(f,1);FFT(g,1);
rep(i,0,n) f[i]=f[i]*g[i];
FFT(f,-1);
rep(i,0,m) cout<<(int)(fabs(f[i].x)/(n*1.0)+0.5)<<" ";
}
NTT
咕咕。
生成函数
一些题目
P1919 【模板】高精度乘法 | A*B Problem 升级版
注意到高精度乘法本身就是一个卷积，直接把每一位当系数卷积即可，要处理一下进位。
P3338[ZJOI2014]力
咕咕。
标签：,le,limits,sum,CP,omega,2i From： https://www.cnblogs.com/q1uple/p/18684373