bzoj2194 快速傅立葉之二

Description

請計算C[k]=sigma(a[i]*b[i-k]) 其中 k < = i < n ，並且有 n < = 10 ^ 5。 a,b中的元素均為小於等於100的非負整數。

Input

Output

輸出N行，每行一個整數，第i行輸出C[i-1]。

Sample Input

Sample Output

一看題的名字就知道這題什麼方法了。

這不是卷積的形式，所以我們要把兩個數組中的一個翻轉，這樣就變成卷積的形式了。然後就能用FFT解決了。

形如c[k]=∑(a[i]*b[i-k])的形式可以將一個數組翻轉，再用FFT。

#include
#include
#include
#include
#include
#include
#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>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>=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\n",(ll)(c[nn-1+i].x+0.5));
	return 0;
}