Submission #1593845
Source Code Expand
#include <bits/stdc++.h> typedef long long ll; typedef long long llong; typedef long double ld; typedef unsigned long long ull; using namespace std; const ll MOD = 924844033; ll pw(ll a, ll b) { ll ans = 1; while (b) { while (!(b & 1)) b >>= 1, a = (a * a) % MOD; ans = (ans * a) % MOD, --b; } return ans; } const ll B = 3597; const int MAXN = 220000; int was[MAXN]; int c[MAXN]; ll a[1 << 19]; ll b[1 << 19]; ll fc[MAXN]; ll bfc[MAXN]; vector<int> eds[MAXN]; int sz[MAXN]; int n; void dfs1(int v) { sz[v] = 1; was[v] = 1; for (int u: eds[v]) { if (was[u]) continue; dfs1(u); sz[v] += sz[u]; ++c[sz[u]]; } if (sz[v] != n) ++c[n - sz[v]]; } int rev(int x, int k) { int ans = 0; for (int i = 0; i < k; ++i) { ans = ans * 2 + (x & 1); x >>= 1; } return ans; } void fft(ll *a, int k, int inv) { int n = (1 << k); for (int i = 0; i < n; ++i) { int x = rev(i, k); if (x > i) swap(a[x], a[i]); } for (int bl = 1; bl < n; bl *= 2) { ll wadd = pw(B, (1 << 20) / bl); if (inv) wadd = pw(wadd, MOD - 2); for (int i = 0; i < n; i += 2 * bl) { ll w = 1; for (int j = i; j < i + bl; ++j, w = (w * wadd) % MOD) { ll u = a[j]; ll v = a[j + bl] * w % MOD; a[j] = (u + v) % MOD; a[j + bl] = (u - v + MOD) % MOD; } } } if (inv) { ll n2 = pw(n, MOD - 2); for (int j = 0; j < n; ++j) a[j] = (a[j] * n2) % MOD; } } int main() { scanf("%d", &n); fc[0] = bfc[0] = 1; for (int i = 1; i <= n; ++i) fc[i] = (fc[i - 1] * i) % MOD, bfc[i] = pw(fc[i], MOD - 2); for (int i = 0; i < n - 1; ++i) { int a, b; scanf("%d%d", &a, &b); --a, --b; eds[a].push_back(b); eds[b].push_back(a); } dfs1(0); for (int i = 0; i <= n; ++i) a[i] = (c[i] * fc[i]) % MOD; for (int i = 0; i <= n; ++i) b[i] = bfc[n - i]; int k = 0; while ((1 << k) <= 2 * n) ++k; fft(a, k, 0); fft(b, k, 0); for (int i = 0; i < (1 << k); ++i) a[i] = (a[i] * b[i]) % MOD; fft(a, k, 1); for (int i = 1; i <= n; ++i) { a[i] = a[i + n] * bfc[i] % MOD; ll go = fc[n] * bfc[i] % MOD * bfc[n - i] % MOD * n % MOD; go = (go - a[i] + MOD) % MOD; printf("%lld\n", go); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Many Easy Problems |
User | LHiC |
Language | C++14 (GCC 5.4.1) |
Score | 1900 |
Code Size | 2262 Byte |
Status | AC |
Exec Time | 284 ms |
Memory | 35456 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:82:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &n); ^ ./Main.cpp:88:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &a, &b); ^
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 | 254 ms | 27896 KB |
doublestar1 | AC | 255 ms | 27896 KB |
doublestar2 | AC | 254 ms | 27896 KB |
doublestar3 | AC | 254 ms | 27896 KB |
doublestar4 | AC | 254 ms | 27896 KB |
example0 | AC | 4 ms | 13696 KB |
example1 | AC | 4 ms | 13696 KB |
example2 | AC | 4 ms | 13696 KB |
line0 | AC | 266 ms | 35456 KB |
line1 | AC | 265 ms | 35456 KB |
line2 | AC | 265 ms | 35456 KB |
line3 | AC | 265 ms | 35456 KB |
line4 | AC | 265 ms | 35456 KB |
maxrand0 | AC | 279 ms | 27776 KB |
maxrand1 | AC | 276 ms | 27776 KB |
maxrand10 | AC | 275 ms | 27776 KB |
maxrand11 | AC | 275 ms | 27776 KB |
maxrand12 | AC | 284 ms | 27776 KB |
maxrand13 | AC | 276 ms | 27776 KB |
maxrand14 | AC | 277 ms | 27776 KB |
maxrand15 | AC | 280 ms | 27776 KB |
maxrand16 | AC | 280 ms | 27776 KB |
maxrand17 | AC | 276 ms | 27776 KB |
maxrand18 | AC | 276 ms | 27776 KB |
maxrand19 | AC | 275 ms | 27776 KB |
maxrand2 | AC | 277 ms | 27776 KB |
maxrand3 | AC | 278 ms | 27776 KB |
maxrand4 | AC | 276 ms | 27776 KB |
maxrand5 | AC | 278 ms | 27776 KB |
maxrand6 | AC | 278 ms | 27776 KB |
maxrand7 | AC | 275 ms | 27776 KB |
maxrand8 | AC | 276 ms | 27776 KB |
maxrand9 | AC | 278 ms | 27776 KB |
rand0 | AC | 8 ms | 13824 KB |
rand1 | AC | 4 ms | 13696 KB |
rand2 | AC | 6 ms | 13824 KB |
rand3 | AC | 8 ms | 13824 KB |
rand4 | AC | 5 ms | 13696 KB |
rand5 | AC | 8 ms | 13824 KB |
rand6 | AC | 6 ms | 13824 KB |
rand7 | AC | 7 ms | 13824 KB |
rand8 | AC | 4 ms | 13696 KB |
rand9 | AC | 5 ms | 13824 KB |
star0 | AC | 246 ms | 28276 KB |
star1 | AC | 248 ms | 28276 KB |
star2 | AC | 249 ms | 28276 KB |
star3 | AC | 248 ms | 28276 KB |
star4 | AC | 249 ms | 28276 KB |