Submission #2241986
Source Code Expand
//~ #pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge {c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
typedef long long ll;
const int mod = 924844033;
int add(int a, int b) { a += b; if(a >= mod) a -= mod; return a; }
void add_self(int & a, int b) { a = add(a, b); }
int mul(int a, int b) { return (ll) a * b % mod; }
void mul_self(int & a, int b) { a = mul(a, b); }
int my_pow(int a, int b) {
int r = 1;
while(b) {
if(b % 2) mul_self(r, a);
mul_self(a, a);
b /= 2;
}
return r;
}
int my_inv(int a) { return my_pow(a, mod - 2); }
#define div div_ok
int div(int a, int b) { return mul(a, my_inv(b)); }
int sub(int a, int b) { a -= b; if(a < 0) a += mod; return a; }
#define REP(i,n) for(int i = 0; i < int(n); ++i)
int gen;
void dft(vector<int> & a, bool rev) {
const int n = a.size();
for(int i = 1, k = 0; i < n; ++i) {
for(int bit = n / 2; (k ^= bit) < bit; bit /= 2);;;
if(i < k) swap(a[i], a[k]);
}
for(int len = 1, who = 0; len < n; len *= 2, ++who) {
static vector<int> t[2][30];
vector<int> & om = t[rev][who];
if(om.empty()) {
om.resize(len);
om[0] = 1;
int pierw = gen; //my_pow(3, 7 * 17);
for(int rep = 0; rep < 20 - who; ++rep)
pierw = mul(pierw, pierw);
if(rev) pierw = my_inv(pierw);
for(int i = 1; i < len; ++i)
om[i] = mul(om[i-1], pierw);
}
for(int i = 0; i < n; i += 2 * len)
REP(k, len) {
int x = a[i+k];
int y = mul(a[i+k+len], om[k]);
a[i+k] = (x + y) % mod;
a[i+k+len] = (x - y + mod) % mod;
}
}
int tmp = my_inv(n);
if(rev) REP(i, n) a[i] = mul(a[i], tmp);
}
vector<int> multiply( vector<int> a, vector<int> b) {
if(a.empty() || b.empty()) return {};
int n = a.size() + b.size();
/*vector<T> ans(n - 1);
if(min(a.size(),b.size()) < 190) { // BRUTE FORCE
REP(i, a.size()) REP(j, b.size()) ans[i+j] += a[i]*b[j];
return ans; } */
while(n&(n-1)) ++n;
a.resize(n);
b.resize(n);
dft(a, false);
dft(b, false);
for(int i = 0; i < n; ++i) a[i] = mul(a[i], b[i]);
dft(a, true);
return a;
}
#define C C2
//~ #warning small nax
//~ const int nax = 205;
const int nax = 2e5 + 5;
vector<int> w[nax];
int n;
int subtree[nax], cnt[nax], fac[nax], inv_fac[nax];
int C(int a, int b) {
assert(a >= b && b >= 0);
return mul(fac[a], mul(inv_fac[b], inv_fac[a-b]));
}
void dfs(int a, int par) {
subtree[a] = 1;
for(int b : w[a]) if(b != par) {
dfs(b, a);
subtree[a] += subtree[b];
++cnt[subtree[b]];
++cnt[n-subtree[b]];
}
}
void read_uint(int *x){
char c=0;
while(c<'0') c = getchar_unlocked();
*x = c-'0';
c = getchar_unlocked();
while(c>='0') {
*x *= 10;
*x += c-'0';
c = getchar_unlocked();
}
}
void write_uint(int x){
static char buf[13]=" \n";
if(x==0){
fputs_unlocked("0\n", stdout);
return;
}
int i = 10;
while(x) {
buf[i--] = '0' + x % 10;
x /= 10;
}
fputs_unlocked(buf+1+i, stdout);
}
bool okk(int x) {
for(int rep = 0; rep < 20; ++rep)
x = mul(x, x);
if(x == 1) return false;
return mul(x, x) == 1;
}
int main() {
gen = 2;
while(!okk(gen)) ++gen;
fac[0] = 1;
for(int i = 1; i < nax; ++i) fac[i] = mul(fac[i-1], i);
inv_fac[nax-1] = my_inv(fac[nax-1]);
for(int i = nax - 2; i >= 0; --i)
inv_fac[i] = mul(inv_fac[i+1], i+1);
//~ for(int i = 0; i < nax; ++i) inv_fac[i] = my_inv(fac[i]);
//~ scanf("%d", &n);
read_uint(&n);
for(int rep = 0; rep < n - 1; ++rep) {
int a, b;
read_uint(&a); read_uint(&b);
//~ scanf("%d%d", &a, &b);
w[a].push_back(b);
w[b].push_back(a);
}
dfs(1, -1);
for(int i = 1; i <= n; ++i)
mul_self(cnt[i], fac[i]);
vector<int> a(n+1), b(n+1);
for(int i = 0; i <= n; ++i) {
a[i] = cnt[n-i];
b[i] = inv_fac[i];
}
vector<int> c = multiply(a, b);
for(int k = 1; k <= n; ++k) {
int answer = c[n-k];
//~ for(int s = k; s <= n; ++s)
//~ add_self(answer, mul(cnt[s], inv_fac[s-k]));
mul_self(answer, inv_fac[k]);
int whole = mul(n, C(n, k));
write_uint(sub(whole, answer));
}
}
Submission Info
Submission Time |
|
Task |
F - Many Easy Problems |
User |
Errichto |
Language |
C++14 (GCC 5.4.1) |
Score |
1900 |
Code Size |
5037 Byte |
Status |
AC |
Exec Time |
175 ms |
Memory |
34664 KB |
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 |
149 ms |
24416 KB |
doublestar1 |
AC |
149 ms |
24416 KB |
doublestar2 |
AC |
148 ms |
24416 KB |
doublestar3 |
AC |
149 ms |
24416 KB |
doublestar4 |
AC |
149 ms |
24416 KB |
example0 |
AC |
6 ms |
7552 KB |
example1 |
AC |
6 ms |
7552 KB |
example2 |
AC |
6 ms |
7552 KB |
line0 |
AC |
164 ms |
34664 KB |
line1 |
AC |
163 ms |
34664 KB |
line2 |
AC |
162 ms |
34656 KB |
line3 |
AC |
163 ms |
34664 KB |
line4 |
AC |
163 ms |
34664 KB |
maxrand0 |
AC |
172 ms |
24288 KB |
maxrand1 |
AC |
173 ms |
24288 KB |
maxrand10 |
AC |
172 ms |
24288 KB |
maxrand11 |
AC |
173 ms |
24288 KB |
maxrand12 |
AC |
172 ms |
24288 KB |
maxrand13 |
AC |
174 ms |
24288 KB |
maxrand14 |
AC |
175 ms |
24288 KB |
maxrand15 |
AC |
173 ms |
24288 KB |
maxrand16 |
AC |
172 ms |
24288 KB |
maxrand17 |
AC |
174 ms |
24288 KB |
maxrand18 |
AC |
172 ms |
24288 KB |
maxrand19 |
AC |
173 ms |
24288 KB |
maxrand2 |
AC |
173 ms |
24288 KB |
maxrand3 |
AC |
173 ms |
24288 KB |
maxrand4 |
AC |
173 ms |
24288 KB |
maxrand5 |
AC |
174 ms |
24288 KB |
maxrand6 |
AC |
172 ms |
24288 KB |
maxrand7 |
AC |
172 ms |
24288 KB |
maxrand8 |
AC |
173 ms |
24288 KB |
maxrand9 |
AC |
173 ms |
24288 KB |
rand0 |
AC |
8 ms |
7808 KB |
rand1 |
AC |
6 ms |
7552 KB |
rand2 |
AC |
7 ms |
7808 KB |
rand3 |
AC |
8 ms |
7808 KB |
rand4 |
AC |
7 ms |
7680 KB |
rand5 |
AC |
8 ms |
7808 KB |
rand6 |
AC |
7 ms |
7808 KB |
rand7 |
AC |
8 ms |
7808 KB |
rand8 |
AC |
7 ms |
7680 KB |
rand9 |
AC |
7 ms |
7680 KB |
star0 |
AC |
145 ms |
24796 KB |
star1 |
AC |
145 ms |
24796 KB |
star2 |
AC |
145 ms |
24788 KB |
star3 |
AC |
144 ms |
24796 KB |
star4 |
AC |
144 ms |
24796 KB |