Submission #1807609
Source Code Expand
#include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int MAXN = 524290; const int MOD = 924844033; int a[MAXN], b[MAXN]; int n, m, i, j, k, x, y; int size[MAXN]; int first[MAXN], next[MAXN], go[MAXN], t, pre[MAXN]; int bit[MAXN], f[MAXN]; inline int get() { char c; while ((c = getchar()) < 48 || c > 57); int res = c - 48; while ((c = getchar()) >= 48 && c <= 57) res = res * 10 + c - 48; return res; } inline void add(int x, int y) { next[++t] = first[x]; first[x] = t; go[t] = y; } inline void dfs(int now, int las) { size[now] = 1; for(int i = first[now]; i; i = next[i]) if (go[i] != las) dfs(go[i], now), size[now] += size[go[i]]; a[n - size[now]] --; a[n] ++; for(int i = first[now]; i; i = next[i]) if (go[i] != las) a[size[go[i]]] --; } inline int ksm(int x, int y, int z) { int b = 1; while (y) { if (y & 1) b = 1ll * b * x % z; x = 1ll * x * x % z; y >>= 1; } return b; } inline int ntt_init(int m) { int n = 1, nn = 0; while (n <= m) n <<= 1, nn ++; int g = ksm(5, (MOD - 1) / n, MOD); f[0] = 1; for(int i = 1; i < n; i ++) f[i] = 1ll * f[i - 1] * g % MOD, bit[i] = (bit[i >> 1] >> 1) | ((i & 1) << nn - 1); return nn; } inline void ntt(int *a, int nn, int ty) { int n = 1 << nn; for(int i = 0; i < n; i ++) if (i < bit[i]) swap(a[i], a[bit[i]]); for(int k = 1; k <= nn; k ++) { int len = 1 << k, wn = (ty == 1) ? f[n / len] : f[n - n / len]; for(int j = 0; j < n; j += len) { int m = len >> 1, w = 1; for(int i = j; i < j + m; i ++) { int l = a[i], t = 1ll * a[i + m] * w % MOD; a[i] = (l + t) % MOD; a[i + m] = (l - t + MOD) % MOD; w = 1ll * w * wn % MOD; } } } } int main() { cin >> n; for(i = 1; i < n; i ++) { x = get(); y = get(); add(x, y); add(y, x); } int nn = ntt_init(n << 1), N = 1 << nn; dfs(1, 0); for(i = 1; i <= n; i ++) if (a[i] < 0) a[i] += MOD; pre[0] = 1; for(i = 1; i < N; i ++) pre[i] = 1ll * pre[i - 1] * i % MOD, a[i] = 1ll * a[i] * pre[i] % MOD; for(i = 0; i <= n; i ++) b[i] = ksm(pre[n - i], MOD - 2, MOD); ntt(a, nn, 1); ntt(b, nn, 1); for(i = 0; i < N; i ++) a[i] = 1ll * a[i] * b[i] % MOD; ntt(a, nn, -1); int po = ksm(N, MOD - 2, MOD); for(i = 0; i < N; i ++) a[i] = 1ll * a[i] * po % MOD; for(i = n + 1; i <= n + n; i ++) printf("%d\n", 1ll * a[i] * ksm(pre[i - n], MOD - 2, MOD) % MOD); }
Submission Info
Submission Time | |
---|---|
Task | F - Many Easy Problems |
User | diaosipan |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2535 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘void add(int, int)’: ./Main.cpp:26:2: error: reference to ‘next’ is ambiguous next[++t] = first[x]; first[x] = t; go[t] = y; ^ ./Main.cpp:13:18: note: candidates are: int next [524290] int first[MAXN], next[MAXN], go[MAXN], t, pre[MAXN]; ^ In file included from /usr/include/c++/5/bits/stl_algobase.h:66:0, from /usr/include/c++/5/vector:60, from ./Main.cpp:2: /usr/include/c++/5/bits/stl_iterator_base_funcs.h:184:5: note: template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type) next(_ForwardIterator __x, typename ^ ./Main.cpp: In function ‘void dfs(int, int)’: ./Main.cpp:31:33: error: reference to ‘next’ is ambiguous for(int i = first[now]; i; i = next[i]) ^ ./Main.cpp:13:18: note: candidates are: int next [524290] int first[MAXN], next[MAXN], go[MAXN], t, pre[MAXN]; ^ In f...