记录编号	375961	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] 释迦	最终得分	100
用户昵称	kito	是否通过	通过
代码语言	C++	运行时间	1.858 s
提交时间	2017-02-26 11:39:27	内存使用	100.31 MiB

#include<stdio.h>
#include<math.h>
#include<iostream>
#include<ctime>
#define	fcl	fclose(stdin);	fclose(stdout); return 0
	#define SUBMIT 2333
typedef long long LL;
const int mod=23333333;
const int maxn=1048576+10;
const int p=5233;
const int pp=p*p;
const double PI=(double)acos(-1.0);
int n,N,K;
struct Complex{
	double a,b;
	Complex(){}
	Complex(const double& x,const double& y){a=x,b=y;}
	inline Complex operator * (const Complex& x)const{return Complex(a*x.a-b*x.b,b*x.a+a*x.b);}
	inline Complex operator + (const Complex& x)const{return Complex(a+x.a,b+x.b);}
	inline void operator += (const Complex& x){a+=x.a; b+=x.b;}
	inline Complex operator - (const Complex& x)const{return Complex(a-x.a,b-x.b);}
	inline void operator *= (const double& x){a*=x; b*=x;}
	inline Complex operator * (const double& x){return Complex(a*x,b*x);}
}A[maxn],B[maxn],w[maxn][2],C[maxn],D[maxn];
int Rev[maxn];
void REV(){
	for(N=1,K=0;N<n;N<<=1,++K);
	N<<=1;
	for(int i=1;i<N;++i) Rev[i]=((Rev[i>>1]>>1)|((i&1)<<K));
	for(int i=0;i<N;++i){
		w[i][0]=Complex(cos(PI*2*i/N),sin(PI*2*i/N));
		w[i][1]=Complex(cos(-PI*2*i/N),sin(-PI*2*i/N));
	}
}

void FFT(Complex* Q,const int& Ty){
	for(int i=0;i<N;++i) if(Rev[i]<i) std::swap(Q[i],Q[Rev[i]]);
	Complex x;
	for(int i=0;i<N;i+=2){
		x=Q[i];
		Q[i]+=Q[i+1]; Q[i+1]=x-Q[i+1];
	}
	for(int l=4,c=2,t=(N>>2),i,k,tt;l<=N;t>>=1,c=l,l<<=1){
		for(i=0;i<N;i+=l){
			x=Q[i];
			Q[i]+=Q[i+c];	Q[i+c]=x-Q[i+c];
		}
		for(k=1,tt=t;k<c;++k,tt+=t){
			for(i=0;i<N;i+=l){
				x=Q[i+k];
				Q[i+k]+=(w[tt][Ty]*Q[i+k+c]);
				Q[i+k+c]=x-w[tt][Ty]*Q[i+k+c];
			}
		}
	}
}

char CH[100],ch;
int l=0;
void Print(int x){
	if(!x) puts("0");
	else{
		for(l=0;x;x/=10) CH[++l]=x%10+'0';
		for(;l;--l) putchar(CH[l]);
		puts("");
	}
}

void Read(int& x){
	while(ch=getchar(),ch<'0'||ch>'9');
	x=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9') x=x*10+ch-'0';
}

void PRINT(){
	for(int i=0;i<n;++i){
		LL a=(LL(A[i].a+0.5)%mod)*pp%mod;
		LL b=(LL(C[i].a+0.5))*p%mod;
		LL c=(LL(B[i].a+0.5))%mod;
		LL x=(LL)(a+b+c)%mod;
		Print(x);
	}
}

int main(){
	freopen("annona_squamosa.in","r",stdin);
	freopen("annona_squamosa.out","w",stdout);
	Read(n);
//	printf("time after read n %d\n",clock());
	REV();
	int x;
//	printf("time after rev %d\n",clock());
	for(int i=0;i<n;++i){
		Read(x); if(x>=mod) x%=mod;
		A[i].a=1.0*(x/p);
		C[i].a=1.0*(x%p);
	}
	for(int i=0;i<n;++i){
		Read(x); if(x>=mod) x%=mod;
		B[i].a=1.0*(x/p);
		D[i].a=1.0*(x%p);
	}
//	printf("time after read %d\n",clock());
	FFT(A,0); FFT(B,0);
	FFT(C,0); FFT(D,0);
//	printf("time after four times FFT %d\n",clock());
	Complex a,b,c,d;
	for(int i=0;i<N;++i){
		a=A[i]; b=B[i]; c=C[i]; d=D[i];
		A[i]=a*b;	B[i]=c*d;	C[i]=b*c;	D[i]=a*d; C[i]+=D[i];
	}
//	printf("time after multi %d\n",clock());
	FFT(A,1); FFT(B,1); FFT(C,1);
//	printf("time after other three times FFT %d\n",clock());
	double Inv=1.0/N;
//	printf("time=%d\n",clock());
	for(int i=0;i<N;i+=4){
		A[i]*=Inv; B[i]*=Inv; C[i]*=Inv;
		A[i+1]*=Inv; B[i+1]*=Inv; C[i+1]*=Inv;
		A[i+2]*=Inv; B[i+2]*=Inv; C[i+2]*=Inv;
		A[i+3]*=Inv; B[i+3]*=Inv; C[i+3]*=Inv;
	}
//	printf("time=%d\n",clock());
	PRINT();
	//printf("time=%.4f\n",1.0*clock()/CLOCKS_PER_SEC);
	//while(1);
	fcl;
}