Submission #2381519

---

Source Code Expand

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

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const ll MOD = 924844033;

struct NumberTheoreticTransform {
    int mod;
    int root;

    NumberTheoreticTransform(int mod, int root) : mod(mod), root(root) {}

    int mul(int x, int y) {
        return int64_t(x) * y % mod;
    }

    int add(int x, int y) {
        return (x += y) >= mod ? x - mod : x;
    }

    int pow(int x, int y) {
        int res = 1;
        while (y > 0) {
            if (y & 1) res = mul(res, x);
            x = mul(x, x);
            y >>= 1;
        }
        return res;
    }

    int inv(int x) {
        return pow(x, mod - 2);
    }

    void ntt(std::vector<int> &a, bool rev = false) {
        int n = a.size();
        int h = 0;
        for (int i = 0; 1 << i < n; i++) h++;
        for (int i = 0; i < n; i++) {
            int j = 0;
            for (int k = 0; k < h; k++) {
            	j |= (i >> k & 1) << (h - 1 - k);
            }
            if (i < j) std::swap(a[i], a[j]);
        }
        for (int i = 1; i < n; i *= 2) {
            int w = pow(root, (mod - 1) / (i * 2));
            if (rev) w = inv(w);
            for (int j = 0; j < n; j += i * 2) {
                int wn = 1;
                for (int k = 0; k < i; k++) {
                    int s = a[j + k + 0];
                    int t = mul(a[j + k + i], wn);
                    a[j + k + 0] = add(s, t);
                    a[j + k + i] = add(s, mod - t);
                    wn = mul(wn, w);
                }
            }
        }
        int v = inv(n);
        if (rev) for (int i = 0; i < n; i++) a[i] = mul(a[i], v);
    }

    std::vector<int> mul(std::vector<int> a, std::vector<int> b) {
        int s = a.size() + b.size() - 1;
        int t = 1;
        while (t < s) t *= 2;
        a.resize(t);
        b.resize(t);
        ntt(a);
        ntt(b);
        for (int i = 0; i < t; i++) {
            a[i] = mul(a[i], b[i]);
        }
        ntt(a, true);

        a.resize(s);
        return a;
    }
};

const int MN = 400010;

int N;
vi g[MN];
int num[MN], sz[MN];
ll fac[MN], ifac[MN], inv[MN];

void dfs(int v, int p)
{
	sz[v] = 1;
	for (int to : g[v]) if (to != p) {
		dfs(to, v);
		sz[v] += sz[to];
		++num[sz[to]];
	}
	if (p != -1) {
		++num[N - sz[v]];
	}
}

int main() {
	inv[1] = 1;
    for (int i = 2; i < MN; ++i) {
        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;	
    }
	fac[0] = ifac[0] = 1;

	for (int i = 1; i < MN; ++i) {
		fac[i] = fac[i-1] * i % MOD;
		ifac[i] = ifac[i-1] * inv[i] % MOD;
	}

	cin >> N;

	rep(i, N-1) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		g[a].pb(b); g[b].pb(a);
	}

	dfs(0, -1);

	vi a(N+1), b(N+1);

	rep(i, N+1) {
		a[i] = (ll)num[i] * fac[i] % MOD;
		b[i] = ifac[N-i];
	}

    NumberTheoreticTransform ntt(MOD, 5);

    a = ntt.mul(a, b);

    for (int i = 1; i <= N; ++i) {
    	ll x = a[N + i] * ifac[i] % MOD;
    	ll t = N * fac[N] % MOD * ifac[i] % MOD * ifac[N-i] % MOD;
    	t -= x;
    	if (t < 0) t += MOD;
    	cout << t << endl;
    }

    return 0;
}

Submission Info

Judge Result