CF512D Fox And Travelling 题解

CF512D Fox And Travelling

题意

• 给定一张 $n$ 个点 $m$ 条边的无向图。
• 一个点只有当与它直接相连的点中最多只有一个点未被遍历过时才可被遍历。
• 询问对于每个 $k \in [0,n]$，遍历 $k$ 个点的方案数。
• $n \le 100$，$m \le \frac{n(n-1)}2$，答案对 $10^9+9$ 取模。

题解

首先，在环中的点一定不会被遍历。

用类似拓扑排序的过程可以把环上的点全部扔掉，剩下的点会构成若干个有根树和无根树，其中有根树的根是树中唯一与环中的点相连的点。

每棵树求出答案后，01 背包合并即可，中间只需要乘上一个组合数。

对于有根树，设 $f_{i,j}$ 为 $i$ 的子树中选 $j$ 个的方案数，那么就是树上背包，同样需要乘上一个组合数。

对于无根树，以树中每个点为根做一次有根树的树上背包，这样会发现每种选择 $i$ 个点的方案会被算 $s - i$ 次，其中 $s$ 为这棵无根树的大小，那么除掉即可。

总时间复杂度 $\mathcal O(n^3)$，其中背包经过了上下界优化，原理简单来说就是「每对点只会在 LCA 处合并一次」。

代码

const int N = 107;
int n, m, d[N], w[N], b[N], s[N], S;
vi e[N];
modint p[N], v[N], vp[N], f[N][N], ans[N];

inline modint C(int a, int b) {
	return p[a] * vp[b] * vp[a-b];
}

void dfs(int x, int o, int &s) {
	b[x] = o, ++s;
	for (ui i = 0; i < e[x].size(); i++) {
		int y = e[x][i];
		if (!d[y] && !b[y]) dfs(y, o, s);
	}
}

void dp(int x, int fa) {
	s[x] = 1, f[x][0] = 1;
	for (ui i = 0; i < e[x].size(); i++) {
		int y = e[x][i];
		if (b[x] != b[y] || y == fa) continue;
		dp(y, x);
		for (int j = 0; j < s[y]; j++) f[x][s[x]+j] = 0;
		for (int j = s[x] - 1; ~j; j--)
			for (int k = 1; k <= s[y]; k++)
				f[x][j+k] += f[x][j] * f[y][k] * C(j + k, j);
		s[x] += s[y];
	}
	f[x][s[x]] = f[x][s[x]-1];
}

void get(int x) {
	dp(x, 0);
	for (int i = 0; i <= s[x]; i++) f[0][i] += f[x][i];
}

int main() {
	rd(n), rd(m);
	p[0] = v[0] = 1;
	for (int i = 1; i <= n; i++) p[i] = p[i-1] * i;
	vp[n] = p[n] ^ -1;
	for (int i = n; i; i--) v[i] = p[i-1] * vp[i], vp[i-1] = vp[i] * i;
	for (int i = 1, x, y; i <= m; i++) rd(x), rd(y), e[x].pb(y), e[y].pb(x), ++d[x], ++d[y];
	queue<int> q;
	for (int i = 1; i <= n; i++) if (d[i] <= 1) w[i] = 1, q.push(i);
	while (q.size()) {
		int x = q.front();
		q.pop();
		for (ui i = 0; i < e[x].size(); i++) {
			int y = e[x][i];
			if (--d[y] <= 1 && !w[y]) w[y] = 1, q.push(y);
		}
	}
	for (int i = 1; i <= n; i++) if (d[i] == 1) dfs(i, i, s[i]);
	for (int i = 1; i <= n; i++) if (!d[i] && !b[i]) dfs(i, i, s[i]);
	ans[0] = 1;
	for (int i = 1; i <= n; i++)
		if (i == b[i]) {
			int o = s[i];
			if (d[i] == 1) get(i);
			else {
				for (int j = 1; j <= n; j++)
					if (b[j] == i) get(j);
				for (int j = 0; j <= o; j++) f[0][j] *= v[o-j];
			}
			for (int j = S; ~j; j--)
				for (int k = 1; k <= o; k++)
					ans[j+k] += ans[j] * f[0][k] * C(j + k, j);
			for (int j = 0; j <= o; j++) f[0][j] = 0;
			S += o;
		}
	for (int i = 0; i <= n; i++) print(ans[i]);
	return 0;
}