记录编号	413597	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] 释迦	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.365 s
提交时间	2017-06-11 20:29:34	内存使用	14.31 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1<<18|1,p=23333333;
int n,a[N],b[N];
int mul(int x,int y){return (ll)x*y%p;}
struct mod_seq{
	int p,gen;
	int inc(int x,int y){x+=y;return x>=p?x-p:x;}
	int dec(int x,int y){x-=y;return x<0?x+p:x;}
	int mul(int x,int y){return (ll)x*y%p;}
	int power(int x,int y){
		int ans=1;
		for (;y;y>>=1,x=mul(x,x))
			if (y&1) ans=mul(ans,x);
		return ans;
	}
	int a[N],b[N],w[N],iw[N];
	void init(int n){
		w[0]=1;w[1]=power(gen,(p-1)/n);
		for (int i=2;i<=n;i++) w[i]=mul(w[i-1],w[1]);
		for (int i=0;i<=n;i++) iw[i]=w[n-i];
	}
	void fft(int n,int *a,int *w){
		for (int i=0,j=0;i<n;i++){
			if (i<j) swap(a[i],a[j]);
			for (int k=n>>1;(j^=k)<k;k>>=1);
		}
		for (int i=2;i<=n;i<<=1){
			int m=i>>1,step=n/i;
			for (int j=0;j<n;j+=i)
			for (int k=0,pos=0;k<m;k++,pos+=step){
				int t=mul(a[j+k+m],w[pos]);
				a[j+k+m]=dec(a[j+k],t);
				a[j+k]=inc(a[j+k],t);
			}
		}
	}
	void solve(int P,int Gen){
		p=P;gen=Gen;
		for (int i=0;i<n;i++) a[i]=::a[i],b[i]=::b[i];
		int size=1;
		while (size<n+n) size<<=1;
		init(size);
		fft(size,a,w);fft(size,b,w);
		for (int i=0;i<size;i++) a[i]=mul(a[i],b[i]);
		fft(size,a,iw);
		int del=power(size,p-2);
		for (int i=0;i<size;i++) a[i]=mul(a[i],del);
	}
}A,B,C;
int CRT(int a1,int a2,int a3){
	static ll AB=(ll)A.p*B.p,AiB=B.power(A.p,B.p-2),BiA=A.power(B.p,A.p-2);
	static ll ABiC=C.power(AB%C.p,C.p-2);
	ll a=((ll)B.p*A.mul(a1,BiA)+(ll)A.p*B.mul(a2,AiB))%AB;
	a=(a+((a3-a)%C.p+C.p)%C.p*ABiC%C.p*(AB%p)%p)%p;
	return a<0?a+p:a;
}
int main()
{
	freopen("annona_squamosa.in","r",stdin);
	freopen("annona_squamosa.out","w",stdout);
	scanf("%d",&n);
	for (int i=0;i<n;i++) scanf("%d",&a[i]),a[i]%=p;
	for (int i=0;i<n;i++) scanf("%d",&b[i]),b[i]%=p;
	A.solve(119<<23|1,3);
	B.solve(479<<21|1,3);
	C.solve(1917<<19|1,5);
	for (int i=0;i<n;i++) printf("%d ",CRT(A.a[i],B.a[i],C.a[i]));puts("");
	return 0;
}