自动搬运

查看原文

来自洛谷，原作者为

	xyz32768 “各方面相差太远”

搬运于2025-08-24 21:46:51，当前版本为作者最后更新于2018-03-17 21:13:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

先用并查集将所有用等号连接的点缩成一个。然后看到题目中有一个很重要的条件：

对每张图片$i$，小D都最多只记住了某一张质量不比$i$差的另一张图片$K_i$。

缩点后建树，对于每个$i$，如果$K_i$存在，就将$K_i$作为$i$的父节点。建树后有可能是一棵森林，所以新建一个新的节点$n+1$连接森林里每棵树的根节点，形成一棵树，$n+1$为根。

然后树形DP，$f[u]$表示$u$的子树内的方案数。

但对于$u$的两个不同子节点$v$和$w$，$v$和$w$的子树内可能存在两个点质量相等，所以还需要加一维：

$f[u][i]$表示$u$的子树里，分成$i$段（也就是共有$i-1$个小于号把质量序列分成了$i$个部分，每个部分里的图片质量相等）的方案数，然后做一次树形背包DP（当前枚举到了$u$的子节点$v$，$f'$表示枚举到子节点$v$之前的DP值）：

$$f[u][i]=\sum_{j,k}f'[u][j]\times f[v][k]\times ORZ $$

$ORZ$表示$j$段和$k$段合并成$i$段的方案数。

如何求$ORZ$呢？

设$f[u]$的质量序列为$A$，$f'[u]$的质量序列为$B$，$f[v]$的质量序列为$C$。

$A$中的每一段可以只包含$B$中的一段，可以只包含$C$中的一段，也可以有$B$和$C$中各一段合并而成，但不能为空。特殊地，$A$的第一段只能包含节点$u$。

相当于先枚举$B$中的$j-1$段在$A$中放的位置，方案数为$C_{i-1}^{j-1}$，然后把$C$中的$i-j$段放到$A$中剩下的位置，使每一段都不为空。现在$C$中还剩下$k-i+j$个段，他们需要与$B$中的段合并，方案数$C_{j-1}^{k-i+j}$。

所以：

$$ORZ=C_{i-1}^{j-1}\times C_{j-1}^{k-i+j}$$

最后答案$\sum_{i}f[n+1][i]$。

复杂度：$f[u][i]$第二维的上界只有$u$的子树大小，枚举$i$相当于枚举$i$的子树内的点。所以看上去是$O(n^4)$的，实际上每对点都只在lca处被计算贡献了$O(n)$次，复杂度$O(n^3)$。

代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
	int res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	return bo ? ~res + 1 : res;
}
inline char get() {
	char c; while ((c = getchar()) != '<' && c != '='); return c;
}
const int N = 135, M = 265, ZZQ = 1e9 + 7;
int n, m, X[N], Y[N], fa[N], ecnt, nxt[M], adj[N], go[M], in[N], cnt[N],
f[N][N], sze[N], C[N][N], g[N];
bool eq[N], its[N];
void init() {
	int i, j; for (i = 0; i <= 120; i++) C[i][0] = 1;
	for (i = 1; i <= 120; i++) for (j = 1; j <= i; j++)
		C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % ZZQ;
}
void add_edge(int u, int v) {
	nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
	nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u;
}
int cx(int x) {
	if (fa[x] != x) fa[x] = cx(fa[x]);
	return fa[x];
}
bool zm(int x, int y) {
	int ix = cx(x), iy = cx(y);
	if (ix != iy) fa[iy] = ix;
	else return 1;
	return 0;
}
void dfs(int u, int fu) {
	int i, j, k; sze[u] = f[u][1] = 1;
	for (int e = adj[u], v; e; e = nxt[e]) {
		if ((v = go[e]) == fu) continue; dfs(v, u);
		for (i = 1; i <= n; i++) g[i] = 0;
		for (i = 1; i <= sze[u] + sze[v]; i++) for (j = 1; j <= sze[u]; j++)
		for (k = 1; k <= sze[v]; k++) {
			int x = k - i + j; if (x < 0) continue;
			(g[i] += 1ll * f[u][j] * f[v][k] % ZZQ *
				C[i - 1][j - 1] % ZZQ * C[j - 1][x] % ZZQ) %= ZZQ;
		}
		for (i = 1; i <= sze[u] + sze[v]; i++) f[u][i] = g[i];
		sze[u] += sze[v]; 
	}
}
int main() {
	int i; n = read(); m = read(); init();
	for (i = 1; i <= n; i++) fa[i] = i;
	for (i = 1; i <= m; i++) X[i] = read(),
		eq[i] = get() == '=', Y[i] = read();
	for (i = 1; i <= m; i++) if (eq[i]) zm(X[i], Y[i]);
	for (i = 1; i <= n; i++) its[in[i] = cx(i)] = 1;
	for (i = 1; i <= n; i++) fa[i] = i;
	for (i = 1; i <= m; i++)
		if (!eq[i]) {
			add_edge(in[X[i]], in[Y[i]]); cnt[in[Y[i]]]++;
			if (zm(in[X[i]], in[Y[i]])) return printf("0\n"), 0;
		}
	for (i = 1; i <= n; i++) if (its[i] && !cnt[i]) add_edge(n + 1, i);
	int ans = 0; dfs(n + 1, 0); for (i = 1; i <= sze[n + 1]; i++)
		ans = (ans + f[n + 1][i]) % ZZQ; cout << ans << endl;
	return 0;
}