题解：P14016 [ICPC 2024 Nanjing R] 拓扑

题意

给定一棵 \(n\) 个点的树。对于每个 \(1\leq i\leq n\)，求出有多少这棵树的拓扑序 \(p\) 使得 \(p_i=i\)。\(n\leq 5\times 10^3\)。

题解

考虑暴力枚举 \(u\) 计算答案。注意到我们只限制了 \(p_u=u\)，所以我们并不关心 \(sub_u\) 内的点的排列方法。据此设计 DP：令 \(f_{u,i}\) 表示不考虑 \(sub_u\) 内的点，剩下的 \(n-sz_u+1\) 个点构成的相对拓扑序中，\(p_i=u\) 的方案数。

转移时枚举 \(v\in son_u\)，考虑如何从 \(f_{u,i}\) 向 \(f_{v,j}\) 转移，相当于要把 \(u\) 的所有不为 \(v\) 的儿子节点 \(s\) 的子树拼上去。考虑这些儿子节点 \(s\) 有什么限制，显然要求 \(s\) 在 \(p\) 中的出现位置要在 \(u\) 之后。\(f_{u,i}\) 对应的 \(n-sz_u+1\) 个点中，有 \(n-sz_u+1-i\) 个点出现在 \(u\) 之后，我们要把这些点和拼上来的 \(sz_u-sz_v-1\) 个点放在一起重排，这里会乘上一个组合数，然后还需要乘上这 \(sz_u-sz_v-1\) 个点内部拓扑排序的方案数。可以列出转移式：

\[f_{v,j}=\sum_{i=1}^{j-1}f_{u,i}\times\binom{n-sz_v-i}{sz_u-sz_v-1}\times \frac{(sz_u-sz_v-1)!}{\displaystyle\prod_{x\in sub_u-sub_v}sz_x} \]

容易注意到转移式与 \(j\) 无关，直接求一遍前缀和即可单次 \(\mathcal{O}(n)\) 转移。这样就得到了 \(\mathcal{O}(n^2)\) 的 DP。注意还要预处理一下子树内 \(sz\) 的乘积及其逆元。

考虑如何统计答案。和转移比较类似，考虑 \(f_{u,u}\) 的 \(n-sz_u+1\) 个点中，有 \(n-sz_u+1-u\) 个点在拓扑序中出现在 \(u\) 之后，要把这些点和 \(u\) 子树内的 \(sz_u-1\) 个点拼在一起，再乘上 \(u\) 子树内的点的拓扑序方案数。可以得到点 \(u\) 的答案即为：

\[f_{u,u}\times \binom{n-u}{sz_u-1}\times \frac{sz_u!}{\displaystyle\prod_{v\in sub_u}sz_v} \]

整体时间复杂度为 \(\mathcal{O}(n^2)\)。

代码

#include <bits/stdc++.h>using namespace std;using ll = long long;
using i128 = __int128;
using ui = unsigned int;
using ull = unsigned long long;
using u128 = unsigned __int128;
using ld = long double;
using pii = pair<int, int>;
const int N = 5e3 + 5;
const int mod = 998244353;template<typename T> inline T lowbit(T x) { return x & -x; }
template<typename T> inline void chk_min(T &x, T y) { if (y < x) x = y; }
template<typename T> inline void chk_max(T &x, T y) { if (x < y) x = y; }
template<typename T> inline T add(T x, T y) { return (x += y) >= mod ? x - mod : x; }
template<typename T> inline T sub(T x, T y) { return (x -= y) < 0 ? x + mod : x; }
template<typename T> inline void cadd(T &x, T y) { (x += y) >= mod ? (x -= mod) : x; }
template<typename T> inline void csub(T &x, T y) { (x -= y) < 0 ? (x += mod) : x; }int n, fa[N], f[N][N], pre[N];
int sz[N], mul[N], imul[N];
int fac[N], ifac[N], inv[N];
vector<int> T[N];int qpow(int a, int b) {int res = 1;for (; b; b >>= 1) {if (b & 1) res = (ll)res * a % mod;a = (ll)a * a % mod;}return res;
}void init(int n) {fac[0] = 1;for (int i = 1; i <= n; ++i) fac[i] = (ll)fac[i - 1] * i % mod;ifac[n] = qpow(fac[n], mod - 2);for (int i = n - 1; ~i; --i) ifac[i] = (ll)ifac[i + 1] * (i + 1) % mod;inv[1] = 1;for (int i = 2; i <= n; ++i) inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
}int C(int n, int m) {if (n < 0 || m < 0 || n < m) return 0;else return (ll)fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}void dfs1(int x, int fx) {sz[x] = mul[x] = imul[x] = 1;for (int y : T[x]) if (y != fx) {dfs1(y, x);sz[x] += sz[y];mul[x] = (ll)mul[x] * mul[y] % mod;imul[x] = (ll)imul[x] * imul[y] % mod;}mul[x] = (ll)mul[x] * sz[x] % mod;imul[x] = (ll)imul[x] * inv[sz[x]] % mod;
}
void dfs2(int x, int fx) {for (int y : T[x]) if (y != fx) {int p = (ll)imul[x] * sz[x] % mod * inv[sz[x] - sz[y]] % mod * mul[y] % mod * fac[sz[x] - sz[y]] % mod;for (int i = 1; i <= n; ++i) {int q = (ll)C(n - sz[y] - i, sz[x] - sz[y] - 1) * p % mod;pre[i] = add<int>(pre[i - 1], (ll)f[x][i] * q % mod);}for (int j = 1; j <= n; ++j) f[y][j] = pre[j - 1];dfs2(y, x);}
}int main() {ios::sync_with_stdio(0), cin.tie(0);cin >> n;for (int i = 2; i <= n; ++i) cin >> fa[i], T[fa[i]].emplace_back(i);init(n);f[1][1] = 1, dfs1(1, 0), dfs2(1, 0);for (int u = 1; u <= n; ++u)cout << (ll)f[u][u] % mod * C(n - u, sz[u] - 1) % mod * fac[sz[u]] % mod * imul[u] % mod << ' ';return 0;
}