洛谷P3803 【模板】多项式乘法（FFT）

lzzVIL · 2018-07-23 15:00:28 · 个人记录

题意

给定一个n次多项式F(x)，和一个m次多项式G(x)。
请求出F(x)和G(x)的卷积。

输入

第一行2个正整数n,m。
接下来一行n+1个数字，从低到高表示F(x)的系数。
接下来一行m+1个数字，从低到高表示G(x))的系数。

输出

一行n+m+1个数字，从低到高表示F(x)∗G(x)的系数。

题解

http://www.cnblogs.com/zwfymqz/p/8244902.html

代码

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iostream>
#define ll long long
#define ld long double
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!('0'<=ch&&ch<='9')) {if (ch=='-') f=-f;ch=getchar();}
    while ('0'<=ch&&ch<='9') x<<=1,x+=(x<<2)+ch-'0',ch=getchar();
    return x;
}
inline void read(ll &x){x=read();}
inline void write(ll x){
    if (x<0) putchar('-'),x=-x;
    if (x>9) write(x/10);putchar(x%10+'0');
}
inline void writeln(){putchar('\n');}
inline void writeln(ll x){write(x);writeln();}
const double Pi=acos(-1.0);
struct complex{
    double x,y;
    complex (double X=0,double Y=0){x=X,y=Y;}   
} a[5000020],b[5000020];
complex operator +(complex a,complex b){return complex(a.x+b.x,a.y+b.y);}
complex operator -(complex a,complex b){return complex(a.x-b.x,a.y-b.y);}
complex operator *(complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
ll n,m,lim=1;
ll l,r[5000020];
inline void FFT(ll &lim,complex *a,ll type){
    for (ll i=0;i<lim;++i)
        if (i<r[i]) swap(a[i],a[r[i]]);
    for (ll mid=1;mid<lim;mid<<=1){
        complex Wn=complex(cos(Pi/mid),type*sin(Pi/mid));
        for (ll R=mid<<1,j=0;j<lim;j+=R){
            complex w=complex(1,0);
            for (ll k=0;k<mid;++k,w=w*Wn){
                complex x=a[j+k],y=w*a[j+mid+k];
                a[j+k]=x+y;
                a[j+mid+k]=x-y;             
            }           
        }       
    }
}
signed main(){
    ios::sync_with_stdio(false);
    read(n),read(m);
    for (ll i=0;i<=n;++i) a[i].x=read();
    for (ll i=0;i<=m;++i) b[i].x=read();
    while (lim<=n+m) lim<<=1,++l;
    for (int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    FFT(lim,a,1);
    FFT(lim,b,1);
    for (int i=0;i<=lim;++i) a[i]=a[i]*b[i];
    FFT(lim,a,-1);
    for (ll i=0;i<=n+m;++i) write((ll)(a[i].x/lim+0.5)),putchar(' ');
    writeln();
    return 0;
}

心得体会

FFT模板还是很实用的。所以板子一定要好好背。