Submission #907676
Source Code Expand
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{} ());
int rnd(int x) {
return mrand() % x;
}
typedef double ld;
typedef long long ll;
#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif
#define pb push_back
#define mp make_pair
#define sz(x) ((int) (x).size())
#define TASK "text"
const int inf = (int) 1.01e9;
const ld eps = 1e-9;
const ld pi = acos((ld) -1.0);
const int mod = 924844033;
void add(int &x, int y) {
if ((x += y) >= mod) {
x -= mod;
}
}
int mult(int x, int y) {
return (long long) x * y % mod;
}
int myPower(int x, int pw) {
int res = 1;
for (; pw; pw >>= 1) {
if (pw & 1) {
res = mult(res, x);
}
x = mult(x, x);
}
return res;
}
const int maxn = (int) 2e5 + 10;
int inv[maxn];
void precalc() {
for (int i = 1; i < maxn; ++i) {
inv[i] = myPower(i, mod - 2);
}
}
//BEGIN ALGO
namespace FFT {
struct com {
ld x, y;
com(ld _x = 0, ld _y = 0) : x(_x), y(_y) {}
inline com operator + (const com &c) const {
return com(x + c.x, y + c.y);
}
inline com operator - (const com &c) const {
return com(x - c.x, y - c.y);
}
inline com operator * (const com &c) const {
return com(x * c.x - y * c.y, x * c.y + y * c.x);
}
inline com conj() const {
return com(x, -y);
}
};
const static int maxk = 20, maxn = (1 << maxk) + 1;
int dp[maxn];
com rs[maxn];
int n, k;
int lastk = -1;
void fft(com *a, bool torev = 0) {
if (lastk != k) {
lastk = k;
dp[0] = 0;
for (int i = 1, g = -1; i < n; ++i) {
if (!(i & (i - 1))) {
++g;
}
dp[i] = dp[i ^ (1 << g)] ^ (1 << (k - 1 - g));
}
}
for (int i = 0; i < n; ++i) {
if (i < dp[i]) {
swap(a[i], a[dp[i]]);
}
}
for (int len = 1; len < n; len <<= 1) {
ld alf = pi / len;
com w(cos(alf), sin(alf));
if (torev) {
w.y = -w.y;
}
for (int i = 0; i < n; i += len) {
com cw(1, 0);
for (int it = 0, j = i + len; it < len; ++it, ++i, ++j) {
com tmp = a[j] * cw;
a[j] = a[i] - tmp;
a[i] = a[i] + tmp;
cw = cw * w;
}
}
}
}
com a[maxn];
int mult(int na, int *_a, int nb, int *_b, long long *ans) {
if (!na || !nb) {
return 0;
}
for (k = 0, n = 1; n < na + nb - 1; n <<= 1, ++k) ;
assert(n < maxn);
for (int i = 0; i < n; ++i) {
a[i] = com(i < na ? _a[i] : 0, i < nb ? _b[i] : 0);
}
fft(a);
a[n] = a[0];
for (int i = 0; i <= n - i; ++i) {
a[i] = (a[i] * a[i] - (a[n - i] * a[n - i]).conj()) * com(0, (ld) -1 / n / 4);
a[n - i] = a[i].conj();
}
fft(a, 1);
int res = 0;
for (int i = 0; i < n; ++i) {
long long val = (long long) round(a[i].x);
assert(abs(val - a[i].x) < 1e-1);
if (val) {
assert(i < na + nb - 1);
while (res < i) {
ans[res++] = 0;
}
ans[res++] = val;
}
}
return res;
}
};
//END ALGO
int ta[maxn], tb[maxn];
long long tans[maxn];
void mult(int n1, int *a1, int n2, int *a2, int *ans) {
for (int i = 0; i < n1 + n2 - 1; ++i) {
ans[i] = 0;
}
const int Base = (int) 1e3;
for (int it1 = 0, cur1 = 1; it1 < 3; ++it1, cur1 *= Base) {
for (int it2 = 0, cur2 = cur1; it2 < 3; ++it2, cur2 = mult(cur2, Base)) {
for (int i = 0; i < n1; ++i) {
ta[i] = a1[i];
for (int j = 0; j < it1; ++j) {
ta[i] /= Base;
}
ta[i] %= Base;
}
for (int i = 0; i < n2; ++i) {
tb[i] = a2[i];
for (int j = 0; j < it2; ++j) {
tb[i] /= Base;
}
tb[i] %= Base;
}
int res = FFT::mult(n1, ta, n2, tb, tans);
for (int i = 0; i < res; ++i) {
ans[i] = (tans[i] % mod * cur2 + ans[i]) % mod;
}
}
}
assert(n1 > 0 && n2 > 0);
#ifdef DEBUG
/*for (int i = 0; i < n1; ++i) {
eprintf("%d%c", a1[i], " \n"[i == n1 - 1]);
}
for (int i = 0; i < n2; ++i) {
eprintf("%d%c", a2[i], " \n"[i == n2 - 1]);
}*/
for (int i = 0; i < n1 + n2 - 1; ++i) {
int res = 0;
for (int j = 0; j < n1 && j <= i; ++j) {
int k = i - j;
if (k >= n2) {
continue;
}
add(res, mult(a1[j], a2[k]));
}
//eprintf("ans[%d] = %d\n", i, ans[i]);
//eprintf("res = %d\n", res);
//ans[i] = res;
assert(ans[i] == res);
}
/*
for (int i = 0; i < n1 + n2 - 1; ++i) {
eprintf("%d%c", ans[i], " \n"[i == n2 - 1]);
}*/
#endif
}
vector<vector<int> > es;
int n;
int read() {
if (scanf("%d", &n) < 1) {
return 0;
}
es = vector<vector<int> >(n);
for (int i = 0; i < n - 1; ++i) {
int s, t;
scanf("%d%d", &s, &t);
--s, --t;
es[s].pb(t), es[t].pb(s);
}
return 1;
}
int a[maxn];
int dfs(int v, int pr) {
int res = 1;
for (int u : es[v]) {
if (u == pr) {
continue;
}
int got = dfs(u, v);
add(a[got], mod - 1);
res += got;
}
if (pr != -1) {
add(a[n - res], mod - 1);
}
return res;
}
int ans[maxn];
int coefs[maxn];
int tmp[maxn];
void solve(int l, int r) {
if (l + 1 == r) {
ans[l] = a[l];
return;
}
int m = (l + r) / 2;
solve(l, m);
solve(m, r);
{
int t = m - l;
int curc = 1;
coefs[0] = 1;
for (int i = 1; i <= t; ++i) {
coefs[i] = mult(coefs[i - 1], mult(t - i + 1, inv[i]));
}
}
mult(r - m, ans + m, m - l + 1, coefs, tmp);
for (int i = l; i < m; ++i) {
add(tmp[i - l], ans[i]);
}
/*for (int i = l; i < r; ++i) {
eprintf("%d%c", ans[i], " \n"[i == r - 1]);
}
eprintf("solve [%d..%d):\n", l, r);*/
for (int i = l; i < r; ++i) {
ans[i] = tmp[i - l];
//eprintf("%d%c", ans[i], " \n"[i == r - 1]);
}
}
void solve() {
for (int i = 0; i <= n; ++i) {
a[i] = 0;
}
a[n] = n;
dfs(0, -1);
/*for (int i = 0; i <= n; ++i) {
eprintf("%d%c", a[i], " \n"[i == n]);
}*/
solve(0, n + 1);
for (int i = 1; i <= n; ++i) {
printf("%d\n", ans[i]);
}
}
int main() {
precalc();
#ifdef LOCAL
freopen(TASK ".out", "w", stdout);
assert(freopen(TASK ".in", "r", stdin));
#endif
while (1) {
if (!read()) {
break;
}
solve();
#ifdef DEBUG
eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
}
return 0;
}
Submission Info
Submission Time
2016-10-02 03:11:34+0900
Task
F - Many Easy Problems
User
XraY
Language
C++14 (GCC 5.4.1)
Score
1900
Code Size
6776 Byte
Status
AC
Exec Time
4176 ms
Memory
60672 KB
Compile Error
./Main.cpp: In function ‘int read()’:
./Main.cpp:231:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &s, &t);
^
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
4017 ms
53240 KB
doublestar1
AC
4033 ms
53112 KB
doublestar2
AC
4029 ms
53112 KB
doublestar3
AC
4023 ms
53112 KB
doublestar4
AC
4026 ms
53112 KB
example0
AC
67 ms
33792 KB
example1
AC
67 ms
33792 KB
example2
AC
67 ms
33920 KB
line0
AC
4176 ms
60672 KB
line1
AC
4122 ms
60672 KB
line2
AC
4153 ms
60672 KB
line3
AC
4143 ms
60672 KB
line4
AC
4114 ms
60672 KB
maxrand0
AC
4043 ms
52992 KB
maxrand1
AC
4064 ms
52992 KB
maxrand10
AC
4061 ms
52992 KB
maxrand11
AC
4037 ms
52992 KB
maxrand12
AC
4072 ms
52992 KB
maxrand13
AC
4082 ms
52992 KB
maxrand14
AC
4048 ms
52992 KB
maxrand15
AC
4062 ms
52992 KB
maxrand16
AC
4049 ms
52992 KB
maxrand17
AC
4055 ms
52992 KB
maxrand18
AC
4056 ms
52992 KB
maxrand19
AC
4042 ms
52992 KB
maxrand2
AC
4040 ms
52992 KB
maxrand3
AC
4040 ms
52992 KB
maxrand4
AC
4061 ms
52992 KB
maxrand5
AC
4047 ms
52992 KB
maxrand6
AC
4055 ms
52992 KB
maxrand7
AC
4045 ms
52992 KB
maxrand8
AC
4062 ms
52992 KB
maxrand9
AC
4051 ms
52992 KB
rand0
AC
103 ms
34048 KB
rand1
AC
68 ms
33792 KB
rand2
AC
86 ms
34048 KB
rand3
AC
104 ms
34048 KB
rand4
AC
76 ms
33920 KB
rand5
AC
102 ms
34048 KB
rand6
AC
86 ms
34048 KB
rand7
AC
103 ms
34048 KB
rand8
AC
71 ms
33920 KB
rand9
AC
81 ms
33920 KB
star0
AC
4005 ms
53492 KB
star1
AC
3994 ms
53492 KB
star2
AC
4031 ms
53492 KB
star3
AC
3992 ms
53492 KB
star4
AC
4003 ms
53492 KB