Submission #4044465
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] = (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:14:09+0900
Task
F - Many Easy Problems
User
PinkRabbit
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2256 Byte
Status
WA
Exec Time
291 ms
Memory
22528 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
0 / 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
WA
248 ms
14464 KB
doublestar1
WA
248 ms
14464 KB
doublestar2
WA
253 ms
14464 KB
doublestar3
WA
251 ms
14464 KB
doublestar4
WA
251 ms
14464 KB
example0
AC
4 ms
10368 KB
example1
AC
4 ms
10368 KB
example2
AC
4 ms
10368 KB
line0
WA
291 ms
22528 KB
line1
WA
291 ms
22400 KB
line2
WA
291 ms
22400 KB
line3
WA
291 ms
22400 KB
line4
WA
291 ms
22400 KB
maxrand0
WA
277 ms
14464 KB
maxrand1
WA
277 ms
14464 KB
maxrand10
WA
276 ms
14464 KB
maxrand11
WA
276 ms
14464 KB
maxrand12
WA
275 ms
14464 KB
maxrand13
WA
276 ms
14464 KB
maxrand14
WA
275 ms
14464 KB
maxrand15
WA
276 ms
14464 KB
maxrand16
WA
276 ms
14464 KB
maxrand17
WA
275 ms
14464 KB
maxrand18
WA
275 ms
14464 KB
maxrand19
WA
275 ms
14464 KB
maxrand2
WA
275 ms
14464 KB
maxrand3
WA
277 ms
14464 KB
maxrand4
WA
276 ms
14464 KB
maxrand5
WA
278 ms
14464 KB
maxrand6
WA
280 ms
14464 KB
maxrand7
WA
277 ms
14464 KB
maxrand8
WA
277 ms
14464 KB
maxrand9
WA
275 ms
14464 KB
rand0
WA
6 ms
10496 KB
rand1
WA
4 ms
10368 KB
rand2
WA
5 ms
10496 KB
rand3
WA
6 ms
10496 KB
rand4
WA
4 ms
10368 KB
rand5
WA
6 ms
10496 KB
rand6
WA
5 ms
10496 KB
rand7
WA
6 ms
10496 KB
rand8
WA
4 ms
10368 KB
rand9
WA
5 ms
10368 KB
star0
WA
245 ms
14464 KB
star1
WA
246 ms
14464 KB
star2
WA
245 ms
14464 KB
star3
WA
244 ms
14464 KB
star4
WA
244 ms
14464 KB