记录编号	564292	评测结果	AAAAAAAAAA
题目名称	2294.[HZOI 2015] 释迦	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	3.745 s
提交时间	2021-09-29 04:24:02	内存使用	48.27 MiB

#include <bits/stdc++.h>

using namespace std;

const int maxn = 262155, p = 23333333, base = 5000;
const double pi = acos((double)-1.0);

struct Complex {
	double a, b;

	Complex(double a = 0.0, double b = 0.0) : a(a), b(b) {}

	Complex operator + (const Complex &x) const {
		return Complex(a + x.a, b + x.b);
	}

	Complex operator - (const Complex &x) const {
		return Complex(a - x.a, b - x.b);
	}

	Complex operator * (const Complex &x) const {
		return Complex(a * x.a - b * x.b, a * x.b + b * x.a);
	}

	Complex operator * (double x) const {
		return Complex(a * x, b * x);
	}

	Complex &operator += (const Complex &x) {
		return *this = *this + x;
	}

	Complex conj() const {
		return Complex(a, -b);
	}
} omega[maxn], omega_inv[maxn];
const Complex ima = Complex(0, 1);

int fft_n;

void FFT_init(int n) {
	fft_n = n;

	for (int i = 0; i < n; i++)
		omega[i] = Complex(cos(2 * pi / n * i), sin(2 * pi / n * i));
	
	omega_inv[0] = omega[0];
	for (int i = 1; i < n; i++)
		omega_inv[i] = omega[n - i];
}

void FFT(Complex *a, int n, int tp) {
	for (int i = 1, j = 0, k; i < n - 1; i++) {
		k = n;
		do
			j ^= (k >>= 1);
		while (j < k);

		if (i < j)
			swap(a[i], a[j]);
	}

	for (int k = 2, m = fft_n / 2; k <= n; k *= 2, m /= 2)
		for (int i = 0; i < n; i += k)
			for (int j = 0; j < k / 2; j++) {
				Complex u = a[i + j], v = (tp > 0 ? omega : omega_inv)[m * j] * a[i + j + k / 2];

				a[i + j] = u + v;
				a[i + j + k / 2] = u - v;
			}

	if (tp < 0)
		for (int i = 0; i < n; i++) {
			a[i].a /= n;
			a[i].b /= n;
		}
}

void DFT(Complex *a, Complex *b, int n) {
	static Complex c[maxn];

	for (int i = 0; i < n; i++)
		c[i] = Complex(a[i].a, b[i].a);
	
	FFT(c, n, 1);

	for (int i = 0; i < n; i++) {
		int j = (n - i) & (n - 1);

		a[i] = (c[i] + c[j].conj()) * 0.5;
		b[i] = (c[i] - c[j].conj()) * -0.5 * ima;
	}
}

void IDFT(Complex *a, Complex *b, int n) {
	static Complex c[maxn];

	for (int i = 0; i < n; i++)
		c[i] = a[i] + ima * b[i];
	
	FFT(c, n, -1);
	
	for (int i = 0; i < n; i++) {
		a[i].a = c[i].a;
		b[i].a = c[i].b;
	}
}

Complex a[2][maxn], b[2][maxn], c[3][maxn];
int ans[maxn];

int main() {
	freopen("annona_squamosa.in", "r", stdin);
	freopen("annona_squamosa.out", "w", stdout);

	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);

		a[1][i].a = x / base;
		a[0][i].a = x % base;
	}

	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);

		b[1][i].a = x / base;
		b[0][i].a = x % base;
	}

	int N = 1;
	while (N < n * 2 - 1)
		N <<= 1;
	
	FFT_init(N);

	DFT(a[0], a[1], N);
	DFT(b[0], b[1], N);

	for (int i = 0; i < N; i++)
		c[0][i] = a[0][i] * b[0][i];
	
	for (int i = 0; i < N; i++)
		c[1][i] = a[0][i] * b[1][i] + a[1][i] * b[0][i];

	for (int i = 0; i < N; i++)
		c[2][i] = a[1][i] * b[1][i];

	FFT(c[1], N, -1);
	IDFT(c[0], c[2], N);

	for (int j = 2; ~j; j--)
		for (int i = 0; i < n; i++)
			ans[i] = ((long long)ans[i] * base + (long long)(c[j][i].a + 0.5)) % p;

	for (int i = 0; i < n; i++) {
		if (i)
			printf(" ");

		printf("%d", ans[i]);
	}

	return 0;
}