bzoj 2194高速フーリエの2

2311 ワード

2194:高速フーリエの2
Time Limit: 10 Sec  
Memory Limit: 259 MB
Submit: 829  
Solved: 474
[ Submit][ Status][ Discuss]
Description
C[k]=sigma(a[i]*b[i-k])のk<=iInput
第1行の整数N、次のN行、第i+2..i+N−1行、行ごとに2つの数、a[i],b[i](0<=iOutput
N行を出力し、行ごとに整数を1つ、i行目はC[i-1]を出力する. 
Sample Input
5 3 1 2 4 1 1 2 4 1 4
Sample Output
24 12 10 6 1
問題の名前を見ると、この問題の方法がわかります.
これはボリュームの形式ではないので、2つの配列の1つを反転して、ボリュームの形式になります.そしてFFTで解決できます.
c[k]=Σ(a[i]*b[i-k])のような形で配列を反転させ、FFTを使用することができます.
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 300005
using namespace std;
int n,m,len,rev[maxn];
struct cp
{
    double x,y;
    inline cp operator +(cp b){return (cp){x+b.x,y+b.y};}
    inline cp operator -(cp b){return (cp){x-b.x,y-b.y};}
    inline cp operator *(cp b){return (cp){x*b.x-y*b.y,x*b.y+y*b.x};}
}a[maxn],b[maxn],c[maxn];
const double PI=acos(-1.0);
inline int read()
{
	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;
}
inline void fft(cp *x,int n,int flag)
{
	F(i,0,n-1) if (rev[i]>i) swap(x[i],x[rev[i]]);
	for(int m=2;m<=n;m<<=1)
	{
		cp wn=(cp){cos(2.0*PI/m*flag),sin(2.0*PI/m*flag)};
		for(int i=0;i<n;i+=m)
		{
			cp w=(cp){1.0,0};
			int mid=m>>1;
			F(j,0,mid-1)
			{
				cp u=x[i+j],v=x[i+j+mid]*w;
				x[i+j]=u+v;x[i+j+mid]=u-v;
				w=w*wn;
			}
		}
	}
    if(flag==-1) F(i,0,n-1) x[i].x/=n;
}
int main()
{
	n=read();int nn=n;
	F(i,0,n-1) a[i].x=read(),b[n-1-i].x=read();
	n=2*n-1;m=1;
	while (m<n) m<<=1,len++;
	n=m;
	F(i,0,n-1)
	{
		int t=i,ret=0;
		F(j,1,len){ret<<=1;ret|=(t&1);t>>=1;}
		rev[i]=ret;
	}
	fft(a,n,1);fft(b,n,1);
	F(i,0,n-1) c[i]=a[i]*b[i];
	fft(c,n,-1);
	F(i,0,nn-1) printf("%lld
",(ll)(c[nn-1+i].x+0.5)); return 0; }