【题解】LOJ 2117 「HNOI2015」实验比较

请注意,本文编写于 136 天前,最后修改于 136 天前,其中某些信息可能已经过时。

Problem

给定 $m$ 条形如 $x<y$ 或者 $x=y$ 的关系,求 $1-n$ 用 $<$ 和 $=$ 连成一个序列有多少种本质不同的方式

Thought

将相同的点缩起来,有 $<$ 关系的用边连起来,这样就形成了一片森林
将所有根节点和 $0$ 连起来,就形成了一棵树

显然,每个点的子树之间是没有任何关系的,也就是说我们可以任意安排它们之间的顺序

设 $f[i][j]$ 为以 $i$ 为序列第一段,共分为 $j$ 段有多少种方案

设点 $u$ 的儿子为 $v$ ,考虑如何转移贡献

显然, $u$ 所在序列中第一段必然为 $u$ ,那么后面段可以由两者剩余段合并构成

设当前 $u$ 序列长度为 $j$ , $v$ 序列长度为 $k$ ,需要转移到长度为 $l$ 的序列,即

先用 $u$ 序列中 $j$ 个随意占一些位置,其中第一个(也就是 $u$ ) 只能放到第一位
也就是说序列中占了 $j$ 个位置,还有 $l-j$ 个是空的,一共有 ${l-1\choose j-1}$ 种方案

接下来的 $k$ 个必须要将所有空位全部占满,$k$ 个中有 $l-j$ 个需要取占据空位,也就是说还有 $j+k-l$ 个可以随意选择位置,显然只能选择除 $1$ 号位外 $u$ 序列占据的位置,共 $j-1$ 个

所以答案为

$$ f[u][l]=f[u][j]*f[v][k]*{l-1\choose j-1}{j-1\choose j+k-l} $$

最终答案为 $\sum_{i=1}^{n} f[0][i+1]$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 110;
const int mod = 1000000007;
typedef pair <int, int> P;
struct Edge {
    int t, n;
}e[N << 1];
int head[N], tot;
int c[N][N];
int fa[N], num[N];
int n, m;
int f[N][N], siz[N], g[N];
bool in[N];
P line[N];
int lineCnt;
void addedge(int u, int v) {
    e[++ tot] = {v, head[u]};
    head[u] = tot;
}
int find(int x) {
    return fa[x] = (fa[x] == x ? fa[x] : find(fa[x]));
}
void merge(int a, int b) {
    a = find(a); b = find(b);
    if(num[a] < num[b])
        swap(a, b);
    num[a] += num[b]; num[b] = 0;
    fa[b] = a;
}
void dfs(int x) {
    siz[x] = 1; f[x][1] = 1;
    for(int i = head[x]; i; i = e[i].n) {
        dfs(e[i].t);
        memset(g, 0, sizeof(g));
        for(int j = 1; j <= siz[x]; ++ j)
            for(int k = 1; k <= siz[e[i].t]; ++ k)
                for(int l = max(j, k + 1); l <= j + k; ++ l) {
                    g[l] += 1ll * f[x][j] * f[e[i].t][k] % mod * c[l - 1][j - 1] % mod * c[j - 1][j + k - l] % mod;
                    if(g[l] >= mod) g[l] -= mod;
                }
        siz[x] += siz[e[i].t];
        for(int j = 0; j <= siz[x]; ++ j)
            f[x][j] = g[j];
    }
}
int main() {
    #ifndef ONLINE_JUDGE
        freopen("in", "r", stdin);
    #endif
    n = read(); m = read();
    for(int i = 1; i <= n; ++ i) {
        fa[i] = i;
        num[i] = 1;
    }
    for(int i = 0; i <= n; ++ i)
        c[i][0] = 1;
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= i; ++ j)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    for(int i = 1; i <= m; ++ i) {
        int x = read();
        char ch = getchar();
        int y = read();
        if(ch == '<')
            line[++ lineCnt] = {x, y};
        else
            merge(x, y);
    }
    for(int i = 1; i <= lineCnt; ++ i) {
        int x = line[i].first, y = line[i].second;
        x = find(x); y = find(y);
        if(x == y) {
            puts("0");
            return 0;
        }
        addedge(x, y);
        in[y] = 1;
    }
    for(int i = 1; i <= n; ++ i)
        if(!in[i] && fa[i] == i)
            addedge(0, i);
    dfs(0);
    int ans = 0;
    for(int i = 1; i <= n; ++ i)
        ans = (ans + f[0][i + 1]) % mod;
    printf("%d\n", ans);
    return 0;
}
Comments

添加新评论