BZOJ 2194 快速傅立叶之二

还没搞清楚卷积到底是啥...大概就是多项式乘法?

//By Richard
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define log2(x) (31-__builtin_clz(x))
#define mod (int)(1e9+7)
#define inf 0x3f3f3f3f
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
#ifdef ONLINE_JUDGE
#define debugdo(X)
#define debugndo(X)
#define debugout(X)
#endif
#define putarray(x,n) rep(iiii,1,n) printf("%d ",x[iiii])
#define mp make_pair
using namespace std;
typedef pair<int,int> pairs;
typedef long long LL;
/////////////////////read3.0////////////////////////////////////
template <typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {ch=getchar();if (ch=='-') flag=true;}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template <typename T>
inline void read(T &x,T &y){read(x);read(y);}
/////////////////variables&functions////////////////////
const double pi=3.1415926535897932384626433832795028841971693993751058209749446;
const int maxn=1024768;
struct cp
{
    double x,y;
    cp(double a=0,double b=0):x(a),y(b){}
    cp operator+(cp a){return cp(x+a.x,y+a.y);}
    cp operator-(cp a){return cp(x-a.x,y-a.y);}
    cp operator*(cp a){return cp(x*a.x-y*a.y,x*a.y+y*a.x);}
    cp operator/(int a){return cp(x/a,y/a);}
}A[maxn],B[maxn];
int l,n,r[maxn],nn,m;
inline void swap(int &x,int &y){int t=x;x=y;y=t;}
void FFT(cp *a,int n,int op)
{
    rep(i,0,n-1) if (i<r[i]) swap(a[i],a[r[i]]);
    for (int i=1;i<n;i<<=1)
    {
        cp wn(cos(pi/i),sin(pi/i)*op);
        for (int j=0;j<n;j+=i<<1)
        {
            cp w(1,0);
            for (int k=0;k<i;k++,w=w*wn)
            {
                cp x=a[j+k],y=w*a[i+j+k];
                a[j+k]=x+y;
                a[i+j+k]=x-y;
            }
        }
    }
}
void mul(cp *a,cp *b)
{
    m+=n-2;
    for (l=0,n=1;n<=m;n<<=1,l++);
    rep(i,0,n-1) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    FFT(a,n,1);FFT(b,n,1);
    // rep(i,0,n-1) printf("%d %d\n",(int)A[i].x,(int)B[i].x);
    rep(i,0,n-1) a[i]=a[i]*b[i];
    FFT(a,n,-1);
    rep(i,0,n-1) a[i].x=a[i].x/n;
}
int main()
{
    read(n);
    nn=n;
    rep(i,0,n-1) read(A[i].x,B[n-i-1].x);
    m=n;
    mul(A,B);
    // rep(i,0,n-1) printf("%d %d\n",(int)A[i].x,(int)B[i].x);
    rep(i,m-nn+1,m) printf("%d\n",(int)(A[i].x+0.5));
    return 0;
}