bzoj 2194: 快速傅立叶之二 — FFT

2194: 快速傅立叶之二

Time Limit: 10 Sec  Memory Limit: 259 MB

Description

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

Input

第一行一个整数N,接下来N行，第i+2..i+N-1行，每行两个数，依次表示a[i],b[i] (0 < = i < N)。

Output

输出N行，每行一个整数，第i行输出C[i-1]。

Sample Input

5
3 1
2 4
1 1
2 4
1 4

Sample Output

24
12
10
6
1

HINT

Source

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<complex>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define cp complex<double>
#define inf 1000000007
#define ll long long
#define PI acos(-1)
#define N 400010
inline int rd()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
cp a[N],b[N];
int c[N],n,m,L=-1,r[N];
void FFT(cp *x,int f)
{
    for(int i=0;i<n;i++) if(i<r[i]) swap(x[i],x[r[i]]);
    for(int i=1;i<n;i<<=1)
    {
        cp wn(cos(PI/i),f*sin(PI/i));
        for(int j=0;j<n;j+=(i<<1))
        {
            cp w(1,0),X,Y;
            for(int k=0;k<i;k++,w*=wn)
            {
                X=x[j+k];Y=w*x[i+j+k];
                x[j+k]=X+Y;x[i+j+k]=X-Y;
            }
        }
    }
}
int main()
{
    n=rd()-1;
    for(int i=0;i<=n;i++){a[i]=rd();b[n-i]=rd();}
    m=n<<1;for(n=1;n<=m;n<<=1) L++;
    for(int i=0;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<L);
    FFT(a,1);FFT(b,1);
    for(int i=0;i<n;i++) a[i]*=b[i];
    FFT(a,-1);
    for(int i=m/2;i<=m;i++) printf("%d\n",(int)(a[i].real()/n+0.1));
    return 0;
}