题解 P4099【[HEOI2013]SAO】

zhiyangfan · 2021-08-05 17:19:14 · 题解

这题好sao啊

题意简述

给一个 n 个节点 n-1 条边的有向图，且保证任何两点之间都有一定的关联性，求拓扑序个数，对 p 取模。（ n \le 1000,p=10^9+7 ）

思路分析

有向图的拓扑序个数看起来就是一脸不可求的样子，这提醒我们注意题目中的特殊性质——如果我们把有向边看成无向边，原图就构成了一棵树。而树型DP肯定是要比拓扑序个数好做的。

考虑设 f_{i,j} 表示以 i 为根的子树中，i 的拓扑序排名第 j 的方案数。这个状态还是比较套路的，难点在于转移。

根据树型DP的通常套路，我们考虑怎么把子结点的信息往父结点合并。比如我们要把 f_{v,k} 往 f_{u,i} 上合并（其中 u 是 v 的父结点 ），那会出现两种情况：一种是在以 u 为根的子树中，v 的拓扑序在 u 前，即 \cdot\cdot\cdot v\cdot\cdot\cdot u\cdot\cdot\cdot ，另一种就是 u 在 v 前，即 \cdot\cdot\cdot u\cdot\cdot\cdot v\cdot\cdot\cdot 。

我们分别考虑每种情况怎么转移。当 u 在 v 前时，u 排在第 i 位，说明它前面有 i-1 个结点，同理，v 的前面有 k-1 个结点，合并时，我们就假设有 j 个结点合并到了 u 前面，这下转移方程就呼之欲出了。新的状态应该是 f_{u,i+j} ，原来方案数应该是 f_{u,i}\times f_{v,k} ，而选 j 个放到 u 前的方案数是 \binom{i+j-1}{j}\binom{size_u+size_v-i-j}{size_v-j} ，组合意义大概是从在拓扑序中位于 u 之前的元素（ i+j-1 个 ）选 j 个是从 v 子树来的，从拓扑序中位于 v 之后的元素（ size_u+size_v-i-j 个 ）选 size_v-j 个是从 v 子树来的。所以最终的转移方程为 f_{u,i+j}=\binom{i+j-1}{j}\binom{size_u+size_v-i-j}{size_v-j}f_{u,i}\times f_{v,k} 。考虑一下每个变量的范围。显然 1\le i\le size_u,1\le k\le size_v 而由于 v 还在 u 后，所以最多有 k-1 个在 u 前，即 0\le j<k

另一种情况是类似的，依然是选从在 u 前面的 i+j-1 个选 j 个来自 v ，从在 u 后面的 size_u+size_v-i-j 个选 size_v-j 个来自 v 。所以转移方程不变，但因为 v 在 u 前，所以至少有 k 个在 u前，即 k\le j\le size_v ，其余范围不变。

接下来考虑复杂度。i,j,k 全需要枚举，所以复杂度为 \mathcal{O}(n^3) ，不足以通过本题。我们来把枚举换成求和式再来推导一下（以 u 在 v 前为例）:

这里展示过程主要是为了帮助一些像我一样的不会很快地换求和顺序的同学。这里的方法是先交换求和顺序，把从里面换到外面的顶满范围，再用艾佛森约定加以限制，最后通过限制外面换到里面的变量的取值范围来满足艾佛森约定（虽然笨但好用啊）（ v 在 u 前类似，留给读者自行推导）。

注意到这样的话后面可以把 f_{v,k} 提出来变成前缀和的形式，这样就优化掉了一个变量的枚举，复杂度降低为 \mathcal{O}(n^2) ，足以通过本题。

代码环节

有一些细节放在注释啦。

#include <cstdio>
#include <cstring>
const int N = 2e3 + 10, mod = 1e9 + 7;
typedef long long ll; ll C[N][N];
struct edge{ int v, next, w; }E[N << 1]; int p[N], cnt;
inline void init() { memset(p, -1, sizeof p); cnt = 0; }
inline void insert(int u, int v, int w)
{ E[cnt].w = w; E[cnt].v = v; E[cnt].next = p[u]; p[u] = cnt++; }
int size[N]; ll f[N][N], g[N];
void dfs(int u, int fa)
{
    size[u] = 1; f[u][1] = 1;
    for (int t = p[u], v; t + 1; t = E[t].next)
    {
        v = E[t].v; if (v == fa) continue;
        dfs(v, u);
        //注意到并入时用到的f值都应该是并入前的f值，所以要提前记录一下
        //否则在转移时会受到影响 
        for (int i = 1; i <= size[u]; i++) g[i] = f[u][i], f[u][i] = 0;
        if (E[t].w)
        {
            //这里0是因为前面有可能一个都没有
            //<是因为v在u后面，v子树不可能全部都在u前面 
            for (int i = 1; i <= size[u]; i++)
                for (int j = 0; j < size[v]; j++)
                    f[u][i + j] = (f[u][i + j] + 
                    C[size[u] + size[v] - i - j][size[v] - j] * C[i + j - 1][j] % mod
                    * g[i] % mod * (f[v][size[v]] - f[v][j] + mod) % mod) % mod;
        }
        else
        {
            //这里1是因为前面至少有个v
            //<=是因为v就在u前面，v子树有可能全在u前面 
            for (int i = 1; i <= size[u]; i++)
                for (int j = 1; j <= size[v]; j++)
                    f[u][i + j] = (f[u][i + j] + 
                    C[size[u] + size[v] - i - j][size[v] - j] * C[i + j - 1][j] % mod
                    * g[i] % mod * f[v][j] % mod) % mod;
        }
        size[u] += size[v]; //注意最后再合并size,可以降低复杂度
    }
    for (int i = 1; i <= size[u]; i++) f[u][i] = (f[u][i] + f[u][i - 1]) % mod;
}
int main()
{
    int T, n; scanf("%d", &T); char opt[5]; C[0][0] = 1;
    for (int i = 1; i < N; i++) //这里之前因为写了<=导致开O2RE了好几发/wul
    {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }   
    while (T--)
    {
        init(); scanf("%d", &n);
        for (int i = 1, x, y; i < n; i++)
        {
            scanf("%d", &x); ++x; scanf("%s", opt); scanf("%d", &y); ++y;
            insert(x, y, opt[0] == '<'); insert(y, x, opt[0] == '>');
            //<表示x的拓扑序一定在y之前，转移时会用到 
        }
        dfs(1, 0);
        printf("%lld\n", f[1][n]);
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++) f[i][j] = 0;
            size[i] = 0;
        }    //多测不清空，爆零见祖宗
    }
    return 0;
}