Description
给你一个 $n$ 个节点的有向树,问你这棵树的拓扑序个数,对大质数取模。多测,测试组数 $T$。
$1\leq n\leq 1000, 1\leq T\leq 5$
Solution
以 1 为根。记 $f_{u,i}$ 表示 $u$ 为根的子树中 $u$ 的拓扑序号为 $i$ 时的方案数。
从儿子 $v$ 向父亲 $u$ 转移时,考虑 $(u,v)$ 的方向。以 $u\rightarrow v$ 为例。
枚举 $u$ 的拓扑序号 $i$,$v$ 的拓扑序 $j$。那么 $u,v$ 的分别的原排列如图示($A,B$ 为原先在 $u$ 前/后的部分,$C,D$ 同理),
$$
\begin{aligned}
\underline{\quad A\quad}&\quad i\quad\underline{\quad B\quad}\
& \downarrow\
\underline{\quad C\quad}&\quad j\quad\underline{\quad D\quad}
\end{aligned}
$$
我们考虑 $u$ 在新序列中的位置 $k$,可以得到
$$
\text{new}f_{u,k} = \sum_{i,j}{k-1\choose i-1}{sz_u+sz_v-k\choose sz_u-i}f_{u,i}f_{v,j}
$$
其中 $sz_u$ 表示子树 $u$ 的大小。
容易发现 $j$ 这一维可以前缀和优化。
故最终复杂度为 $O(n^2)$。
Code
#include <bits/stdc++.h>
using namespace std;
const int yzh = 1000000007, N = 1000+5;
int f[N][N], sz[N], t, n, u, v, g[N], fac[N], ifac[N];
struct tt {
int to, nxt, c;//0->
} edge[N<<1];
int path[N], top;
char sign;
int C(int n, int m) {return 1ll*fac[n]*ifac[m]%yzh*ifac[n-m]%yzh; }
void dfs(int u, int fa) {
f[u][1] = sz[u] = 1;
for (int v, i = path[u]; i; i = edge[i].nxt)
if ((v = edge[i].to) != fa) {
dfs(v, u);
memcpy(g, f[u], sizeof(g));
memset(f[u], 0, sizeof(g));
if (edge[i].c == 0) {
for (int i = 1; i <= sz[u]; i++)
for (int k = i; k <= i+sz[v]-1; k++)
(f[u][k] += 1ll*C(k-1, i-1)*C(sz[u]+sz[v]-k, sz[u]-i)%yzh*g[i]%yzh*(f[v][sz[v]]-f[v][k-i])%yzh) %= yzh;
} else {
for (int i = 1; i <= sz[u]; i++)
for (int k = i+1; k <= i+sz[v]; k++)
(f[u][k] += 1ll*C(k-1, i-1)*C(sz[u]+sz[v]-k, sz[u]-i)%yzh*g[i]%yzh*f[v][k-i]%yzh) %= yzh;
}
sz[u] += sz[v];
}
for (int i = 1; i <= n; i++) (f[u][i] += f[u][i-1]) %= yzh;
}
void add(int u, int v, int c) {
edge[++top] = (tt){v, path[u], c};
path[u] = top;
}
int main() {
n = 1000;
ifac[0] = ifac[1] = fac[0] = 1;
for (int i = 2; i <= n; i++) ifac[i] = -1ll*yzh/i*ifac[yzh%i]%yzh;
for (int i = 1; i <= n; i++)
ifac[i] = 1ll*ifac[i]*ifac[i-1]%yzh,
fac[i] = 1ll*i*fac[i-1]%yzh;
scanf("%d", &t);
while (t--) {
scanf("%d", &n); top = 0;
for (int i = 1; i <= n; i++) {
path[i] = sz[i] = 0;
for (int j = 1; j <= n; j++) f[i][j] = 0;
}
for (int i = 1; i < n; i++) {
scanf("%d %c %d", &u, &sign, &v); ++u, ++v;
if (sign == '<') add(u, v, 0), add(v, u, 1);
else add(u, v, 1), add(v, u, 0);
}
dfs(1, 0);
printf("%d\n", (f[1][n]+yzh)%yzh);
}
return 0;
}