Submission #3494416
Source Code Expand
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int G = 5;
const int N = 1 << 20;
const int mod = 924844033;
int n, E;
int fir[N], nex[N], arr[N];
LL A[N], B[N], fac[N], inv[N], fav[N], res[N];
inline void Add_Edge(int x, int y) {
nex[++E] = fir[x];
fir[x] = E; arr[E] = y;
}
LL Qpow(LL x, int p) {
LL ans = 1;
while (p) {
if (p & 1) ans = ans * x % mod;
x = x * x % mod;
p >>= 1;
}
return ans;
}
LL Inv(LL x) {
return Qpow(x, mod - 2);
}
LL C(int x, int y) {
if (x < y) return 0;
return fac[x] * fav[y] % mod * fav[x - y] % mod;
}
namespace init {
int siz[N], num[N];
void dfs(int x, int fa) {
siz[x] = 1;
for (int i = fir[x]; i; i = nex[i]) {
if (arr[i] == fa) continue;
dfs(arr[i], x);
++num[siz[arr[i]]];
siz[x] += siz[arr[i]];
}
++num[n - siz[x]];
}
void main() {
dfs(1, 0);
fac[0] = fav[0] = 1;
inv[1] = fav[1] = fac[1] = 1;
for (int i = 2; i < N; ++i) {
inv[i] = -mod / i * inv[mod % i] % mod + mod;
fac[i] = fac[i - 1] * i % mod;
fav[i] = fav[i - 1] * inv[i] % mod;
}
for (int i = 0; i <= n; ++i) {
A[i] = num[i] * fac[i] % mod;
if (A[i] < 0) A[i] += mod;
B[i] = fav[n - i];
}
}
}
namespace convolution {
int rev[N];
void NTT(LL *a, int lim, int type) {
for (int i = 0; i < lim; ++i) {
if (i < rev[i]) swap(a[i], a[rev[i]]);
}
for (int len = 2; len <= lim; len <<= 1) {
int mid = len >> 1;
LL Wn = Qpow(G, (mod - 1) / len);
if (type == -1) Wn = Inv(Wn);
for (int i = 0; i < lim; i += len) {
LL W = 1;
for (int j = 0; j < mid; ++j) {
LL x = a[i + j], y = a[i + j + mid] * W % mod;
a[i + j] = (x + y >= mod) ? (x + y - mod) : (x + y);
a[i + j + mid] = (x < y) ? (x + mod - y) : (x - y);
W = W * Wn % mod;
}
}
}
if (type == -1) {
LL tmp = Inv(lim);
for (int i = 0; i < lim; ++i) {
a[i] = a[i] * tmp % mod;
}
}
}
void Solve() {
int lim = 1, l = 0;
while (lim < n + n + 2) lim <<= 1, ++l;
for (int i = 1; i < lim; ++i) {
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << l - 1);
}
NTT(A, lim, 1); NTT(B, lim, 1);
for (int i = 0; i < lim; ++i)
A[i] = A[i] * B[i] % mod;
NTT(A, lim, -1);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; ++i) {
int x, y;
scanf("%d%d", &x, &y);
Add_Edge(x, y);
Add_Edge(y, x);
}
init::main();
convolution::Solve();
for (int i = 1; i <= n; ++i) {
LL tmp = C(n, i) * n % mod;
tmp = tmp - fav[i] * A[i + n] % mod;
if (tmp < 0) tmp += mod;
printf("%lld\n", tmp);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Many Easy Problems |
User |
Vexoben |
Language |
C++14 (GCC 5.4.1) |
Score |
1900 |
Code Size |
2669 Byte |
Status |
AC |
Exec Time |
255 ms |
Memory |
61312 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:111:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:114: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 |
231 ms |
53376 KB |
doublestar1 |
AC |
230 ms |
53376 KB |
doublestar2 |
AC |
231 ms |
53376 KB |
doublestar3 |
AC |
230 ms |
53376 KB |
doublestar4 |
AC |
230 ms |
53376 KB |
example0 |
AC |
25 ms |
39168 KB |
example1 |
AC |
24 ms |
39168 KB |
example2 |
AC |
24 ms |
39168 KB |
line0 |
AC |
255 ms |
61312 KB |
line1 |
AC |
255 ms |
61312 KB |
line2 |
AC |
255 ms |
61312 KB |
line3 |
AC |
255 ms |
61312 KB |
line4 |
AC |
254 ms |
61312 KB |
maxrand0 |
AC |
247 ms |
53376 KB |
maxrand1 |
AC |
247 ms |
53376 KB |
maxrand10 |
AC |
247 ms |
53376 KB |
maxrand11 |
AC |
247 ms |
53376 KB |
maxrand12 |
AC |
248 ms |
53376 KB |
maxrand13 |
AC |
248 ms |
53376 KB |
maxrand14 |
AC |
249 ms |
53376 KB |
maxrand15 |
AC |
248 ms |
53376 KB |
maxrand16 |
AC |
248 ms |
53376 KB |
maxrand17 |
AC |
247 ms |
53376 KB |
maxrand18 |
AC |
247 ms |
53376 KB |
maxrand19 |
AC |
248 ms |
53376 KB |
maxrand2 |
AC |
247 ms |
53376 KB |
maxrand3 |
AC |
247 ms |
53376 KB |
maxrand4 |
AC |
247 ms |
53376 KB |
maxrand5 |
AC |
247 ms |
53376 KB |
maxrand6 |
AC |
250 ms |
53376 KB |
maxrand7 |
AC |
247 ms |
53376 KB |
maxrand8 |
AC |
247 ms |
53376 KB |
maxrand9 |
AC |
248 ms |
53376 KB |
rand0 |
AC |
27 ms |
39168 KB |
rand1 |
AC |
25 ms |
39168 KB |
rand2 |
AC |
26 ms |
39168 KB |
rand3 |
AC |
27 ms |
39168 KB |
rand4 |
AC |
25 ms |
39168 KB |
rand5 |
AC |
27 ms |
39168 KB |
rand6 |
AC |
26 ms |
39168 KB |
rand7 |
AC |
27 ms |
39168 KB |
rand8 |
AC |
25 ms |
39168 KB |
rand9 |
AC |
25 ms |
39168 KB |
star0 |
AC |
228 ms |
53376 KB |
star1 |
AC |
228 ms |
53376 KB |
star2 |
AC |
236 ms |
53376 KB |
star3 |
AC |
229 ms |
53376 KB |
star4 |
AC |
228 ms |
53376 KB |