Submission #41479722

---

Source Code Expand

#include <bits/stdc++.h>
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
const int N = 2e5 + 10, MOD = 924844033;
int n, sz[N], fac[N], ifac[N], inv[N];
vector <int> v[N], a;
void dfs(int x, int fa) {
	sz[x] = 1;
	for (int i: v[x])
		if (i != fa) {
			dfs(i, x);
			a[sz[i]]++;
			sz[x] += sz[i];
		}
	a[n - sz[x]]++;
}
inline int Quickpow(int x, int y = MOD - 2) {
	int ans = 1;
	for (; y; x = (ll) x * x % MOD, y >>= 1)
		if (y & 1) ans = (ll) ans * x % MOD;
	return ans;
}
namespace NTT {
	const int N = (1 << 21) + 10;
	int rev[N], lim;
	void ntt(int *f, int flag) {
		F(i, 0, lim - 1)
			if (i < rev[i]) swap(f[i], f[rev[i]]);
		for (int len = 2, t = 1; len <= lim; len <<= 1, t <<= 1) {
			int r = Quickpow(5, ((MOD - 1) / len * flag + MOD - 1) % (MOD - 1));
			for (int i = 0; i < lim; i += len) {
				int tt = 1;
				for (int j = i; j < i + t; j++) {
					int A = f[j], B = (ll) f[j + t] * tt % MOD;
					f[j] = A + B; if (f[j] > MOD) f[j] -= MOD;
					f[j + t] = A - B; if (f[j + t] < 0) f[j + t] += MOD;
					tt = (ll) tt * r % MOD;
				}
			}
		}
		if (flag == -1) {
			int t = Quickpow(lim);
			F(i, 0, lim - 1) f[i] = (ll) f[i] * t % MOD;
		}
	}
	vector <int> solve(vector <int> a, vector <int> b) {
		int sum = SZ(a) + SZ(b);
		int s = -1;
		for (lim = 1; lim <= sum; lim <<= 1, s++);
		a.resize(lim), b.resize(lim);
		F(i, 1, lim - 1) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << s);
		ntt(a.data(), 1); ntt(b.data(), 1);
		F(i, 0, lim - 1) a[i] = (ll) a[i] * b[i] % MOD;
		ntt(a.data(), -1);
		a.resize(sum + 1);
		return a;
	}
}
void init(int n) {
	fac[0] = ifac[0] = inv[1] = 1;
	F(i, 2, n) inv[i] = (ll) (MOD - MOD / i) * inv[MOD % i] % MOD;
	F(i, 1, n) fac[i] = (ll) fac[i - 1] * i % MOD, ifac[i] = (ll) ifac[i - 1] * inv[i] % MOD;
}
int C(int n, int m) {
	return m < 0 || n < m ? 0 : (ll) fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}
signed main() {
	read(n);
	init(n);
	F(i, 2, n) {
		int x, y; read(x), read(y);
		v[x].push_back(y);
		v[y].push_back(x);
	} a.resize(n);
	dfs(1, 0);
	F(i, 0, n - 1) a[i] = (ll) a[i] * fac[i] % MOD;
	vector <int> b(n);
	F(i, 0, n - 1) b[n - 1 - i] = ifac[i];// * ((i & 1) ? MOD - 1 : 1) % MOD;
	// F(i, 0, n - 1) cout << a[i] << " "; cout << endl;
	// F(i, 0, n - 1) cout << b[i] << " "; cout << endl;
	vector <int> c = NTT::solve(a, b);
	// F(i, 0, 2 * n - 2) cout << c[i] << " "; cout << endl;
	F(i, n, 2 * n - 1) {
		int ans = (ll) C(n, i - (n - 1)) * n % MOD - (ll) c[i] * ifac[i - (n - 1)] % MOD + MOD;
		cout << ans % MOD << '\n';
	}
	return 0;
}

Submission Info

Judge Result