AGC005F: Many Easy Problems

https://beta.atcoder.jp/contests/agc005/tasks/agc005_f

FMT初実装です。

まず求めるものを式にすると
ans[K]=1/(K!)Σ(i=K...N)cnt[i]*(i!)/(i-K)!
となります。ただしcnt[i]はサイズがiである部分木の数です。
これを式変形すると、
ans[N-u]=1/((N-u)!)Σ(i=0...u)d[u-i]*e[i]となります。
ただしd[i]=cnt[N-i]*(N-i)!、e[i]=1/(i!)です。このようにdi,eiがK(またはu)に依存しない式が立てれれば、FMTが使えます。iとK-iの式で表わせる形があったらFFTを疑ったほうが良さそうですね。

FMTですが、FFTとほとんど同じです。代わりにω^n=1(mod p)を満たすようなωを探せばいいだけです。その際にpの原始根が必要になるんですが、与えられるpは因数分解すると綺麗な形になっているので、見つけるのもそんなに苦労はしないです。

今回はp=924844033ですが原子根の１つに5があります。

struct FMT {
	const int num_factor = 3;
	ll factor[3] = {2, 3, 7};
	ll gen = 5;

	ll mod_pow(ll a, ll n) {
		if(n == 0) return 1;
		ll res = mod_pow(a, n / 2);
		if(n % 2 == 0) return res * res % mod;
		else return a * res % mod * res % mod;
	}

	bool check() {
		rep(i, 0, num_factor) {
			if(mod_pow(gen, (mod - 1) / factor[i]) == 1) {
				return false;
			}
		}
		return true;
	}
	void fmt(vector<ll>& v, bool rev = false) { //v.size() == (1 << x)
		int n = sz(v), i, j;
		for(i = 0, j = 1; j < n - 1; j++) {
			for(int k = n >> 1; k > (i ^= k); k /= 2);
			if(i > j) swap(v[i], v[j]);
		}
		for(int m = 2; m <= n; m *= 2) {
			ll root = mod_pow(gen, (mod - 1) / m);
			for(int i = 0; i < n; i += m) {
				ll w = 1;
				rep(j, 0, m / 2) {
					ll f0 = v[i + j], f1 = w * v[i + j + m / 2] % mod;
					v[i + j] = (f0 + f1) % mod;
					v[i + j + m / 2] = (mod + f0 - f1) % mod;
					MUL(w, root);
				}
			}
		}
		if(rev) rep(i, 0, n) MUL(v[i], mod_pow(n, mod - 2));
	}
	vector<ll> get(const vector<ll>& A, const vector<ll>& B) {
		int n = 1;
		int len = sz(A) + sz(B) - 1;
		while(n < len) n *= 2;
		vector<ll> a(n, 0), b(n, 0);
		rep(i, 0, sz(A)) a[i] = A[i];
		rep(i, 0, sz(B)) b[i] = B[i];
		fmt(a); fmt(b);
		rep(i, 0, n) MUL(a[i], b[i]);
		reverse(++a.begin(), a.end());
		fmt(a, true);
		vector<ll> res(len);
		rep(i, 0, len) res[i] = a[i];
		return res;
	}
};

int N;
vi G[MAX_N];
int cnt[MAX_N];

int dfs(int v, int p = -1) {
	int res = 1;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(n == p) continue;
		res += dfs(n, v);
	}
	if(p != -1) {
		cnt[res]++;
		cnt[N - res]++;
	}
	return res;
}

void solve() {
	cin >> N;
	C_init(N + 10);
	rep(i, 0, N - 1) {
		int a, b;
		cin >> a >> b; a--; b--;
		G[a].pb(b);
		G[b].pb(a);
	}
	dfs(0);
	
	vector<ll> D(N + 1), E(N + 1);
	rep(i, 0, N + 1) {
		D[i] = cnt[N - i] * fac[N - i] % mod;
		E[i] = fiv[i];
	}
	FMT f;
	vector<ll> F = f.get(D, E);
	vector<ll> ans(N + 1);
	rep(i, 0, N) {
		ans[N - i] = (mod + N * C(N, i) % mod - fiv[N - i] * F[i] % mod) % mod;
	}
	rep(i, 1, N + 1) cout << ans[i] << "\n";
}