题面

题目链接

解题思路

按题解模拟即可，这里提供一份能跑过的代码。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MOD = 786433;
const int G = 10;
const int N = MOD * 8 + 5;

int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
int mul(int a, int b) { return 1LL * a * b % MOD; }
int qpow(int x, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res = mul(res, x);
		x = mul(x, x);
		n /= 2;
	}
	return res;
}

namespace Poly {
	int a[N], b[N], c[N], rev[N];

	void ntt(int *a, int n, int op) {
		for (int i = 0; i < n; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
		for (int i = 1; i < n; i <<= 1) {
			int gn = qpow(G, (MOD - 1) / (i << 1));
			for (int j = 0; j < n; j += (i << 1)) {
				for (int k = 0, g = 1; k < i; k++, g = mul(g, gn)) {
					int x = a[j + k], y = mul(g, a[i + j + k]);
					a[j + k] = add(x, y);
					a[i + j + k] = add(x, MOD - y);
				}
			}
		}
		if (op == 1) return;
		reverse(a + 1, a + n);
		int inv = qpow(n, MOD - 2);
		for (int i = 0; i < n; i++) a[i] = mul(a[i], inv);
	}

	void clr(int *a, int l, int r) {
		for (int i = l; i < r; i++) a[i] = 0;
	}

	void getMul(int *aa, int n, int *bb, int m, int *cc, int q) {
		int p = 1, l = 0;
		while (p < n + m) p <<= 1, l++;
		for (int i = 0; i < p; i++) a[i] = b[i] = c[i] = rev[i] = 0;
		for (int i = 0; i < p; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
		for (int i = 0; i < n; i++) a[i] = aa[i];
		for (int i = 0; i < m; i++) b[i] = bb[i];
		ntt(a, p, 1); ntt(b, p, 1);
		for (int i = 0; i < p; i++) c[i] = mul(a[i], b[i]);
		ntt(c, p, -1);
		for (int i = 0; i < q; i++) cc[i] = c[i];
	}

	void getInv(int *aa, int *bb, int n) {
		if (n == 1) return void(bb[0] = qpow(aa[0], MOD - 2));
		getInv(aa, bb, (n + 1) / 2);
		int p = 1, l = 0;
		while (p < n * 2) p <<= 1, l++;
		for (int i = 0; i < p; i++) a[i] = b[i] = c[i] = rev[i] = 0;
		for (int i = 0; i < p; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
		for (int i = 0; i < n; i++) a[i] = aa[i];
		for (int i = 0; i < n; i++) b[i] = bb[i];
		ntt(a, p, 1); ntt(b, p, 1);
		for (int i = 0; i < p; i++) c[i] = mul(b[i], add(2, MOD - mul(a[i], b[i])));
		ntt(c, p, -1);
		for (int i = 0; i < n; i++) bb[i] = c[i];
	}

	void getDer(int *a, int *b, int n) {
		for (int i = 1; i < n; i++) b[i - 1] = mul(i, a[i]);
		b[n - 1] = 0;
	}

	void getInt(int *a, int *b, int n) {
		for (int i = n - 1; i >= 1; i--) b[i] = mul(a[i - 1], qpow(i, MOD - 2));
		b[0] = 0;
	}

	int getN(int n) {
		int p = 1;
		while (p < n) p <<= 1;
		return p;
	}

	void getLn(int *aa, int *bb, int n) {
		static int s[N], ss[N];
		getDer(aa, s, n);
		getInv(aa, ss, n);
		getMul(s, n, ss, n, s, n);
		getInt(s, bb, n);
		clr(s, 0, n); clr(ss, 0, n);
	}

	void getExp(int *aa, int *bb, int n) {
		static int fu[N];
		if (n == 1) return void(bb[0] = 1);
		getExp(aa, bb, n / 2); getLn(bb, fu, n);
		for (int i = 0; i < n; i++) fu[i] = add(aa[i], MOD - fu[i]);
		fu[0]++;
		getMul(bb, n, fu, n, bb, n);
		clr(bb, n, n * 2); clr(fu, 0, n * 2);
	}
}

using Poly::ntt;
using Poly::getExp;

int n, m, tp;
int p[N], P[N], E[N], f1[N], f2[N], f3[N], F[N], ans[N];

int get(int x) {
	int ans = 0;
	for (int i = 0; i <= n; i++) ans = add(ans, mul(F[i], qpow(x, i)));
	return ans;
}

int main() {
	//freopen("0.txt", "r", stdin);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", p + i);
	for (int i = 1, co = 1; i <= n; i++, co = MOD - co) P[i - 1] = mul(co, p[i]);
	m = Poly::getN(n + 1);
	Poly::getInt(P, f1, m);
	getExp(f1, f2, m);
	for (int i = 1; i <= n; i++) E[i] = f2[i];
	for (int i = 1, co = MOD - 1; i <= n; i++, co = MOD - co) F[n - i] = mul(E[i], co);
	F[n] = 1;
	memset(f1, 0, sizeof(f1)); memset(f2, 0, sizeof(f2));
	int g = qpow(G, MOD - 2), g2 = mul(g, g);
	g = G, g2 = mul(G, G);
	for (int i = 0; i <= n; i++) f1[i] = F[i];
	for (int i = 1; i <= n; i++) f2[i] = mul(F[i], qpow(g, i));
	for (int i = 1; i <= n; i++) f3[i] = mul(F[i], qpow(g2, i));
	f2[0] = f3[0] = F[0];
	m = (1 << 18);
	for (int i = 0; i < m; i++) Poly::rev[i] = 0;
	for (int i = 0; i < m; i++) Poly::rev[i] = (Poly::rev[i >> 1] >> 1) | ((i & 1) << (18 - 1));
	ntt(f1, m, 1); ntt(f2, m, 1); ntt(f3, m, 1);
	for (int i = 0; i < m; i++) if (f1[i] == 0) ans[++tp] = qpow(G, i * 3);
	for (int i = 0; i < m; i++) if (f2[i] == 0) ans[++tp] = qpow(G, i * 3 + 1);
	for (int i = 0; i < m; i++) if (f3[i] == 0) ans[++tp] = qpow(G, i * 3 + 2);
	if (F[0] == 0) ans[++tp] = 0;
	sort(ans + 1, ans + tp + 1);
	for (int i = 1; i <= tp; i++) printf("%d%c", ans[i], i == tp ? '\n' : ' ');
	return 0;
}