记录编号	261355	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] 释迦	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	2.556 s
提交时间	2016-05-17 07:15:50	内存使用	19.86 MiB

#define maxn 270010ul

#include <cmath>
#include <stdio.h>
#include <algorithm>

using namespace std;

const int mod=23333333,M=4830;

namespace FFT{

	typedef long long ll;
	typedef long double ld;

	struct cpx{
		ld r,i;
		cpx(ld _r=0,ld _i=0){r=_r,i=_i;}
		cpx operator + (const cpx &x){return cpx(r+x.r,i+x.i);}
		cpx operator - (const cpx &x){return cpx(r-x.r,i-x.i);}
		cpx operator * (const cpx &x){return cpx(r*x.r-i*x.i,r*x.i+i*x.r);}
		cpx conj(){return cpx(r,-i);}
	}A[maxn],B[maxn];

	const ld pi=acos(-1.0);

	int fft_len;
	int a0[maxn],b0[maxn],a1[maxn],b1[maxn];

	void set_len(int n){
		fft_len=1;
		for(;fft_len<=n;fft_len<<=1);
		fft_len<<=1;return;
	}

	void fft(cpx f[],int n,int flag){
		for(int i=0,j=0;i<n;i++){
			if(i>j) std::swap(f[i],f[j]);
			for(int t=n>>1;(j^=t)<t;t>>=1);
		}
		cpx wn,w,u,t;
		for(int m=2;m<=n;m<<=1){
			wn=cpx(cos(2.0*pi/m),flag*sin(2.0*pi/m)),w=cpx(1,0);
			for(int i=0,p=m>>1;i<n;i+=m,w=cpx(1,0)) for(int k=0;k<p;k++,w=w*wn)
				u=f[i+k],t=w*f[i+k+p],f[i+k]=u+t,f[i+k+p]=u-t;
		}
		if(flag==-1) for(int i=0;i<n;i++) f[i].r/=n;
		return;
	}

	void mul(int *a,int *b,int *c){
		for(int i=0;i<fft_len;i++) A[i]=cpx(a[i],b[i]);
		fft(A,fft_len,1);
		for(int i=0,j;i<fft_len;i++){
  			j=(fft_len-i)&(fft_len-1);
    		B[i]=(A[i]*A[i]-(A[j]*A[j]).conj())*cpx(0,-0.25);
		}
		fft(B,fft_len,-1);
		for(int i=0;i<fft_len;i++) c[i]=((long long)(B[i].r+0.5))%mod;
		return;
	}

	void mul_mod(int *a,int *b,int *c){
		for(int i=0;i<fft_len;i++) a0[i]=a[i]/M,b0[i]=b[i]/M;
		mul(a0,b0,a0);
		for(int i=0;i<fft_len;i++) c[i]=1ll*a0[i]*M*M%mod,a1[i]=a[i]%M,b1[i]=b[i]%M;
		mul(a1,b1,a1);
		for(int i=0;i<fft_len;i++) c[i]=(a1[i]+c[i])%mod,a0[i]=(a0[i]+a1[i])%mod,a1[i]=a[i]/M+a[i]%M,b1[i]=b[i]/M+b[i]%M;
		mul(a1,b1,a1);
		for(int i=0;i<fft_len;i++) c[i]=(1ll*M*(a1[i]-a0[i]+mod)%mod+c[i])%mod;
		return;
	}
};

int n,L[maxn],R[maxn],result[maxn];

void read(int &x){
	x=0;int c=getchar();
	for(;c<'0'||c>'9';c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+(c^48);
	return;
}
int main(){
	freopen("annona_squamosa.in","r",stdin);
	freopen("annona_squamosa.out","w",stdout);
	read(n);
	for(int i=0;i<n;i++) read(L[i]);
	for(int i=0;i<n;i++) read(R[i]);
	FFT::set_len(n);
	FFT::mul_mod(L,R,result);
	for(int i=0;i<n;i++) printf("%d ",result[i]);
	return 0;
}