FFT：

沒啥好說的吧。。

證明應(yīng)該都會，寫的時候記住兩個點就行：

1.怎么定義復(fù)數(shù)？千萬別寫成

complex<double> w=(1,0);

可以自己試一下這樣輸出什么東西……

2.枚舉len，遍歷前一半，用原來的$a_{i},a_{i+len/2}$值計算新的$a_{i},a_{i+len/2}$值。

我覺得我還是解釋一下這么做的原因好一點。。

我們希望得到多項式$A(x)$在$w_{n}^{1},w_{n}^{2},cdots,w_{n}^{n}$處的點值表示。

而我們有$w_{n}^{k}=w_{frac{n}{2}}^{frac{k}{2}},w_{n}^{k+frac{n}{2}}=-w_{frac{n}{2}}^{frac{k}{2}}$。

那么把偶數(shù)下標的系數(shù)和奇數(shù)下標的系數(shù)分別拆出來組成兩個多項式$A_{0}(x)$和$A_{1}(x)$，則有

$A(w_{n}^{k})=A_{0}(w_{n}^{2k})+w_{n}^{k}A_{1}(w_{n}^{2k})=A_{0}(w_{frac{n}{2}}^{k})+w_{n}^{k}A_{1}(w_{frac{n}{2}}^{k})$

$A(w_{n}^{k+frac{n}{2}})=A_{0}(w_{n}^{2k})-w_{n}^{k}A_{1}(w_{n}^{2k})=A_{0}(w_{frac{n}{2}}^{k})-w_{n}^{k}A_{1}(w_{frac{n}{2}}^{k})$

那么我們可以先遞歸處理$A_{0}(x)$和$A_{1}(x)$，然后爆枚$k$，得到$A(x)$的$n$個點值。

這東西很像線段樹，倒數(shù)第$i$層的$n$是$2^{i}$，有$frac{n}{2^{i}}$個多項式需要爆枚$2^{i}$次。

每層爆枚的復(fù)雜度是$O(n)$，一共$log{n}$層，總復(fù)雜度$O(nlog{n})$。

發(fā)現(xiàn)位置$i$最終會被換到$i$的二進制位反過來的位置，于是可以不用遞歸，直接模擬線段樹上爆枚的過程即可。

強烈推薦偉大的石神給出的里程碑式的證明！

代碼：

#include<bits/stdc++.h>
#define maxn 3000005
#define maxm 500005
#define inf 0x7fffffff
#define ll long long
#define cp complex<double>
#define pi acos(-1)

using namespace std;
cp a[maxn],b[maxn],c[maxn];
int ind[maxn];

inline int read(){
    int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}

inline void fft(cp *t,int n,int op){
    for(int i=0;i<n;i++) ind[i]=(i&1)?((ind[i>>1]>>1)|(n>>1)):(ind[i>>1]>>1);
    for(int i=0;i<n;i++) if(ind[i]<i) swap(t[i],t[ind[i]]);
    for(int len=2;len<=n;len<<=1)
        for(int j=0;j<n;j+=len){
            cp w(1,0),p(cos(op*2*pi/len),sin(op*2*pi/len));
            for(int k=0;k<(len>>1);k++,w*=p){
                cp t1=t[j+k+(len>>1)],t2=t[j+k];
                t[j+k+(len>>1)]=t2-t1*w,t[j+k]=t2+t1*w;
            }
        }
    return;
}

int main(){
    int n=read(),m=read();
    for(int i=0;i<=n;i++) a[i]=read();
    for(int i=0;i<=m;i++) b[i]=read();
    int len=1; while(len<=n+m) len<<=1;
    fft(a,len,1),fft(b,len,1);
    for(int i=0;i<len;i++) c[i]=a[i]*b[i];
    fft(c,len,-1);
    for(int i=0;i<=n+m;i++) cout<<(int)(c[i].real()/len+0.5)<<" ";
    cout<<endl;
    return 0;
}

FFT

NTT：

原根的性質(zhì)與單位根一模一樣。只是$IDFT$的時候得求個逆元。

題里有模數(shù)就用$NTT$，沒有模數(shù)也盡量用$NTT$，避免出現(xiàn)時間精度雙爆炸的慘劇。

注意$w_{n}^{k}=g^{frac{mod-1}{n}cdot k}$，證明時將k分離出來考慮即可。

我還是證一下吧。。雖然這也不算是證明了。。

根據(jù)原根的性質(zhì)，有$g_{i}mod{p}$的值互不相同$(0leq i<p)$。

那么實際上$w_{n}^{k}=g^{frac{k}{n}}$，都滿足首尾值相等且中間值互不相同。

但是等一下，這個$frac{k}{n}$不是整數(shù)啊？

而且指數(shù)沒有同余定律，只有費馬小定理$a^{p-1}equiv apmod p$。

那我們只能取$n|(mod-1)$的$n$來做了，此時$g^{frac{k}{n}}=g^{frac{k(mod-1)}{n}}$。

現(xiàn)在我們就理解為什么$NTT$只能用形如$2^{k}+1$的模數(shù)了。

偉大的石神在剛才那篇里也更了$NTT$！

代碼：

#include<bits/stdc++.h>
#define maxn 3000005
#define maxm 500005
#define inf 0x7fffffff
#define ll long long
#define mod 998244353
#define g 3

using namespace std;
ll a[maxn],b[maxn],res[maxn],ind[maxn];

inline ll read(){
    ll x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}

inline ll power(ll a,ll b){ll ans=1;while(b)ans=(b&1)?ans*a%mod:ans,a=a*a%mod,b>>=1;return ans;}
inline void ntt(ll *t,ll n,ll op){
    for(ll i=0;i<n;i++) ind[i]=(i&1)?((ind[i>>1]>>1)|(n>>1)):(ind[i>>1]>>1);
    for(ll i=0;i<n;i++) if(ind[i]<i) swap(t[i],t[ind[i]]); 
    for(ll len=1;len<=n;len<<=1){
        ll p=power(g,(mod-1)/len);
        if(op==-1) p=power(p,mod-2);
        for(ll i=0;i<n;i+=len)
            for(ll j=i,w=1,tp;j<i+(len>>1);j++,w=w*p%mod)
                tp=t[j+(len>>1)]*w%mod,t[j+(len>>1)]=(t[j]-tp+mod)%mod,t[j]=(t[j]+tp)%mod;
    }
    return;
}

int main(){
    ll n=read(),m=read();
    for(ll i=0;i<=n;i++) a[i]=read();
    for(ll i=0;i<=m;i++) b[i]=read();
    ll len=1; while(len<=n+m) len<<=1;
    ntt(a,len,1),ntt(b,len,1);
    for(ll i=0;i<len;i++) res[i]=a[i]*b[i];
    ntt(res,len,-1);
    ll mo=power(len,mod-2);
    for(ll i=0;i<=n+m;i++) cout<<res[i]*mo%mod<<" ";
    cout<<endl;
    return 0;
}

NTT

（upd：數(shù)組一定要開兩倍，點數(shù)少了就沒法表示一個多項式）

總結(jié)

以上是生活随笔為你收集整理的【知识点】多项式乘法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。