CF917D Stranger Trees

标签：连通 ifac Stranger int text 划分 Trees CF917D 条边

\(\text{Solution}\)

\(\text{have gained so many tricks。。。}\)
第一步：设恰好重合 \(i\) 条边的答案为 \(f(i)\)，至少重合 \(i\) 条边的答案为 \(g(i)\)
那么

\[g(i)=\sum_{j=i}^{n-1}\binom{j}{i}f(j) \]

二项式反演得

\[f(i)=\sum_{j=i}^{n-1}(-1)^{j-i}\binom{j}{i}g(j) \]

于是乎只需求 \(g(i)\)

第二步：转化求 \(g(i)\) 问题：选出 \(i\) 条边相当于把原图分成 \(n-i\) 个连通块，再连边使得所有连通块连通
有结论 \(g(i)=n^{n-i-2}\prod_{j=1}^i s_j\)，借助 \(\text{Prufer}\) 即可证明
于是问题相当于求一棵树划分成 \(i\) 个连通块，每种划分方式的贡献为所有连通块大小之积，求所有划分方式的贡献之和

第三步：这个问题可以树形 \(dp\) 解决
设 \(h_{u,i,j}\) 表示以 \(u\) 为根的子树已经划分出 \(i\) 个连通块，\(u\) 所在连通块大小为 \(j\) 且此连通块贡献还未算（即贡献还未乘上 \(j\)） 的答案
可以 \(O(n^3)\) 简单转移
事实上可以做到更优，考虑到一个连通块的贡献相当于这个连通块选出一个数的方案数
于是设 \(h_{u,i,0/1}\) 表示以 \(u\) 为根的子树已经划分出 \(i\) 个连通块，\(u\) 所在连通块还未/已经选出一个数的方案数
那么可以 \(O(n^2)\) 转移

\(\text{Code}\)

#include <bits/stdc++.h>
#define IN inline
#define eb emplace_back
using namespace std;

typedef long long LL;
const int N = 105, P = 1e9 + 7;
int n, g[N][N][2], G[N], sz[N], pw[N], fac[N], ifac[N], tg[N][2];
vector<int> E[N];

IN int C(int n, int m){return (LL)fac[n] * ifac[n - m] % P * ifac[m] % P;}
void dfs(int x, int fa) {
	g[x][1][0] = g[x][1][1] = sz[x] = 1;
	for(auto v : E[x]) if (v ^ fa) {
		dfs(v, x);
		for(int i = 1; i <= sz[x]; i++) {
			for(int j = 1; j <= sz[v]; j++) {
				tg[i + j][0] = (tg[i + j][0] + (LL)g[x][i][0] * g[v][j][1] % P) % P;
				tg[i + j][1] = (tg[i + j][1] + (LL)g[x][i][1] * g[v][j][1] % P) % P;
				tg[i + j - 1][0] = (tg[i + j - 1][0] + (LL)g[x][i][0] * g[v][j][0] % P) % P;
				tg[i + j - 1][1] = (tg[i + j - 1][1] + (LL)g[x][i][1] * g[v][j][0] % P + (LL)g[x][i][0] * g[v][j][1] % P) % P;
			}
		}
		sz[x] += sz[v];
		for(int i = 1; i <= sz[x]; i++) g[x][i][0] = tg[i][0], g[x][i][1] = tg[i][1], tg[i][0] = tg[i][1] = 0;
	}
}

int main() {
	scanf("%d", &n);
	for(int i = 1, u, v; i < n; i++) scanf("%d%d", &u, &v), E[u].eb(v), E[v].eb(u);
	dfs(1, 0), fac[0] = ifac[0] = ifac[1] = pw[0] = 1;
	for(int i = 1; i <= n; i++) fac[i] = (LL)fac[i - 1] * i % P, pw[i] = (LL)pw[i - 1] * n % P;
	for(int i = 2; i <= n; i++) ifac[i] = (LL)ifac[P % i] * (P - P / i) % P;
	for(int i = 2; i <= n; i++) ifac[i] = (LL)ifac[i] * ifac[i - 1] % P;
	for(int i = 0; i < n - 1; i++) G[i] = (LL)pw[n - i - 2] * g[1][n - i][1] % P;
	G[n - 1] = 1;
	for(int i = 0; i < n; i++) {
		int ans = 0;
		for(int j = i; j < n; j++) ans = (ans + (LL)((j - i & 1) ? P - 1 : 1) * C(j, i) % P * G[j] % P) % P;
		printf("%d ", ans);
	}
}

标签：连通,ifac,Stranger,int,text,划分,Trees,CF917D,条边
From： https://www.cnblogs.com/leiyuanze/p/17110330.html