序言
這篇文章是自己看的，外面有這麼多優秀的部落格多好。
這是我在複賽前那個暑假的一個噩夢。。。最終我還是花了一天時間搞出來了，這說明我天賦一般，雖然即使說明了我天賦一般也沒有什麼用。。該幹啥還是得幹啥。其實天賦沒啥用的，真正的是方法什麼的比較重要，以及平時各種能力的積累，最終展現在天賦上，也就是說天賦是可以改變的，天賦和智商差距應該還是蠻大的。我在說啥。。。。。
感謝很多優秀的部落客帶來的優秀的文章，感謝同機房的yyn帶了了符合我們機房風格的代碼闆子。。。。
FFT/NTT是幹嘛的？
FFT中文叫做快速傅裡葉變換。
就是在O(nlogn)的時間裡面求出多項式乘法，如果硬乘的話是O(n^2).
當然還有一個作用就是求卷積，在O(nlogn)求出f(1)~f(n)，其中f(i)=sum{g(j)*g(k-j),0<=j<=i},不會卷積沒有關系的，大概看一下定義就行了，多項式乘法的實質其實也算是個卷積吧。
至于做題的話一個是優化多項式乘法，一個是求卷積形式的數學題，一般來說就是推公式推出卷積形式就套模闆吧，
此外，這個真的就是個闆子，是以即使有些細節無法了解，隻要背下來問題也就不大了。
NTT中文叫做快速數論變換。
NTT基本上和FFT差不多，代碼結構基本上完全一樣，NTT對于有mod的，會比較快而且沒有精度誤差，因為它是建立在整數上的情況而不是FFT建立在複數的情況。
FFT原理
注：我們這裡按照多項式乘法來了解
優化原理
我們是用什麼方法是的O(n^2)的算法變成了O(nlogn)的呢？
首先我們需要知道，多項式有兩種表示方法，系數表示法和點值表示法，系數表示法就是直接記錄系數，點值表示法就是帶入n個不同值的點，得到答案，也就是n項的多項式用n個(x,y)表示（n個方程解n個系數嘛）。
是以我們有一種叫做DFT的變換可以使得系數表達式通過O(nlogn)的時間變成點值表達式，然後點值表達式O(n)就能做完乘法，又可以用幾乎相同的方法在O(nlogn)的時間裡面變成系數表達式，最終就完成了時間複雜度O(nlogn)的做法。
當然這隻是個意思，實際上肯定還是有很多數學技巧的。
實作原理
wn的遞推是第一個用三角形式，後面的用指數形式。
A(x)=a0+a1∗x+a2∗x2+a3∗x3+a4∗x4+a5∗x5+⋯+an−2∗xn−2+an−1∗xn−1 $
A1(x)=a0+a2∗x+a4∗x2+⋯+an−2∗xn/2−1
A2(x)=a1∗x+a3∗x+a5∗x2+⋯+an−1∗xn/2−1
A(x)=A1(x^2)+x*A2(x ^2)
大概就是這個意思，加上機關複數根的一些性質，加上蝴蝶變換模仿遞歸操作,記住代碼就好了。
其中x^2經過遞歸剛剛符合，wn(k,n)=-wn(k+n/2,n),是以一個加一個減
最後逆變換是用了一個矩陣思想，反矩陣，主要答案要/n;
一些操作
分治FFT
FFT可以完全看作乘法運算（比如它用來優化高精度乘法，而高精度乘法本身就是卷積運算），隻不過是對于一個數組（多項式）進行操作。
是以有時候遇到快速幂的形式是可以用快速幂來做的。
循環卷積
有時候要把f[n]的值算作f[n%m]的值，那麼累加上去即可,比如bzoj4827 [Hnoi2017]禮物
具體來說就是比如正常的是a1 * bn + a2 * bn-1+..
然後你要a1* b1+ a2 * bn +a3 * bn-1+…
序列反轉
a1 *b1+ a2 *b2+…
把b序列反轉了就變成了卷積形式
代碼
遞歸處理應該比較好了解，然後看非遞歸，我們通過觀察發現在遞歸處理一些元素之後原來的第i個元素，新下标恰好是i在二進制下的反轉，是以我們通過實作預處理初最終位置來進行非遞歸，這一部也叫做蝴蝶變換，因為叉過來叉過去的很像蝴蝶嘛。
FFT
BZOJ2179 FFT（A*B）
#include<cmath>
#include<queue>
#include<cctype>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=+;
const double pi=acos(-);
struct Complex
{
double x,y;
Complex(){};
Complex(double _x,double _y){x=_x,y=_y;};//注意這裡的幾個指派操作
friend Complex operator+(Complex a,Complex b)
{
return Complex(a.x+b.x,a.y+b.y);
}
friend Complex operator-(Complex a,Complex b)
{
return Complex(a.x-b.x,a.y-b.y);
}
friend Complex operator*(Complex a,Complex b)//(a+bi)*(c+di)=ac+bd*i^2+(ad+bc)i=(ac-bd,(ab+bc)i)
{
return Complex(a.x*b.x-a.y*b.y , a.x*b.y+a.y*b.x);
}
}a[maxn],b[maxn];
int m,n;
int r[maxn],l;
/*
雖然根據我的理論來說兩個多項式翻轉的乘積=兩多項式乘積的翻轉，但實際上并沒有什麼用
因為我們可以高位補0而能是低位補0，是以我們不能簡單做到完全翻轉（或者懶得做，并沒有得到友善)
*/
void ins(Complex *a,int n)
{
char c;
while(c=getchar(),c<'0');
for(int i=n-;i>=;i--)
{
a[i]=Complex(c^,);
c=getchar();
}
}
//我們系數和點值都直接用複數來存，理想的話存系數的時候虛部為0
void FFT(Complex *c,int f)
{
for(int i=;i<n;i++)if(i<r[i])swap(c[i],c[r[i]]);//為了防止兩次交換，是以用一個i<r[i]
for(int i=;i<n;i<<=)//表示準備去合并區間長度為i的
{
Complex wn(cos(pi/i),sin(f*pi/i)),x,y;//這是根據定義來的，目前區間長2i,2pi/2i=pi/i
//本來pi都應該取負的，但是cos(-a)=cos(a),是以隻加一個
for(int j=;j<n;j+=(i<<))//目前被合并的區間開始下标，因為合并了兩個區間，是以j+=(i<<1)
{
Complex w(,);
for(int k=;k<i;k++,w=w*wn)//在區間内部搞合并,根據平面複數根的幂形式推出w
{
x=c[j+k],y=w*c[i+j+k];//j+k,i+j+k這兩個位置隻需要這兩個位置填，是以剛剛好
//根據f(x)=f1(x)+x*f2(x),是以y要*w
c[j+k]=x+y,c[i+j+k]=x-y;//根據 wk+n/2=-wk，是以後面那個是-
}
}
}
if(f==-)for(int i=;i<n;i++)c[i].x/=n,c[i].y/=n;
//根據我們逆矩陣的求法，系數為原來n倍，是以‘點值->系數’的時候需要/n
}
int d[maxn];
int main()
{
//為了友善和符合多項式規範以及資料特征，n位整數标成0~n-1
scanf("%d",&m);
ins(a,m);
ins(b,m);
m=*m-;//兩個多項式乘積的長度是len1+len2-1
for(n=;n<m;n<<=)l++;//n是真實長度，為了友善就讓多項式都弄成n，本來單獨的多項式沒這麼長
//也就是說，基本上接下來所有操作都是基于n的，但是不要忘了範圍是0~n-1
for(int i=;i<n;i++)r[i]=(r[i>>]>>)|((i&)<<(l-));
//遞歸/DP求二進制翻轉，大概就是前n-1位翻轉，位移，根據i補位，運算複雜不要忘了括号
FFT(a,);//系數->點值
FFT(b,);//系數->點值
for(int i=;i<n;i++)a[i]=a[i]*b[i];//點值->點值
FFT(a,-);//點值->系數
for(int i=;i<n;i++)
{
d[i]+=(int)(a[i].x+);//誤差操作必須要有的,但實際上誤差沒有大到十分位，也不小
d[i+]+=d[i]/,d[i]%=;
}
for(int i=n;i>=;i--)
if(d[i])
for(;i>=;i--)
putchar(d[i]^);
putchar('\n');
return ;
}
NTT
對于需要取mod的情況，FFT并不适用，而且有較大的精度誤差，由于複數而造成的較大常數，是以找到了一個替換機關複數根的東西，就是原根，原根的求法在另外一篇部落格裡面提高過，其它的基本上和FFT相同。
特殊的，對于插值過程，複數的快速幂不好求，可以在最後反轉序列，雖然我也不知道為什麼，版子而已。
BZOJ 4555 [Tjoi2016&Heoi2016]求和（并沒有加注釋版）
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=+,mod=;
int n,lim,l,r[maxn<<];
LL f[maxn],g[maxn],h[maxn];
LL qkpow(LL a,LL p)
{
LL t=,tt=a%mod;
while(p)
{
if(p&)t=t*tt%mod;
tt=tt*tt%mod;
p>>=;
}
return t;
}
void Init()
{
LL tmp=;
g[]=,h[]=;
for(int i=;i<=lim;i++)
{
tmp=tmp*i%mod;
g[i]=-g[i-]*qkpow(i,mod-)%mod;
h[i]=(qkpow(i,lim+)-+mod)%mod*qkpow(i-,mod-)%mod*qkpow(tmp,mod-)%mod;
}
h[]=lim+;
int k=lim*2;
for(n=;n<k;n<<=)l++;
for(int i=;i<n;i++)r[i]=((r[i>>]>>)|((i&)<<(l-)));
}
void NTT(LL *c,int f)
{
for(int i=;i<n;i++)if(i<r[i])swap(c[i],c[r[i]]);
for(int i=;i<n;i<<=)
{
LL wn=qkpow(,(mod-)/(i<<)),x,y;
for(int j=;j<n;j+=(i<<))
{
LL w=;
for(int k=;k<i;k++,w=w*wn%mod)
{
x=c[j+k],y=w*c[i+j+k]%mod;
c[j+k]=(x+y)%mod,c[i+j+k]=(x-y+mod)%mod;
}
}
}
if(f==-){
reverse(c+,c+n);
LL tmp=qkpow(n,mod-);
for(int i=;i<n;i++)c[i]=c[i]*tmp%mod;
}
}
LL ans;
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d",&lim);
Init();
NTT(g,);NTT(h,);
for(int i=;i<n;i++)f[i]=g[i]*h[i]%mod;
NTT(f,-);
LL t1=,t2=;
ans=f[];
for(int i=;i<=lim;i++)
{
t1=t1*2%mod;
t2=t2*i%mod;
ans=(ans+t1*t2%mod*f[i])%mod;
}
printf("%lld\n",ans);
return ;
}
沒有注釋的FFT
struct Complex
{
double x,y;
Complex(){};
Complex(double _x,double _y){x=_x,y=_y;};
friend Complex operator+(Complex a,Complex b)
{
return Complex(a.x+b.x,a.y+b.y);
}
friend Complex operator-(Complex a,Complex b)
{
return Complex(a.x-b.x,a.y-b.y);
}
friend Complex operator*(Complex a,Complex b)
{
return Complex(a.x*b.x-a.y*b.y , a.x*b.y+a.y*b.x);
}
}a[maxn],b[maxn];
int m,n;
int r[maxn],l;
void FFT(Complex *c,int f)
{
for(int i=;i<n;i++)if(i<r[i])swap(c[i],c[r[i]]);
for(int i=;i<n;i<<=)
{
Complex wn(cos(pi/i),sin(f*pi/i)),x,y;
for(int j=;j<n;j+=(i<<))
{
Complex w(,);
for(int k=;k<i;k++,w=w*wn)
{
x=c[j+k],y=w*c[i+j+k];
c[j+k]=x+y,c[i+j+k]=x-y;
}
}
}
if(f==-)for(int i=;i<n;i++)c[i].x/=n,c[i].y/=n;
}
int d[maxn];
int main()
{
scanf("%d",&m);
ins(a,m);
ins(b,m);
m=*m-;
for(n=;n<m;n<<=)l++;
for(int i=;i<n;i++)r[i]=(r[i>>]>>)|((i&)<<(l-));
FFT(a,);
FFT(b,);
for(int i=;i<n;i++)a[i]=a[i]*b[i];
FFT(a,-);
return ;
}