Submission #906824
Source Code Expand
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define sz(s) ((int) ((s).size()))
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#ifdef _WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
typedef long long ll;
typedef long double ld;
const int inf = (int) 1e9 + 100;
const ld eps = 1e-11;
const ld PI = acos(-1.0L);
namespace FFT {
struct comp {
ld x, y;
comp(ld x = 0, ld y = 0) : x(x), y(y) {}
comp operator+(const comp & b) const {
return comp(x + b.x, y + b.y);
}
comp operator-(const comp & b) const {
return comp(x - b.x, y - b.y);
}
comp operator*(const comp & b) const {
return comp(x * b.x - y * b.y, x * b.y + y * b.x);
}
};
const int maxn = 1 << 20;
int n, logn, rev[maxn];
comp a[maxn], b[maxn];
void init() {
rev[0] = 0;
for (int i = 1, j = -1; i < n; i++) {
if (!(i & (i - 1))) {
j++;
}
rev[i] = rev[i ^ (1 << j)] ^ (1 << (logn - 1 - j));
}
}
void fft(comp * a, bool back = false) {
for (int i = 0; i < n; i++) {
if (rev[i] < i) {
swap(a[rev[i]], a[i]);
}
}
for (int j0 = 1; j0 < n; j0 <<= 1) {
comp mult = comp(cos(PI / j0), sin(PI / j0));
if (back) {
mult.y = -mult.y;
}
for (int i = 0; i < n; i += j0) {
comp cur = comp(1);
for (int it = 0, j = i + j0; it < j0; i++, j++, it++) {
comp add = a[j] * cur;
a[j] = a[i] - add;
a[i] = a[i] + add;
cur = cur * mult;
}
}
}
}
int mult(int n1, int * a1, int n2, int * a2, ll * ans) {
for (n = 1, logn = 0; n < n1 + n2 - 1; n <<= 1, logn++) ;
init();
for (int i = 0; i < n; i++) {
a[i] = (i < n1) ? a1[i] : 0;
b[i] = (i < n2) ? a2[i] : 0;
}
fft(a);
fft(b);
for (int i = 0; i < n; i++) {
a[i] = a[i] * b[i];
}
fft(a, true);
int anslen = 0;
for (int i = 0; i < n; i++) {
ll cur = (ll) floor(a[i].x / n + 0.5);
if (cur) {
while (anslen < i) {
ans[anslen++] = 0;
}
ans[anslen++] = cur;
}
}
return anslen;
}
}
mt19937 mrand(random_device{} ());
int rnd(int x) {
return mrand() % x;
}
const int mod = 924844033;
void add(int & a, int b) {
if ((a += b) >= mod) {
a -= mod;
}
}
int mult(int a, int b) {
return (ll) a * b % mod;
}
int power(int a, int p) {
int res = 1;
while (p) {
if (p & 1) {
res = mult(res, a);
}
a = mult(a, a);
p >>= 1;
}
return res;
}
int inv(int a) {
return power(a, mod - 2);
}
int n;
const int maxn = 2e5 + 100;
int fact[maxn];
void precalc() {
fact[0] = 1;
for (int i = 1; i < maxn; i++) {
fact[i] = mult(fact[i - 1], i);
}
}
vector<vector<int> > tree;
int cnt[maxn];
bool read() {
if (scanf("%d", &n) < 1) {
return false;
}
tree = vector<vector<int> > (n);
for (int i = 0; i < n - 1; i++) {
int a, b;
scanf("%d%d", &a, &b);
a--, b--;
tree[a].pb(b);
tree[b].pb(a);
}
return true;
}
int a[maxn];
void dfs(int v, int par = -1) {
a[n]++;
cnt[v] = 1;
for (int i = 0; i < sz(tree[v]); i++) {
int to = tree[v][i];
if (to == par) {
continue;
}
dfs(to, v);
cnt[v] += cnt[to];
a[cnt[to]]--;
}
a[n - cnt[v]]--;
}
int f1[maxn], f2[maxn], ans[maxn * 2];
int tmpa[maxn], tmpb[maxn];
ll tmpans[maxn * 2];
const int BASE = 1000;
int getmy(int i, int val) {
for (int j = 0; j < i; j++) {
val /= BASE;
}
return val % BASE;
}
void mymult() {
int m = n + 1;
memset(ans, 0, sizeof(ans));
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < m; k++) {
tmpa[k] = getmy(i, f1[k]);
tmpb[k] = getmy(j, f2[k]);
}
int res = FFT::mult(m, tmpa, m, tmpb, tmpans);
int tomult = power(BASE, i + j);
for (int r = 0; r < res; r++) {
add(ans[r], mult(tomult, tmpans[r] % mod));
}
}
}
}
void solve() {
memset(a, 0, sizeof(a));
memset(f1, 0, sizeof(f1));
memset(f2, 0, sizeof(f2));
dfs(0);
for (int i = 0; i <= n; i++) {
f1[i] = mult(fact[i], (a[i] + mod) % mod);
f2[i] = inv(fact[n - i]);
}
mymult();
for (int i = 1; i <= n; i++) {
printf("%d\n", mult(ans[i + n], inv(fact[i])));
}
}
int main() {
precalc();
#ifdef DEBUG
assert(freopen("text.in", "r", stdin));
assert(freopen("text.out", "w", stdout));
#endif
while (true) {
if (!read()) {
break;
}
solve();
#ifdef DEBUG
eprintf("Time: %.18f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
}
return 0;
}
Submission Info
Submission Time
2016-10-01 22:31:43+0900
Task
F - Many Easy Problems
User
StanislavErshov
Language
C++14 (GCC 5.4.1)
Score
1900
Code Size
4968 Byte
Status
AC
Exec Time
2267 ms
Memory
101504 KB
Compile Error
./Main.cpp: In function ‘bool read()’:
./Main.cpp:167:26: 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
2232 ms
91384 KB
doublestar1
AC
2179 ms
91128 KB
doublestar2
AC
2194 ms
91256 KB
doublestar3
AC
2177 ms
91128 KB
doublestar4
AC
2168 ms
91256 KB
example0
AC
81 ms
70528 KB
example1
AC
81 ms
70528 KB
example2
AC
82 ms
70528 KB
line0
AC
2184 ms
101376 KB
line1
AC
2198 ms
101376 KB
line2
AC
2200 ms
101504 KB
line3
AC
2267 ms
101376 KB
line4
AC
2183 ms
101376 KB
maxrand0
AC
2169 ms
91136 KB
maxrand1
AC
2173 ms
91136 KB
maxrand10
AC
2204 ms
91136 KB
maxrand11
AC
2189 ms
91136 KB
maxrand12
AC
2186 ms
91136 KB
maxrand13
AC
2186 ms
91136 KB
maxrand14
AC
2237 ms
91136 KB
maxrand15
AC
2168 ms
91136 KB
maxrand16
AC
2181 ms
91136 KB
maxrand17
AC
2200 ms
91136 KB
maxrand18
AC
2173 ms
91136 KB
maxrand19
AC
2188 ms
91136 KB
maxrand2
AC
2204 ms
91136 KB
maxrand3
AC
2167 ms
91136 KB
maxrand4
AC
2162 ms
91136 KB
maxrand5
AC
2177 ms
91136 KB
maxrand6
AC
2218 ms
91136 KB
maxrand7
AC
2186 ms
91136 KB
maxrand8
AC
2173 ms
91136 KB
maxrand9
AC
2175 ms
91136 KB
rand0
AC
105 ms
70784 KB
rand1
AC
83 ms
70528 KB
rand2
AC
93 ms
70656 KB
rand3
AC
105 ms
70784 KB
rand4
AC
86 ms
70528 KB
rand5
AC
104 ms
70784 KB
rand6
AC
93 ms
70656 KB
rand7
AC
104 ms
70784 KB
rand8
AC
84 ms
70528 KB
rand9
AC
92 ms
70656 KB
star0
AC
2151 ms
91636 KB
star1
AC
2144 ms
91636 KB
star2
AC
2150 ms
91636 KB
star3
AC
2165 ms
91764 KB
star4
AC
2139 ms
91636 KB