Submission #2212471
Source Code Expand
#include <bits/stdc++.h> using std::pair; using std::vector; using std::string; typedef long long ll; typedef pair<int, int> pii; #define fst first #define snd second #define pb(a) push_back(a) #define mp(a, b) std::make_pair(a, b) #define debug(...) fprintf(stderr, __VA_ARGS__) template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; } template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; } const int oo = 0x3f3f3f3f; string procStatus() { std::ifstream t("/proc/self/status"); return string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>()); } template <typename T> T read(T& x) { int f = 1; x = 0; char ch = getchar(); for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1; for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48; return x *= f; } const int g = 5; const int N = 1 << 20; const int mo = 924844033; int fpm(int x, int y) { int res = 1; for(; y > 0; y >>= 1) { if(y & 1) res = (ll) res * x % mo; x = (ll) x * x % mo; } return res; } namespace Poly { int n; void init(int _n) { n = _n; while(n > (n & -n)) n += (n & -n); } void dft(int *x, int ty) { for(int i = 0, j = 0; i < n; ++i) { if(i < j) std::swap(x[i], x[j]); for(int l = n >> 1; (j ^= l) < l; l >>= 1); } for(int l = 1; l < n; l <<= 1) { int wn = fpm(g, (mo - 1) / l / 2); if(ty == -1) wn = fpm(wn, mo - 2); for(int i = 0; i < n; i += l << 1) { int w = 1; for(int j = 0; j < l; ++j) { int u = x[i + j]; int v = (ll) x[i + j + l] * w % mo; x[i + j] = (u + v) % mo; x[i + j + l] = (u - v + mo) % mo; w = (ll) w * wn % mo; } } } if(ty == -1) { int inv = fpm(n, mo - 2); for(int i = 0; i < n; ++i) { x[i] = (ll) x[i] * inv % mo; } } } } int n, k; vector<int> G[N + 5]; int x[N + 5], y[N + 5], sz[N + 5]; void dfs(int u, int f = 0) { ++ x[n]; sz[u] = 1; for(const auto& v : G[u]) if(v ^ f) { dfs(v, u); sz[u] += sz[v]; -- x[sz[v]], -- x[n - sz[v]]; } } int main() { #ifdef Wearry freopen("in", "r", stdin); freopen("out", "w", stdout); #endif read(n); for(int i = 1; i < n; ++i) { static int u, v; read(u), read(v); G[u].pb(v), G[v].pb(u); } dfs(1); int fac = 1; for(int i = 1; i <= n; ++i) { fac = (ll) fac * i % mo; x[i] = (ll) x[i] * fac % mo; } fac = 1; for(int i = n; i >= 0; --i) { y[i] = fpm(fac, mo - 2); fac = (ll) fac * (n - i + 1) % mo; } Poly::init(2*n+1); Poly::dft(x, 1), Poly::dft(y, 1); for(int i = 0; i < Poly::n; ++i) x[i] = (ll) x[i] * y[i] % mo; Poly::dft(x, -1); fac = 1; for(int i = n+1; i <= 2*n; ++i) { fac = (ll) fac * (i - n) % mo; printf("%lld\n", (ll) x[i] * fpm(fac, mo - 2) % mo); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Many Easy Problems |
User | Wearry |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 3348 Byte |
Status | WA |
Exec Time | 296 ms |
Memory | 49920 KB |
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 | AC | 256 ms | 38260 KB |
doublestar1 | AC | 263 ms | 42360 KB |
doublestar2 | AC | 255 ms | 42360 KB |
doublestar3 | AC | 252 ms | 42360 KB |
doublestar4 | AC | 253 ms | 42360 KB |
example0 | AC | 10 ms | 28928 KB |
example1 | AC | 9 ms | 28928 KB |
example2 | AC | 10 ms | 28928 KB |
line0 | WA | 268 ms | 49920 KB |
line1 | AC | 269 ms | 49920 KB |
line2 | WA | 270 ms | 49920 KB |
line3 | AC | 269 ms | 49920 KB |
line4 | AC | 269 ms | 49920 KB |
maxrand0 | AC | 296 ms | 42240 KB |
maxrand1 | AC | 291 ms | 42240 KB |
maxrand10 | WA | 286 ms | 42240 KB |
maxrand11 | AC | 285 ms | 42240 KB |
maxrand12 | AC | 287 ms | 42240 KB |
maxrand13 | AC | 287 ms | 42240 KB |
maxrand14 | AC | 287 ms | 42240 KB |
maxrand15 | WA | 294 ms | 42240 KB |
maxrand16 | AC | 284 ms | 42240 KB |
maxrand17 | WA | 285 ms | 42240 KB |
maxrand18 | AC | 288 ms | 42240 KB |
maxrand19 | WA | 285 ms | 42240 KB |
maxrand2 | AC | 289 ms | 42240 KB |
maxrand3 | WA | 285 ms | 42240 KB |
maxrand4 | AC | 292 ms | 42240 KB |
maxrand5 | WA | 289 ms | 42240 KB |
maxrand6 | WA | 287 ms | 42240 KB |
maxrand7 | AC | 286 ms | 42240 KB |
maxrand8 | WA | 285 ms | 42240 KB |
maxrand9 | WA | 289 ms | 42240 KB |
rand0 | AC | 13 ms | 29056 KB |
rand1 | AC | 10 ms | 28928 KB |
rand2 | AC | 12 ms | 29056 KB |
rand3 | AC | 13 ms | 29056 KB |
rand4 | AC | 11 ms | 28928 KB |
rand5 | AC | 13 ms | 29056 KB |
rand6 | WA | 12 ms | 29056 KB |
rand7 | AC | 13 ms | 29056 KB |
rand8 | AC | 10 ms | 28928 KB |
rand9 | AC | 11 ms | 28928 KB |
star0 | AC | 246 ms | 42740 KB |
star1 | AC | 246 ms | 42740 KB |
star2 | AC | 246 ms | 42740 KB |
star3 | AC | 246 ms | 42740 KB |
star4 | AC | 245 ms | 42740 KB |