Submission #1804486

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
typedef long long ll;
const int N = 2e5;
const int LEN = 524288;
const int G = 5;
const int Mod = 924844033;
int n, fac[N], Ifac[N], que[N], qn, fa[N], sze[N], num[N];
int tot, first[N << 1], next[N << 1], end[N << 1];
int len, w[2][LEN], R[LEN], x[LEN], y[LEN];
inline int Get() {
	char ch;
	while ((ch = getchar()) < '0' || ch > '9');
	int Num = ch - '0';
	while ((ch = getchar()) >= '0' && ch <= '9')
		Num = (Num << 3) + (Num << 1) + ch - '0';
	return Num;
}
inline void AddEdge(int x, int y) {
	next[++tot] = first[x], first[x] = tot, end[tot] = y;
	next[++tot] = first[y], first[y] = tot, end[tot] = x;
}
inline int pow(int x, int k) {
	ll res = 1, r = x;
	for (; k; k >>= 1, r = r * r % Mod)
		if (k & 1) res = res * r % Mod;
	return res;
}
void NTT(int *a, int n, int res) {
	for (int i = 0; i < n; ++i) if (i < R[i]) std :: swap(a[i], a[R[i]]);
	
	for (int k = 1; k < n; k <<= 1) {
		int x = w[res][n / k / 2];
		for (int str = 0; str < n; str += k << 1) {
			int wx = 1;
			for (int i = str; i < str + k; ++i) {
				int u1 = a[i], u2 = (ll)wx * a[i + k] % Mod;
				a[i] = (u1 + u2) % Mod;
				a[i + k] = (u1 - u2 + Mod) % Mod;
				wx = (ll)wx * x % Mod;
			}
		}
	}
	
	if (!res) {
		int Inv = pow(n, Mod - 2);
		for (int i = 0; i < n; ++i) a[i] = (ll)a[i] * Inv % Mod;
	}
}
inline void Init(int n) {
	len = 0;
	while ((1 << len) <= n) ++len;
	int x = pow(G, (Mod - 1) / (1 << len));
	w[0][0] = w[1][0] = 1;
	for (int i = 1; i < (1 << len); ++i) {
		R[i] = (R[i >> 1] >> 1) | ((i & 1) << len - 1);
		w[0][(1 << len) - i] = w[1][i] = (ll)w[1][i - 1] * x % Mod;
	}
}
inline int calc(int n, int m) {
	return (ll)fac[n] * Ifac[m] % Mod * Ifac[n - m] % Mod;
}
int main() {
	n = Get();
	for (int i = 1, u, v; i < n; ++i)
		u = Get(), v = Get(), AddEdge(u, v);
	
	que[qn = 1] = 1, fa[1] = 0;
	for (int ql = 1, u; u = que[ql], ql <= qn; sze[u] = 1, ++ql)
		for (int k = first[u], v; v = end[k], k; k = next[k])
			if (v != fa[u]) fa[v] = u, que[++qn] = v;
	for (int qr = qn, u; u = que[qr], qr > 1; --qr) sze[fa[u]] += sze[u];
	for (int i = 2; i <= n; ++i) ++num[sze[i]], ++num[n - sze[i]];
	
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) fac[i] = (ll)fac[i - 1] * i % Mod;
	Ifac[n] = pow(fac[n], Mod - 2);
	for (int i = n; i; --i) Ifac[i - 1] = (ll)Ifac[i] * i % Mod;

	for (int i = 1; i <= n; ++i) x[i] = (ll)num[i] * fac[i] % Mod;
	for (int i = 0; i <= n; ++i) y[n - i] = Ifac[i];
	
	Init(2 * n), NTT(x, 1 << len, 1), NTT(y, 1 << len, 1);
	for (int i = 0; i < (1 << len); ++i) x[i] = (ll)x[i] * y[i] % Mod;
	NTT(x, 1 << len, 0);
	
	for (int i = 1; i <= n; ++i) 
		printf("%d\n", (int)(((ll)n * calc(n, i) % Mod - (ll)Ifac[i] * x[n + i] % Mod + Mod) % Mod));
	return 0;
}

Submission Info

Judge Result