记录编号	377246	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] 释迦	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	1.763 s
提交时间	2017-03-01 06:30:39	内存使用	58.31 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define ld long double
#define ll long long
const int maxn = (1<<18)+5;
const int mod = 23333333, M = 4830;
namespace FFT {
	const ld Pi = acos(-1.0);
	struct Complex {
		ld x, y;
		Complex(ld x=0.0, ld 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 ld &a) { return Complex(x*a, y*a); }
		Complex operator / (const ld &a) { return Complex(x/a, y/a); }
		Complex conj(bool c=1) { return Complex(x, c?-y:y);}
	} w[maxn];
	Complex a0[maxn], b0[maxn], a1[maxn], b1[maxn];
	Complex c0[maxn], c1[maxn], c2[maxn];
	int n, rev[maxn];
	void FFT_init(int N) {
		int l = 0;
		for(n=1; n<N; n<<=1, ++l); --l;
		for(int i=0; i<n; ++i) {
			w[i] = Complex(cos(2*Pi*i/n), sin(2*Pi*i/n));
			if(i) rev[i] = rev[i>>1]>>1|((i&1)<<l);
		}
	}
	void FFT(Complex *a, int op) {
		for(int i=1; i<n; ++i) if(rev[i]>i) swap(a[rev[i]], a[i]);
		for(int k=2; k<=n; k<<=1) 
			for(int j=0; j<n; j+=k)
				for(int i=0; i<(k>>1); ++i) {
					Complex t = a[i+j+(k>>1)]*w[n/k*i].conj(op);
					a[i+j+(k>>1)] = a[i+j]-t;
					a[i+j] = a[i+j]+t;
				}
		if(op) for(int i=0; i<n; ++i) a[i].x /= n;
	}
	void FFT(Complex *a, Complex *b) {
		static Complex t[maxn];
		for(int i=0; i<n; ++i) t[i] = Complex(a[i].x, b[i].x);
		FFT(t, 0);
		for(int i=0; i<n; ++i) {
			int j = (n-i)&(n-1);
			a[i] = (t[i]+t[j].conj())*Complex(0.5, 0);
			b[i] = (t[i]-t[j].conj())*Complex(0, -0.5);
		}
	}
	void mul(int *a, int *b, int *c, int N) {
		for(int i=0; i<n; ++i) a0[i] = Complex(a[i]/M), b0[i] = Complex(a[i]%M);
		for(int i=0; i<n; ++i) a1[i] = Complex(b[i]/M), b1[i] = Complex(b[i]%M);
		FFT(a0, b0); FFT(a1, b1);
		for(int i=0; i<n; ++i) {
			c0[i] = a0[i]*a1[i];
			c1[i] = a0[i]*b1[i]+a1[i]*b0[i];
			c2[i] = b0[i]*b1[i];
		}
		FFT(c0, 1); FFT(c1, 1); FFT(c2, 1);
		for(int i=0; i<N; ++i) {
			ll x = (ll)round(c0[i].x);
			ll y = (ll)round(c1[i].x);
			ll z = (ll)round(c2[i].x);
			c[i] = (x*M%mod*M%mod+y*M%mod+z)%mod;
		}
	}
}
int N, x[maxn], y[maxn], ans[maxn];
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", x+i);
	for(int i=0; i<N; ++i) scanf("%d", y+i);
	FFT::FFT_init(N+N);
	FFT::mul(x, y, ans, N);
	for(int i=0; i<N; ++i) printf("%d ", ans[i]); puts("");
	getchar(), getchar();
	return 0;
}