题解 P3240 【[HNOI2015]实验比较】
xyz32768
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)$。
代码：
```cpp
#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;
}
```