\[\]
\(\color{green}\text{P4099 [HEOI2013] SAO}\)
Problem
每次给定一棵树以及边的定向，求拓扑序列数。
\(1 \le n \le 3000\)。
Sol
定义 \(f_{i, j}\) 表示 \(i\) 的子树内，\(i\) 在拓扑序中是第 \(j\) 个的拓扑序列数。
考虑合并 \(f_{u, i}\)，\(f_{v, j}\)（\(u\) 为 \(v\) 的父亲），枚举出选 \(u\) 前选 \(v\) 中的点数 \(k\)：
- 当边为 \(u \gets v\) 时，对于 \(j \le k \le sz_v\)，有贡献：\(f'_{u, i + k} \gets f'_{u, i + k} + \binom{i-1+k}{i-1}\binom{sz_u-i+sz_v-k}{sz_u-i}f_{u, i}f_{v, j}\)。
- 当边为 \(u \to v\) 时类似，对于 \(0 \le k < j\)，有贡献：\(f'_{u, i + k} \gets f'_{u, i + k} + \binom{i-1+k}{i-1}\binom{sz_u-i+sz_v-k}{sz_u-i}f_{u, i}f_{v, j}\)。
这两种情况都可以直接枚举 \(i, k\) 然后前缀和。
时间复杂度 \(O(n^2)\)。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define pb emplace_back
const int N = 3010, P = 1e9 + 7;
ll QPow(ll a, ll b) {ll res = 1;for (; b; b >>= 1, a = a * a % P)if (b & 1)res = res * a % P;return res;
}
ll ifac[N], fac[N];
ll C(int n, int m) {ll res = (n < m || n < 0 || m < 0) ? 0 : fac[n] * ifac[n - m] % P * ifac[m] % P;return res;
}
void Init() {int n = 3e3;fac[0] = 1;for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % P;ifac[n] = QPow(fac[n], P - 2);for (int i = n - 1; i >= 0; i--) ifac[i] = ifac[i + 1] * (i + 1) % P;
}
int n;
vector<pii> e[N];
ll f[N][N], s[N], g[N], sz[N];
void M1(int u, int v) {memset(g, 0, (sz[u] + sz[v] + 3) * sizeof (ll));for (int i = 1; i <= sz[v]; i++) s[i] = (s[i - 1] + f[v][i]) % P;for (int i = 1; i <= sz[u]; i++)for (int k = 1; k <= sz[v]; k++)(g[i + k] += C(i - 1 + k, i - 1) * C(sz[u] - i + sz[v] - k, sz[u] - i) % P * f[u][i] % P * s[k]) %= P;memcpy(f[u], g, (sz[u] + sz[v] + 3) * sizeof (ll));
}
void M2(int u, int v) {memset(g, 0, (sz[u] + sz[v] + 3) * sizeof (ll));for (int i = 1; i <= sz[v]; i++) s[i] = (s[i - 1] + f[v][i]) % P;for (int i = 1; i <= sz[u]; i++)for (int k = 0; k < sz[v]; k++)(g[i + k] += C(i - 1 + k, i - 1) * C(sz[u] - i + sz[v] - k, sz[u] - i) % P * f[u][i] % P * (s[sz[v]] + P - s[k])) %= P;memcpy(f[u], g, (sz[u] + sz[v] + 3) * sizeof (ll));
}
void DFS(int u, int ff) {sz[u] = 1;f[u][1] = 1;for (auto [v, w] : e[u]) {if (v == ff) continue;DFS(v, u);if (w == 0) M1(u, v);else M2(u, v);sz[u] += sz[v];}
}
int main() {Init();scanf("%d", &n);for (int i = 1, u, v; i < n; i++) {char op;scanf("%d %c", &u, &op);v = i + 1;e[u].pb(v, op == '<');e[v].pb(u, op != '<');}DFS(1, 0);int ans = 0;for (int i = 1; i <= n; i++) (ans += f[1][i]) %= P;printf("%d\n", ans);return 0;
}