Submission #906281
Source Code Expand
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }
template<int MOD>
struct ModInt {
static const int Mod = MOD;
unsigned x;
ModInt() : x(0) {}
ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
int get() const { return (int)x; }
ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
ModInt inverse() const {
signed a = x, b = MOD, u = 1, v = 0;
while(b) {
signed t = a / b;
a -= t * b; std::swap(a, b);
u -= t * v; std::swap(u, v);
}
if(u < 0) u += Mod;
ModInt res; res.x = (unsigned)u;
return res;
}
};
typedef ModInt<924844033> mint;
vector<int> t_parent;
vi t_ord;
void tree_getorder(const vector<vi> &g, int root) {
int n = g.size();
t_parent.assign(n, -1);
t_ord.clear();
vector<int> stk; stk.push_back(root);
while(!stk.empty()) {
int i = stk.back(); stk.pop_back();
t_ord.push_back(i);
for(int j = (int)g[i].size() - 1; j >= 0; j --) {
int c = g[i][j];
if(t_parent[c] == -1 && c != root)
stk.push_back(c);
else
t_parent[i] = c;
}
}
}
typedef mint fft_mint;
const int OmegaMax = 21;
fft_mint OmegaPrim = 44009197;
fft_mint Omega[OmegaMax + 1];
void fft_init() {
if(Omega[OmegaMax].get() != 0) return;
fft_mint x = OmegaPrim;
for(int i = OmegaMax; i >= 0; i --) {
Omega[i] = x;
x *= x;
}
}
//aを破壊する
void fft_main(int logn, const bool inv, fft_mint a[]) {
fft_init();
int n = 1 << logn;
fft_mint ww = Omega[logn];
if(inv) ww = ww.inverse();
for(int m = n, mi = 0; m >= 2; m >>= 1, mi ++) {
int mh = m >> 1;
fft_mint w = 1;
rep(i, mh) {
for(int j = i; j < n; j += m) {
int k = j + mh;
fft_mint x = a[j] - a[k];
a[j] += a[k];
a[k] = w * x;
}
w *= ww;
}
ww *= ww;
}
int i = 0;
reu(j, 1, n - 1) {
for(int k = n >> 1; k > (i ^= k); k >>= 1);
if(j < i) swap(a[i], a[j]);
}
}
void fft(int logn, fft_mint a[]) { fft_main(logn, false, a); }
void inverse_fft(int logn, fft_mint a[]) {
fft_main(logn, true, a);
int n = 1 << logn;
fft_mint invn = fft_mint(n).inverse();
rep(i, n) a[i] *= invn;
}
//v, wを破壊し、vに結果を返す
//v, wのサイズは 2^logn, lognはceil(log_2(size(v) + size(w)))必要
void convolution(fft_mint v[], fft_mint w[], int logn) {
fft(logn, v); fft(logn, w);
rep(i, 1 << logn) v[i] *= w[i];
inverse_fft(logn, v);
}
vector<mint> fact, factinv;
void nCr_computeFactinv(int N) {
N = min(N, mint::Mod - 1);
fact.resize(N + 1); factinv.resize(N + 1);
fact[0] = 1;
rer(i, 1, N) fact[i] = fact[i - 1] * i;
factinv[N] = fact[N].inverse();
for(int i = N; i >= 1; i --) factinv[i - 1] = factinv[i] * i;
}
mint nCr(int n, int r) {
if(n >= mint::Mod)
return nCr(n % mint::Mod, r % mint::Mod) * nCr(n / mint::Mod, r / mint::Mod);
return r > n ? 0 : fact[n] * factinv[n - r] * factinv[r];
}
int main() {
int N;
while(~scanf("%d", &N)) {
vector<vector<int> > g(N);
for(int i = 0; i < N - 1; ++ i) {
int u, v;
scanf("%d%d", &u, &v), -- u, -- v;
g[u].push_back(v);
g[v].push_back(u);
}
tree_getorder(g, 0);
vi tsize(N, 1);
for(int ix = (int)t_ord.size() - 1; ix > 0; -- ix) {
int i = t_ord[ix], p = t_parent[i];
tsize[p] += tsize[i];
}
int logn = 1;
while(1 << logn < (N + 1) * 2) ++ logn;
vector<mint> v(1 << logn);
rep(i, N) {
if(i != 0) v[N - tsize[i]] += 1;
for(int j : g[i]) if(j != t_parent[i])
v[tsize[j]] += 1;
}
nCr_computeFactinv(N);
rep(i, N + 1)
v[i] *= fact[i];
vector<mint> w(1 << logn);
rep(i, N + 1)
w[i] = factinv[N - i];
convolution(v.data(), w.data(), logn);
rep(k, N + 1)
v[N + k] *= factinv[k];
rer(k, 1, N) {
mint ans;
ans += nCr(N, k) * k;
ans += nCr(N - 1, k) * N - v[N + k];
printf("%d\n", ans.get());
}
}
return 0;
}
Submission Info
Submission Time
2016-10-01 22:00:23+0900
Task
F - Many Easy Problems
User
anta
Language
C++14 (GCC 5.4.1)
Score
1900
Code Size
5110 Byte
Status
AC
Exec Time
321 ms
Memory
21868 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:146:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &u, &v), -- u, -- v;
^
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
269 ms
21616 KB
doublestar1
AC
267 ms
21616 KB
doublestar2
AC
269 ms
21616 KB
doublestar3
AC
268 ms
21616 KB
doublestar4
AC
269 ms
21616 KB
example0
AC
3 ms
256 KB
example1
AC
3 ms
256 KB
example2
AC
3 ms
256 KB
line0
AC
288 ms
21304 KB
line1
AC
288 ms
21304 KB
line2
AC
291 ms
21304 KB
line3
AC
287 ms
21304 KB
line4
AC
294 ms
21304 KB
maxrand0
AC
309 ms
21496 KB
maxrand1
AC
301 ms
21496 KB
maxrand10
AC
300 ms
21496 KB
maxrand11
AC
302 ms
21492 KB
maxrand12
AC
303 ms
21496 KB
maxrand13
AC
300 ms
21496 KB
maxrand14
AC
300 ms
21496 KB
maxrand15
AC
307 ms
21496 KB
maxrand16
AC
305 ms
21496 KB
maxrand17
AC
321 ms
21496 KB
maxrand18
AC
309 ms
21496 KB
maxrand19
AC
300 ms
21496 KB
maxrand2
AC
302 ms
21496 KB
maxrand3
AC
303 ms
21496 KB
maxrand4
AC
299 ms
21496 KB
maxrand5
AC
306 ms
21624 KB
maxrand6
AC
307 ms
21496 KB
maxrand7
AC
304 ms
21492 KB
maxrand8
AC
301 ms
21496 KB
maxrand9
AC
318 ms
21496 KB
rand0
AC
5 ms
512 KB
rand1
AC
3 ms
256 KB
rand2
AC
4 ms
384 KB
rand3
AC
5 ms
512 KB
rand4
AC
3 ms
384 KB
rand5
AC
5 ms
512 KB
rand6
AC
4 ms
384 KB
rand7
AC
5 ms
512 KB
rand8
AC
3 ms
256 KB
rand9
AC
4 ms
384 KB
star0
AC
264 ms
21868 KB
star1
AC
263 ms
21868 KB
star2
AC
262 ms
21864 KB
star3
AC
262 ms
21868 KB
star4
AC
262 ms
21868 KB