Submission #4044480
Source Code Expand
#include <cstdio>
inline void swap(int &x, int &y) { x ^= y ^= x ^= y; }
typedef long long LL;
const int MN = 200005;
const int MS = 524288;
const int Mod = 924844033;
const int G = 5, iG = 554906420;
inline int qPow(int b, int e) {
int a = 1;
for (; e; b = (LL)b * b % Mod, e >>= 1)
if (e & 1) a = (LL)a * b % Mod;
return a;
}
int N;
int h[MN], nxt[MN * 2], to[MN * 2], tot;
inline void ins(int x, int y) {
nxt[++tot] = h[x], to[tot] = y, h[x] = tot;
}
int Inv[MN], Fac[MN], iFac[MN];
int R[MS], A[MS], B[MS];
void Init(int N) {
Inv[1] = 1;
for (int i = 2; i <= N; ++i) {
Inv[i] = (LL)(Mod - Mod / i) * Inv[Mod % i] % Mod;
}
Fac[0] = iFac[0] = 1;
for (int i = 1; i <= N; ++i) {
Fac[i] = (LL)Fac[i - 1] * i % Mod;
iFac[i] = (LL)iFac[i - 1] * Inv[i] % Mod;
}
}
int DFS(int u, int f) {
int sz = 1, sv;
for (int i = h[u]; i; i = nxt[i]) if (to[i] != f) {
sz += sv = DFS(to[i], u);
--A[sv], --A[N - sv];
} return sz;
}
void FNTT(int *A, int Sz, int Ty) {
for (int i = 0; i < Sz; ++i)
if (R[i] < i) swap(A[R[i]], A[i]);
for (int j = 1; j < Sz; j <<= 1) {
int j2 = j << 1, wn = qPow(~Ty ? G : iG, (Mod - 1) / j2);
for (int i = 0; i < Sz; i += j2) {
for (int k = 0, w = 1; k < j; ++k, w = (LL)w * wn % Mod) {
int X = A[i + k], Y = (LL)w * A[i + j + k] % Mod;
A[i + k] = X + Y; if (A[i + k] >= Mod) A[i + k] -= Mod;
A[i + j + k] = X - Y; if (A[i + j + k] < 0) A[i + j + k] += Mod;
}
}
}
if (Ty == -1) {
int InvSz = qPow(Sz, Mod - 2);
for (int i = 0; i < Sz; ++i) A[i] = (LL)A[i] * InvSz % Mod;
}
}
int main() {
scanf("%d", &N);
Init(N);
for (int i = 1, x, y; i < N; ++i) {
scanf("%d%d", &x, &y);
ins(x, y), ins(y, x);
}
DFS(1, 0), A[N] = N;
for (int i = 1; i <= N; ++i) A[i] = ((LL)A[i] * Fac[i] % Mod + Mod) % Mod;
for (int i = 0; i < N; ++i) B[i] = iFac[N - 1 - i];
int Sz = 1, Bt = 0;
for (; Sz < N + N; Sz <<= 1, ++Bt) ;
for (int i = 0; i < Sz; ++i) R[i] = R[i >> 1] >> 1 | (i & 1) << (Bt - 1);
FNTT(A, Sz, 1), FNTT(B, Sz, 1);
for (int i = 0; i < Sz; ++i) A[i] = (LL)A[i] * B[i] % Mod;
FNTT(A, Sz, -1);
for (int i = 1; i <= N; ++i) printf("%d\n", (LL)A[i + N - 1] * iFac[i] % Mod);
return 0;
}
Submission Info
Submission Time
2019-01-19 18:16:17+0900
Task
F - Many Easy Problems
User
PinkRabbit
Language
C++14 (GCC 5.4.1)
Score
1900
Code Size
2260 Byte
Status
AC
Exec Time
290 ms
Memory
22400 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:82:78: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘LL {aka long long int}’ [-Wformat=]
for (int i = 1; i <= N; ++i) printf("%d\n", (LL)A[i + N - 1] * iFac[i] % Mod);
^
./Main.cpp:67:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
./Main.cpp:70:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
^
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
249 ms
14464 KB
doublestar1
AC
248 ms
14464 KB
doublestar2
AC
248 ms
14464 KB
doublestar3
AC
247 ms
14464 KB
doublestar4
AC
248 ms
14464 KB
example0
AC
2 ms
10368 KB
example1
AC
2 ms
10368 KB
example2
AC
2 ms
10368 KB
line0
AC
290 ms
22400 KB
line1
AC
290 ms
22400 KB
line2
AC
290 ms
22400 KB
line3
AC
290 ms
22400 KB
line4
AC
288 ms
22400 KB
maxrand0
AC
273 ms
14464 KB
maxrand1
AC
275 ms
14464 KB
maxrand10
AC
272 ms
14464 KB
maxrand11
AC
273 ms
14464 KB
maxrand12
AC
273 ms
14464 KB
maxrand13
AC
272 ms
14464 KB
maxrand14
AC
272 ms
14464 KB
maxrand15
AC
272 ms
14464 KB
maxrand16
AC
280 ms
14464 KB
maxrand17
AC
272 ms
14464 KB
maxrand18
AC
272 ms
14464 KB
maxrand19
AC
272 ms
14592 KB
maxrand2
AC
272 ms
14464 KB
maxrand3
AC
272 ms
14464 KB
maxrand4
AC
275 ms
14464 KB
maxrand5
AC
278 ms
14464 KB
maxrand6
AC
272 ms
14464 KB
maxrand7
AC
272 ms
14464 KB
maxrand8
AC
272 ms
14464 KB
maxrand9
AC
272 ms
14464 KB
rand0
AC
5 ms
10496 KB
rand1
AC
3 ms
10368 KB
rand2
AC
4 ms
10496 KB
rand3
AC
5 ms
10496 KB
rand4
AC
3 ms
10368 KB
rand5
AC
5 ms
10496 KB
rand6
AC
4 ms
10496 KB
rand7
AC
5 ms
10496 KB
rand8
AC
3 ms
10368 KB
rand9
AC
4 ms
10368 KB
star0
AC
245 ms
14464 KB
star1
AC
245 ms
14464 KB
star2
AC
245 ms
14464 KB
star3
AC
245 ms
14464 KB
star4
AC
245 ms
14464 KB