Submission #1804530
Source Code Expand
#include <cstdio>
#include <iostream>
#include <algorithm>
typedef long long ll;
const int N = 2e5 + 5;
const int LEN = 524288;
const int G = 5;
const int Mod = 924844033;
int n, fac[N], Ifac[N], que[N], qn, fa[N], sze[N], num[N];
int tot, first[N << 1], next[N << 1], end[N << 1];
int len, w[2][LEN], R[LEN], x[LEN], y[LEN];
inline int Get() {
char ch;
while ((ch = getchar()) < '0' || ch > '9');
int Num = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9')
Num = (Num << 3) + (Num << 1) + ch - '0';
return Num;
}
inline void AddEdge(int x, int y) {
next[++tot] = first[x], first[x] = tot, end[tot] = y;
next[++tot] = first[y], first[y] = tot, end[tot] = x;
}
inline int pow(int x, int k) {
ll res = 1, r = x;
for (; k; k >>= 1, r = r * r % Mod)
if (k & 1) res = res * r % Mod;
return res;
}
void NTT(int *a, int n, int res) {
for (int i = 0; i < n; ++i) if (i < R[i]) std :: swap(a[i], a[R[i]]);
for (int k = 1; k < n; k <<= 1) {
int x = w[res][n / k / 2];
for (int str = 0; str < n; str += k << 1) {
int wx = 1;
for (int i = str; i < str + k; ++i) {
int u1 = a[i], u2 = (ll)wx * a[i + k] % Mod;
a[i] = (u1 + u2) % Mod;
a[i + k] = (u1 - u2 + Mod) % Mod;
wx = (ll)wx * x % Mod;
}
}
}
if (!res) {
int Inv = pow(n, Mod - 2);
for (int i = 0; i < n; ++i) a[i] = (ll)a[i] * Inv % Mod;
}
}
inline void Init(int n) {
len = 0;
while ((1 << len) <= n) ++len;
int x = pow(G, (Mod - 1) / (1 << len));
w[0][0] = w[1][0] = 1;
for (int i = 1; i < (1 << len); ++i) {
R[i] = (R[i >> 1] >> 1) | ((i & 1) << len - 1);
w[0][(1 << len) - i] = w[1][i] = (ll)w[1][i - 1] * x % Mod;
}
}
inline int calc(int n, int m) {
return (ll)fac[n] * Ifac[m] % Mod * Ifac[n - m] % Mod;
}
int main() {
n = Get();
for (int i = 1, u, v; i < n; ++i)
u = Get(), v = Get(), AddEdge(u, v);
que[qn = 1] = 1, fa[1] = 0;
for (int ql = 1, u; u = que[ql], ql <= qn; sze[u] = 1, ++ql)
for (int k = first[u], v; v = end[k], k; k = next[k])
if (v != fa[u]) fa[v] = u, que[++qn] = v;
for (int qr = qn, u; u = que[qr], qr > 1; --qr) sze[fa[u]] += sze[u];
for (int i = 2; i <= n; ++i) ++num[sze[i]], ++num[n - sze[i]];
fac[0] = 1;
for (int i = 1; i <= n; ++i) fac[i] = (ll)fac[i - 1] * i % Mod;
Ifac[n] = pow(fac[n], Mod - 2);
for (int i = n; i; --i) Ifac[i - 1] = (ll)Ifac[i] * i % Mod;
for (int i = 1; i <= n; ++i) x[i] = (ll)num[i] * fac[i] % Mod;
for (int i = 0; i <= n; ++i) y[n - i] = Ifac[i];
Init(2 * n), NTT(x, 1 << len, 1), NTT(y, 1 << len, 1);
for (int i = 0; i < (1 << len); ++i) x[i] = (ll)x[i] * y[i] % Mod;
NTT(x, 1 << len, 0);
for (int i = 1; i <= n; ++i)
printf("%d\n", (int)(((ll)n * calc(n, i) % Mod - (ll)Ifac[i] * x[n + i] % Mod + Mod) % Mod));
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Many Easy Problems |
User |
wy1627 |
Language |
C++14 (GCC 5.4.1) |
Score |
1900 |
Code Size |
2824 Byte |
Status |
AC |
Exec Time |
181 ms |
Memory |
21760 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 |
172 ms |
21760 KB |
doublestar1 |
AC |
172 ms |
21760 KB |
doublestar2 |
AC |
172 ms |
21760 KB |
doublestar3 |
AC |
175 ms |
21760 KB |
doublestar4 |
AC |
175 ms |
21760 KB |
example0 |
AC |
4 ms |
16640 KB |
example1 |
AC |
4 ms |
16640 KB |
example2 |
AC |
4 ms |
16640 KB |
line0 |
AC |
175 ms |
21760 KB |
line1 |
AC |
174 ms |
21760 KB |
line2 |
AC |
175 ms |
21760 KB |
line3 |
AC |
175 ms |
21760 KB |
line4 |
AC |
179 ms |
21760 KB |
maxrand0 |
AC |
179 ms |
21760 KB |
maxrand1 |
AC |
181 ms |
21760 KB |
maxrand10 |
AC |
179 ms |
21760 KB |
maxrand11 |
AC |
179 ms |
21760 KB |
maxrand12 |
AC |
179 ms |
21760 KB |
maxrand13 |
AC |
179 ms |
21760 KB |
maxrand14 |
AC |
179 ms |
21760 KB |
maxrand15 |
AC |
181 ms |
21760 KB |
maxrand16 |
AC |
179 ms |
21760 KB |
maxrand17 |
AC |
180 ms |
21760 KB |
maxrand18 |
AC |
178 ms |
21760 KB |
maxrand19 |
AC |
178 ms |
21760 KB |
maxrand2 |
AC |
181 ms |
21760 KB |
maxrand3 |
AC |
179 ms |
21760 KB |
maxrand4 |
AC |
179 ms |
21760 KB |
maxrand5 |
AC |
178 ms |
21760 KB |
maxrand6 |
AC |
179 ms |
21760 KB |
maxrand7 |
AC |
180 ms |
21760 KB |
maxrand8 |
AC |
179 ms |
21760 KB |
maxrand9 |
AC |
178 ms |
21760 KB |
rand0 |
AC |
6 ms |
16640 KB |
rand1 |
AC |
4 ms |
16640 KB |
rand2 |
AC |
5 ms |
16640 KB |
rand3 |
AC |
6 ms |
16768 KB |
rand4 |
AC |
5 ms |
16640 KB |
rand5 |
AC |
6 ms |
16768 KB |
rand6 |
AC |
5 ms |
16640 KB |
rand7 |
AC |
6 ms |
16768 KB |
rand8 |
AC |
5 ms |
16640 KB |
rand9 |
AC |
5 ms |
16640 KB |
star0 |
AC |
172 ms |
21760 KB |
star1 |
AC |
170 ms |
21760 KB |
star2 |
AC |
171 ms |
21760 KB |
star3 |
AC |
171 ms |
21760 KB |
star4 |
AC |
171 ms |
21760 KB |