BZOJ 2194 快速傅立叶之二

题目大意

求$c_k = \sum a_i \times b_{i-k} (k \le i \lt n)$.

差相等直接反转$b$之后FFT即可。

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const double pi=acos(-1);
struct cp
{
	double x,y;
	cp(){x=y=0;}
	cp(double _x,double _y){x=_x,y=_y;}
	cp operator+(const cp &tg){return cp(x+tg.x,y+tg.y);}
	cp operator-(const cp &tg){return cp(x-tg.x,y-tg.y);}
	cp operator*(const cp &tg){return cp(x*tg.x-y*tg.y,x*tg.y+y*tg.x);}
}a[300000],b[300000],c[300000];
int n,len=1;
void fft(cp *x,int flg)
{
	for(int j,k=0,i=0;i<len;++i)
	{
		if(i>k) swap(x[i],x[k]);
		for(j=(len>>1);(k^=j)<j;j>>=1);
	}
	for(int i,j,k=2;k<=len;k<<=1)
	{
		cp wn(cos(2*pi*flg/k),sin(2*pi*flg/k));
		for(i=0;i<len;i+=k)
		{
			cp t,w(1,0);
			for(j=0;j<(k>>1);j++)
			{
				t=w*x[i+j+(k>>1)];
				x[i+j+(k>>1)]=x[i+j]-t;
				x[i+j]=x[i+j]+t;
				w=w*wn;
			}
		}
	}
	if(flg==-1) for(int i=0;i<len;++i) x[i].x/=len;
}
int main()
{
	scanf("%d",&n);
	while(len<(n<<1)) len<<=1;
	for(int i=0;i<n;++i) scanf("%lf%lf",&a[i].x,&b[n-i-1].x);
	fft(a,1),fft(b,1);
	for(int i=0;i<len;++i) c[i]=a[i]*b[i];
	fft(c,-1);
	for(int i=0;i<n;++i) printf("%.0lf\n",c[n+i-1].x+0.1);
	return 0;
}