Submission #1515128

---

Source Code Expand

#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 2e5 + 10, mod = 924844033;

ll n, fact[N], inv[N], sz[N], res[N];
vector<int> adj[N];


ll power(ll a, ll b){
	if(b == 0)return 1;
	ll ret = power(a, b/2);
	ret *= ret; ret %= mod;
	if(b % 2)ret *= a, ret %= mod;
	return ret;
}

ll comb(int n, int k){
	if(k < 0 || k > n)return 0;
	ll ret = fact[n];
	ret *= inv[k]; ret %= mod;
	ret *= inv[n - k]; ret %= mod;
	return ret;
}

void dfs(int v, int p = -1){
	sz[v]++;
	for(auto u : adj[v]){
		if(u == p)continue;
		dfs(u, v);
		for(int i=1; i<=sz[u]; i++)
			res[i] = (res[i] + mod - comb(sz[u], i)), res[i] %= mod;
		sz[v] += sz[u];
	}

	for(int i=1; i<=n-sz[v]; i++)
		res[i] = (res[i] + mod - comb(n-sz[v], i)), res[i] %= mod;

}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> n;
	for(int i=0; i<n-1; i++){
		int u, v; cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	fact[0] = 1;
	for(int i=1; i<N; i++)
		fact[i] = (1LL * fact[i - 1] * i) % mod;

	inv[N - 1] = power(fact[N - 1], mod - 2);
	for(int i=N-2; i>=0; i--)
		inv[i] = (1LL * inv[i + 1] * (i + 1)) % mod;

	dfs(1);

	for(int i=1; i<=n; i++){
		res[i] += (1LL * n * comb(n, i)) % mod;
		res[i] %= mod;
		cout << res[i] << '\n';

	}
}

Submission Info

Judge Result