Submission #1835659

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 924844033;
const int MAXN = 200010;

inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch=='-') f=-1;
	for(; isdigit(ch); ch = getchar()) x = (x*10)+(ch^48);
	return x * f;
}

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

int len, d, r[550000];
ll invlen, w[550000][2];

inline void NTT_init() {
	int i;
	invlen = qpow(len, MOD-2);
	for(i = 0; i < len; i++) r[i] = (r[i>>1]>>1)|((i&1)<<(d-1));
	ll g = qpow(5, (MOD-1)>>d);
	w[0][0] = w[len][0] = 1;
	for(i = 1; i < len; i++) w[i][0] = w[i-1][0]*g%MOD;
	for(i = 0; i <= len; i++) w[i][1] = w[len-i][0];
}

inline void NTT(ll a[], int t) {
	int i, j, k;
	for(i = 0; i < len; i++) if(i < r[i]) swap(a[i], a[r[i]]);
	for(i = 2; i <= len; i<<=1) 
		for(j = 0; j < len; j += i) 
			for(k = 0; k < (i>>1); k++) {
				ll val = a[j+k+(i>>1)]*w[(len/i)*k][t]%MOD;
				a[j+k+(i>>1)] = ((a[j+k]-val)%MOD+MOD)%MOD;
				a[j+k] = (a[j+k]+val)%MOD;
			}
}

ll a[550000], b[550000], fac[MAXN], ifac[MAXN];
int e, st[MAXN], to[MAXN<<1];
int nxt[MAXN<<1];
inline void Add(int u, int v) {
	to[++e] = v, nxt[e] = st[u];
	st[u] = e;
}

int n, c[MAXN];
ll pre[MAXN], ans[MAXN];

int dfs(int u, int fa) {
	int i, sz = 1;
	for(i = st[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == fa) continue;
		sz += dfs(v, u);
	}
	if(u != 1) c[sz]++;
	return sz;
}

inline ll C(int x, int y) {
	return fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;
}

int main() {

	int i;
	n = read();
	fac[0] = 1;
	for(i = 1; i <= n; i++) fac[i] = fac[i-1]*i%MOD;
	ifac[n] = qpow(fac[n], MOD-2);
	for(i = n; i >= 1; i--) ifac[i-1] = ifac[i]*i%MOD;

	for(i = 1; i < n; i++) {
		int u = read(), v = read();
		Add(u, v), Add(v, u);
	}
	dfs(1, 0);
	for(i = 1; i <= n; i++) pre[i] = pre[i-1]+c[i];
	for(i = 1; i <= n; i++) 
		ans[i] = C(n, i)*(1+pre[n])%MOD;
	for(len = 1; len <= (n<<1); len<<=1) d++;
	NTT_init();
	for(i = 0; i <= n; i++) a[i] = c[i]*fac[i]%MOD, b[i] = ifac[n-i];
	/*for(i = 0; i <= n; i++) printf("%lld ", a[i]);
	printf("\n");
	for(i = 0; i <= n; i++) printf("%lld ", b[i]);
	printf("\n");*/
	NTT(a, 0), NTT(b, 0);
	for(i = 0; i < len; i++) a[i] = a[i]*b[i]%MOD;
	NTT(a, 1);
	for(i = n+1; i < len; i++) 
		ans[i-n] = ((ans[i-n]-a[i]*invlen%MOD*ifac[i-n]%MOD)%MOD+MOD)%MOD;
	/*for(i = 0; i < len; i++) printf("%lld ", a[i]*invlen%MOD);
	printf("\n");
	printf(":%lld\n", len*invlen%MOD);*/

	for(i = 0; i < len; i++) a[i] = b[i] = 0;
	for(i = 0; i <= n; i++) a[i] = c[n-i]*fac[i]%MOD, b[i] = ifac[n-i];
	NTT(a, 0), NTT(b, 0);
	for(i = 0; i < len; i++) a[i] = a[i]*b[i]%MOD;
	NTT(a, 1);
	for(i = n+1; i < len; i++)
		ans[i-n] = ((ans[i-n]-a[i]*invlen%MOD*ifac[i-n]%MOD)%MOD+MOD)%MOD;

	for(i = 1; i <= n; i++) printf("%lld\n", ans[i]);
	return 0;
}

Submission Info

Judge Result