Submission #906962

---

Source Code Expand

// In the name of God

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0, _n = (int)(n); i < _n; ++i)
#define int long long
const int N = 1 << 20, lg = 20, mod = 924844033;
int pw(int a, int b) { return b != 0? ll(pw(ll(a) * a % mod, b >> 1)) * (b & 1? a: 1) % mod: 1; }
int rev[N];
vector<int> adj[N];
void NTT(int a[], bool inverse) {
    rep(i, N)
        if (rev[i] > i)
            swap(a[rev[i]], a[i]);
    for (int len = 2; len <= N; len <<= 1) {
        int wn = pw(3, (mod - 1) / len / 2);
        if (inverse)
            wn = pw(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) {
        int div = pw(N, mod - 2);
        rep(i, N)
            a[i] = ll(a[i]) * div % mod;
    }
}

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

int n, f[N], a[N], b[N], c[N], inv[N], sz[N];

void dfs(int v, int p = 0) {
    sz[v] = 1;
    for (int u : adj[v])
        if (u != p)
            dfs(u, v), sz[v] += sz[u];
    a[sz[v]]++;
    a[n - sz[v]]++;
}
int res[N];
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    gen();
    f[0] = inv[0] = 1;
    for (int i = 1; i < N; ++i)
        f[i] = f[i - 1] * i % mod, inv[i] = pw(f[i], mod - 2);
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(0);
    for (int i = 0; i < N; ++i)
        a[i] = a[i] * f[i] % mod;
    int maxn = N / 4;
    for (int i = maxn; i >= 0; --i)
        b[i] = inv[maxn - i];
    NTT(a, false);
    NTT(b, false);
    for (int i = 0; i < N; ++i)
        c[i] = a[i] * b[i] % mod;
    NTT(c, true);
    for (int i = 0; i < maxn; ++i)
        res[i] = c[i + maxn];
    for (int i = 1; i <= n; ++i) {
        cout << inv[i] * ((f[n] * (n + 1) % mod * inv[n - i] % mod - res[i] + mod) % mod) % mod<< '\n';
    }
}

Submission Info

Judge Result