Submission #2241978

---

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)
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[30], t2[30];
		vector<int> & om = t[who], & om2 = t2[who];
		if(om.empty()) {
			om.resize(len);
			om2.resize(len);
			om[0] = om2[0] = 1;
			int pierw = my_pow(3, 7 * 17);
			for(int rep = 0; rep < 22 - who; ++rep)
				pierw = mul(pierw, pierw);
			for(int i = 1; i < len; ++i)
				om[i] = mul(om[i-1], pierw);
			om2[len-1] = my_inv(om[len-1]);
			for(int i = 0; i < len; ++i) om2[i] = my_inv(om[i]);
			//~ pierw = my_inv(pierw);
			//~ for(int i = len - 2; i >= 0; --i) om2[i] = mul(om2[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], rev ? om2[k] : 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);
}
 
 
int main() {
	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

Judge Result