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
Submission Time | |
---|---|
Task | F - Many Easy Problems |
User | Reyna |
Language | C++14 (GCC 5.4.1) |
Score | 1900 |
Code Size | 2872 Byte |
Status | AC |
Exec Time | 997 ms |
Memory | 94080 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1900 / 1900 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0, example1, example2 |
All | doublestar0, doublestar1, doublestar2, doublestar3, doublestar4, example0, example1, example2, line0, line1, line2, line3, line4, maxrand0, maxrand1, maxrand10, maxrand11, maxrand12, maxrand13, maxrand14, maxrand15, maxrand16, maxrand17, maxrand18, maxrand19, maxrand2, maxrand3, maxrand4, maxrand5, maxrand6, maxrand7, maxrand8, maxrand9, rand0, rand1, rand2, rand3, rand4, rand5, rand6, rand7, rand8, rand9, star0, star1, star2, star3, star4 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
doublestar0 | AC | 888 ms | 86516 KB |
doublestar1 | AC | 887 ms | 86516 KB |
doublestar2 | AC | 884 ms | 86516 KB |
doublestar3 | AC | 887 ms | 86516 KB |
doublestar4 | AC | 887 ms | 86516 KB |
example0 | AC | 804 ms | 76032 KB |
example1 | AC | 805 ms | 76032 KB |
example2 | AC | 810 ms | 76032 KB |
line0 | AC | 988 ms | 94080 KB |
line1 | AC | 992 ms | 94080 KB |
line2 | AC | 997 ms | 94080 KB |
line3 | AC | 993 ms | 94080 KB |
line4 | AC | 989 ms | 94080 KB |
maxrand0 | AC | 962 ms | 87040 KB |
maxrand1 | AC | 966 ms | 87040 KB |
maxrand10 | AC | 970 ms | 87040 KB |
maxrand11 | AC | 962 ms | 87040 KB |
maxrand12 | AC | 985 ms | 87040 KB |
maxrand13 | AC | 958 ms | 87040 KB |
maxrand14 | AC | 958 ms | 87040 KB |
maxrand15 | AC | 957 ms | 87040 KB |
maxrand16 | AC | 964 ms | 87040 KB |
maxrand17 | AC | 962 ms | 87040 KB |
maxrand18 | AC | 963 ms | 87040 KB |
maxrand19 | AC | 960 ms | 87040 KB |
maxrand2 | AC | 958 ms | 87040 KB |
maxrand3 | AC | 960 ms | 87040 KB |
maxrand4 | AC | 956 ms | 87040 KB |
maxrand5 | AC | 963 ms | 87040 KB |
maxrand6 | AC | 967 ms | 87040 KB |
maxrand7 | AC | 959 ms | 87040 KB |
maxrand8 | AC | 958 ms | 87040 KB |
maxrand9 | AC | 958 ms | 87040 KB |
rand0 | AC | 835 ms | 76160 KB |
rand1 | AC | 819 ms | 76032 KB |
rand2 | AC | 834 ms | 76160 KB |
rand3 | AC | 834 ms | 76160 KB |
rand4 | AC | 831 ms | 76032 KB |
rand5 | AC | 836 ms | 76160 KB |
rand6 | AC | 835 ms | 76160 KB |
rand7 | AC | 836 ms | 76160 KB |
rand8 | AC | 828 ms | 76032 KB |
rand9 | AC | 830 ms | 76160 KB |
star0 | AC | 877 ms | 87280 KB |
star1 | AC | 879 ms | 87280 KB |
star2 | AC | 880 ms | 87280 KB |
star3 | AC | 878 ms | 87280 KB |
star4 | AC | 880 ms | 87280 KB |