HEOI2013 SAO

题意

给出一颗边有方向的树，求该图的拓扑序数量。

n≤1000,mod=109+7n\le 1000,mod= 10^9+7

题解

f(u,i)f(u,i) 表示以 uu 为根的子树，uu 子树内排名为 ii 的方案数。

考虑转移，枚举 v∈son(u)v\in son(u) ，将 f(v,j)f(v,j) 合并到 f(u,i)f(u,i)，（两列数，各自顺序不打乱的合并）

  • vv 在 uu 前

    再枚举 vv 子树中有 k(k≥j)k(k\ge j) 个排在 uu 前面，对 f(u,i+j)f(u,i+j) 累加。

    f(u,i+k)′←f(u,i+k)+(i+k−1i−1)(sizu+sizv−i−ksizv−k)f(u,i)f(v,j)f(u,i+k)' \gets f(u,i+k)+\binom{i+k-1}{i-1}\binom{siz_u+siz_v-i-k}{siz_v-k}f(u,i)f(v,j)

  • vv 在 uu 后

    同样枚举 vv 子树中有 k(k<j)k(k<j) 个排在 uu 前，式子一样的，注意 k,jk,j 大小关系不一样就行了。

在前缀和处理一下就可以 O(1)O(1) 转移了

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
template <typename Tp>
inline void read(Tp &x) {
    x = 0; bool fg = 0; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') fg ^= 1; ch = getchar();}
    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (Tp)(ch ^ 48), ch = getchar();
    if (fg) x = -x;
}
template <typename Tp, typename... Args>
void read(Tp &t, Args &...args) { read(t); read(args...); }
using namespace std;
typedef long long ll;
const int N = 1005;
const int mod = 1e9 + 7;
int head[N], pnt[N << 1], nxt[N << 1], W[N << 1], E;
int T, n, siz[N];
ll dp[N][N], C[N][N], tmp[N];
template <typename Tp> void Mul(Tp &x, Tp y) { x = (x * y) % mod; }
template <typename Tp> void Add(Tp &x, Tp y) { x = (x + y) % mod; }
void adde(int u, int v, int w) {
    E++; pnt[E] = v; W[E] = w; nxt[E] = head[u]; head[u] = E;
}
void dfs(int u, int f) {
    siz[u] = 1; dp[u][1] = 1;
    for (int _ = head[u]; _; _ = nxt[_]) {
        int v = pnt[_];
        if (v == f) continue;
        dfs(v, u);
        for (int i = 1; i <= siz[v]; ++i) Add(dp[v][i], dp[v][i - 1]);
        memset(tmp, 0, sizeof(tmp));
        for (int i = 1; i <= siz[u]; ++i) {
            for (int k = 0; k <= siz[v]; ++k) {
                if (W[_]) {
                    // j <= k
                    Add(tmp[i + k], C[i + k - 1][k] * C[siz[u] + siz[v] - i - k][siz[v] - k]
                           % mod * dp[u][i] % mod * dp[v][k] % mod);
                } else { 
                    // j > k
                    Add(tmp[i + k], C[i + k - 1][k] * C[siz[u] + siz[v] - i - k][siz[v] - k]
                           % mod * dp[u][i] % mod * (dp[v][siz[v]] - dp[v][k] + mod) % mod);
                }
            }
        }
        siz[u] += siz[v];
        for (int i = 1; i <= siz[u]; ++i) dp[u][i] = tmp[i];
    }
}
void rmain() {
    read(n);
    memset(head, 0, sizeof(head)); E = 0;
    for (int i = 1; i < n; ++i) {
        int a, b; char op[10];
        scanf("%d%s%d", &a, op, &b); ++a, ++b;
        if (op[0] == '>') swap(a, b);
        adde(a, b, 1), adde(b, a, 0);
    }
    memset(dp, 0, sizeof(dp));
    dfs(1, 0);
    ll ans = 0;
    for (int i = 1; i <= n; ++i) Add(ans, dp[1][i]);
    cout << ans << endl;
}

int main() {
    C[0][0] = 1;
    for (int i = 1; i < N; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
    read(T);
    while (T--) rmain();
    return 0;
}