记录编号	375241	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] 释迦	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	4.103 s
提交时间	2017-02-24 21:40:27	内存使用	60.31 MiB

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define ll long long 
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-48,ch=getchar();
	return x*f;
}

const int maxn=(1<<18)+5;
const ll mod=23333333;
const ll M=4830;
const long double pi=acos(-1);
struct Complex{
	long double x,y;
	Complex(long double x=0.0,long double y=0.0):x(x),y(y){}
	Complex operator + (const Complex &a){return Complex(x+a.x,y+a.y);}
	Complex operator - (const Complex &a){return Complex(x-a.x,y-a.y);}
	Complex operator * (const Complex &a){return Complex(x*a.x-y*a.y,x*a.y+y*a.x);}
	Complex operator * (const long double &a){return Complex(x*a,y*a);}
}ka1[maxn],ba1[maxn],ka2[maxn],ba2[maxn],ans1[maxn],ans2[maxn],ans3[maxn];
Complex omega[maxn],iomega[maxn];
ll a[maxn],b[maxn],ans[maxn];

void fft_in(int n){
	for(int i=0;i<n;i++){
		omega[i]=Complex(cos(2*pi/n*i),sin(2*pi/n*i));
		iomega[i]=Complex(cos(-2*pi/n*i),sin(-2*pi/n*i));
	}
}
void fft(Complex *a,int n,Complex *w,int op){
	for(int i=0,j=0;i<n;i++){
		if(i>j) swap(a[i],a[j]);
		for(int l=n>>1;(j^=l)<l;l>>=1);
	}
	for(int l=2,m=1;l<=n;l<<=1,m<<=1)
		for(Complex *p=a;p!=a+n;p+=l)
			for(int i=0;i<m;i++){
				Complex t=p[i+m]*w[n/l*i];
				p[i+m]=p[i]-t,p[i]=p[i]+t;
			}
	if(op) for(int i=0;i<n;i++) a[i]=a[i]*(1.0/n);
}

int main(){
	freopen("annona_squamosa.in","r",stdin);freopen("annona_squamosa.out","w",stdout);
	int m=read();
	for(int i=0;i<m;i++) a[i]=read();
	for(int i=0;i<m;i++) b[i]=read();

	for(int i=0;i<m;i++)
		ka1[i]=a[i]/M*1.0,ba1[i]=a[i]%M*1.0;
	for(int i=0;i<m;i++)
		ka2[i]=b[i]/M*1.0,ba2[i]=b[i]%M*1.0;
	int n=1;while(n<m+m) n<<=1;
	fft_in(n);
	fft(ka1,n,omega,0);fft(ba1,n,omega,0);
	fft(ka2,n,omega,0);fft(ba2,n,omega,0);

	for(int i=0;i<n;i++){
		ans1[i]=ka1[i]*ka2[i];
		ans2[i]=ka1[i]*ba2[i]+ka2[i]*ba1[i];
		ans3[i]=ba1[i]*ba2[i];
	}
	fft(ans1,n,iomega,1);
	fft(ans2,n,iomega,1);
	fft(ans3,n,iomega,1);

	for(int i=0;i<m;i++){
		ll x=(ll)round(ans1[i].x);
		ll y=(ll)round(ans2[i].x);
		ll z=(ll)round(ans3[i].x);
		ans[i]=(x*M%mod*M%mod+y*M%mod+z)%mod;
	}
	for(int i=0;i<m;i++) printf("%lld\n",ans[i]);
	
	fclose(stdin);fclose(stdout);
	return 0;
}