题面描述
树形图拓扑排序计数
题解
论用一种错误的顺序做三倍经验是一种怎样的体验
DAG 的拓扑排序计数一般是用 状压DP 解决的
但由于这道题树形图的特殊性质，我们可以考虑 树形DP
设 \(f_x\) 表示以 \(x\) 为根的子树拓扑排序的个数
考虑 \(f_x\) 如何由 \(f_y\) , \(y\in
son_x\) 推出
发现目前状态不足以表示状态，我们需要知道拓扑排序的大致形态
注意到 \(x\) 的取值只受 \(y\) 的取值的影响，所以就有
设 \(f_{x,n}\) 表示以 \(x\) 为根的子树 \(x\) 排名为 \(n\) 的拓扑排序个数
以此设计转移
当 \(y\) 在 \(x\) 前面时 考虑把 \(y\) 中有 \(j\) 在排名已为 \(i\) 的 \(x\) 之前，我们枚举 \(y\) 的不超过 \(j\) 的排名就有
\[
\begin{aligned}
f_{x,i+j-1}\ =\ \sum_{k=1}^j\binom{i+j-1}{i-1}
\binom{size_x+size_y-i-j}{size_y-j}f_{x,i}
\ f_{y,k}
\end{aligned}
\]
当 \(y\) 在 \(x\) 后面时 考虑把 \(y\) 中有 \(j\) 在排名已为 \(i\) 的 \(x\) 之前，我们枚举 \(y\) 的超过 \(j\) 的排名就有
\[
\begin{aligned}
f_{x,i+j-1}\ =\ \sum_{k=j+1}^{size_y}\binom{i+j-1}{i-1}
\binom{size_x+size_y-i-j}{size_y-j}f_{x,i}
\ f_{y,k}
\end{aligned}
\]
当我们把交换和式后发现只需要维护前缀和和后缀和即可
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
74
| #include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <vector>
#define int unsigned long long
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int N = 1000+5, P = 1e9+7;
int t, n, c[N][N];
vector<pair<int, int> > edge[N];
int f[N][N], size[N], g[N];
int pre[N][N], suf[N][N];
int C(int n, int m) { return n<m?0:c[n][m]; }
void dfs(int x, int fa)
{
size[x] = f[x][1] = 1;
for(int i = 0; i < edge[x].size(); ++i)
{
int y = edge[x][i].first, z = edge[x][i].second;
if(y == fa) continue; dfs(y, x);
memset(g, 0, sizeof(g));
if(z)
{
for(int i = 1; i <= size[x]; ++i)
for(int j = 1; j <= size[y]; ++j)
g[i+j] = (g[i+j]+f[x][i]*pre[y][j]%P*C(i+j-1, i-1)%P*C(size[x]+size[y]-i-j, size[x]-i)%P)%P;
}
else
{
for(int i = 1; i <= size[x]; ++i)
for(int j = 0; j <= size[y]; ++j)
g[i+j] = (g[i+j]+f[x][i]*suf[y][j+1]%P*C(i+j-1, i-1)%P*C(size[x]+size[y]-i-j, size[x]-i)%P)%P;
}
memcpy(f[x], g, sizeof(f[x]));
size[x] += size[y];
}
for(int i = 1; i <= size[x]; ++i) pre[x][i] = (pre[x][i-1]+f[x][i])%P;
for(int i = size[x]; i; --i) suf[x][i] = (suf[x][i+1]+f[x][i])%P;
}
int ans;
signed main()
{
t = read();
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])%P;
while(t--)
{
n = read();
for(int x = 1; x <= n; ++x) edge[x].clear();
memset(pre, 0, sizeof(pre));
memset(suf, 0, sizeof(suf));
for(int i = 1; i < n; ++i)
{
int x, y, z; char op[7];
scanf("%llu%s%llu", &x, op, &y);
z = op[0] == '<'; ++x; ++y;
edge[x].push_back(make_pair(y, z));
edge[y].push_back(make_pair(x, z^1));
}
dfs(1, 0); ans = 0;
for(int i = 1; i <= n; ++i) ans = (ans+f[1][i])%P;
printf("%llu\n", ans);
}
return 0;
}
|