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

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

#include <cstdio>

#include <cstring>

#include <iostream>

#include <cmath>

#define pi acos(-1.0)

using namespace std;

struct cp

{

	double x,y;

	cp (double a,double b){x=a,y=b;}

	cp (){}

	cp operator +(cp a)	const {return cp(x+a.x,y+a.y);}

	cp operator -(cp a) const {return cp(x-a.x,y-a.y);}

	cp operator *(cp a)	const {return cp(x*a.x-y*a.y,x*a.y+y*a.x);}

}n1[1<<20],n2[1<<20];

int ans[1<<20],n;

long long sum;

void init(cp *a,int len)

{

	int i,j,t=0;

	for(i=0;i<len;i++)

	{

		if(i>t)	swap(a[i],a[t]);

		for(j=(len>>1);(t^=j)<j;j>>=1);

	}

}

void FFT(cp *a,int len,int f)

{

	init(a,len);

	int i,j,k,h;

	cp u;

	for(h=2;h<=len;h<<=1)

	{

		cp wn=cp(cos(f*2*pi/h),sin(f*2*pi/h));

		for(j=0;j<len;j+=h)

		{

			cp w(1,0);

			for(k=j;k<j+h/2;k++)

			{

				u=w*a[k+h/2],a[k+h/2]=a[k]-u,a[k]=a[k]+u,w=w*wn;

			}

		}

	}

}

void work(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<len;i++)	ans[i]=int(a[i].x/len+0.5);

}

int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

int main()

{

	n=rd();

	int i,a,b,len=1;

	while(len<2*n)	len<<=1;

	for(i=0;i<n;i++)

	{

		a=rd(),b=rd();

		n1[i].x=a*1.0,n2[n-i-1].x=b*1.0;

	}

	work(n1,n2,len);

	for(i=n-1;i<2*n-1;i++)	printf("%d\n",ans[i]);

	return 0;

}