BZOJ-2194: 快速傅立叶之二

Description

请计算C[k]=sigma(a[i]*b[i-k]) 其中 k < = i < n ，并且有 n < = 10 ^ 5。 a,b中的元素均为小于等于100的非负整数。

将b翻转，那么b[x]->b[n-x-1]，那么c[k]=直接多项式FFT。
板子~~~

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define rint register int
#define N 100010
const double pi=acos(-1.0);
struct cp
{
    double x,i;
    cp(double _x=0,double _i=0):x(_x),i(_i){}
    cp operator+(const cp z)const {return cp(x+z.x,i+z.i);}
    cp operator-(const cp z)const {return cp(x-z.x,i-z.i);}
    cp operator*(const cp z)const {return cp(x*z.x-i*z.i,x*z.i+i*z.x);}
};
int n,ans[N];
void FFT(cp a[],int len,int fl)
{
    rint i,j,k; cp t;
    for(i=k=0;i!=len;++i)
    {
        if(i>k) swap(a[i],a[k]);
        for(j=(len>>1);(k^=j)<j;j>>=1);
    }
    for(i=2;i<=len;i<<=1)
    {
        cp wn(cos(2*pi*fl/i),sin(2*pi*fl/i));
        for(j=0;j!=len;j+=i)
        {
            cp w(1,0);
            for(k=j;k!=j+(i>>1);++k,w=w*wn)
                t=w*a[k+(i>>1)],a[k+(i>>1)]=a[k]-t,a[k]=a[k]+t;
        }
    }
    if(fl==-1) for(i=0;i!=len;++i) a[i].x/=len;
}
cp n1[N<<2],n2[N<<2];
void conv(cp a[],cp b[],int len)
{
    FFT(a,len,1); FFT(b,len,1);
    for(int i=0;i<len;++i) a[i]=a[i]*b[i];
    FFT(a,len,-1);
    for(int i=0;i!=n;++i) ans[i]=int(a[n+i-1].x+0.1);
}
int main()
{
    scanf("%d",&n);
    rint i,x,y;
    for(i=0;i!=n;i++)
    {
        scanf("%d%d",&x,&y);
        n1[i]=cp(x,0);
        n2[n-i-1]=cp(y,0);
    }
    int len;
    for(len=1;len<(n<<1);len<<=1);
    conv(n1,n2,len);
    for(int i=0;i!=n;++i)
        printf("%d\n",ans[i]);
    return 0;
}