Submission #1470810

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define e1 first
#define e2 second
#define pb push_back
#define mp make_pair
#define boost ios_base::sync_with_stdio(false)
#define eb emplace_back
#define OUT(x) {cout << x; exit(0); }
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define scanf(...) scanf(__VA_ARGS__)?:0
typedef long long int ll;
#define int long long
typedef unsigned long long ull;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair <PLL, int> PLLI;
typedef pair <PLL, PLL> PP;
typedef pair <PII, int> PPI;
typedef pair <ll, int> PLI;
typedef unsigned int ui;
const int inf = 1e9+9;
const int mod = 924844033;
const int N = (1 << 20);
const int lg = 20;
int rev[N];

inline ll potmod(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1) res = (res * a)%mod;
		a = (a * a)%mod;
		b >>= 1;
	}
	return res;
}

void compute(int bit = lg - 1, int x = 0, int y = 0)
{
	if (bit == -1)
	{
		rev[y] = x;
		return;
	}
	compute(bit - 1, x, y);
	compute(bit - 1, x + (1 << bit), y + (1 << (lg - bit - 1)));
}

void NTT(int a[], bool inverse)
{
	FOR(i, 0, N-1)
		if (rev[i] > i) swap(a[rev[i]], a[i]);
	
	for (int len = 2; len <= N; len *= 2)
	{
		int wn = potmod(3, (mod -1)/len/2);
		if (inverse) wn = potmod(wn, mod - 2);
		for (int j=0; j<N; j+=len)
		{
			int w = 1;
			for (int x = j, y = j + len / 2; y < j + len; ++x, ++y) 
			{
				int u = a[x], v = (ll)a[y] * w % mod;
				a[x] = u + v;
				a[y] = u - v + mod;
				while (a[x] >= mod) a[x] -= mod;
				while (a[y] >= mod) a[y] -= mod;
				w = (ll)w * wn % mod;
			}
		}
	}	
	
	if (inverse)
	{
		ll w = potmod(N, mod - 2);
		FOR(i, 0, N-1) a[i] = (ll)a[i] * w % mod;
	}
}

ll fac[N], invfac[N];
int n, a[N], b[N], c[N], sz[N], res[N];
vector <int> adj[N];
void dfs(int x, int p = 0)
{
	sz[x] = 1;
	for (auto u : adj[x])
		if (u != p)
		{
			dfs(u, x);
			sz[x] += sz[u];
		}
	a[sz[x]]++;
	a[n - sz[x]]++;
}
int32_t main()
{
	boost;
	compute();
	fac[0] = 1, invfac[0] = 1;
	FOR(i, 1, N-1) fac[i] = (fac[i-1] * i)%mod;
	invfac[N-1] = potmod(fac[N-1], mod - 2);
	for (int i=N-2; i>0; --i) invfac[i] = invfac[i + 1] * (i + 1)%mod;
	cin >> n;
	FOR(i, 2, n)
	{
		int aa, bb;
		cin >> aa >> bb;
		adj[aa].pb(bb);
		adj[bb].pb(aa);
	}
	dfs(1);
	FOR(i, 0, N-1) a[i] = (ll)a[i] * fac[i] % mod;
	int maxn = (1 << 18);
	for (int i=maxn; i>=0; --i) b[i] = invfac[maxn - i];
	NTT(a, false);
	NTT(b, false);
	FOR(i, 0, N-1) c[i] = (ll)a[i] * b[i] % mod;
	NTT(c, true);
	FOR(i, 0, maxn-1) res[i] = c[i + maxn];
	FOR(i, 1, n) cout << invfac[i] * ((fac[n] * (n + 1) % mod * invfac[n - i] %mod -res[i] + mod) % mod)%mod << "\n";
}

Submission Info

Judge Result