QOJ #8047. DFS Order 4 题解

Description

小青鱼（Little Cyan Fish），又名青羽小（Qingyu Xiao），非常喜欢 DFS 序的概念。今天，他手中有一棵有 $n$ 个节点的有根树 $T$，节点编号从 $1$ 到 $n$。这棵树的根是节点 $1$，而对于每个节点 $i$（$2 \le i \le n$），其父节点为 $f_i$，满足 $1 \le f_i < i$。

一个 DFS 序列 $D = (D_1, D_2, \ldots, D_n)$ 表示对树进行深度优先遍历时访问节点的顺序。$D$ 中第 $j$ 项表示该节点是 DFS 过程中第 $j$ 个被访问的节点。

在深度优先搜索过程中，如果某个节点有多个子节点，则按节点编号的升序遍历它们。因此，对于每一棵有根树，DFS 序是唯一确定的。

下面是用于生成 DFS 序列的伪代码，其中树 $T$ 由数组 $f = \{f_2, f_3, \ldots, f_n\}$ 唯一表示：

---

算法 1：深度优先搜索的实现

1: procedure dfs(vertex x)
2:     Append x to the end of dfs_order
3:     for each child y of x do  // 子节点按索引升序遍历
4:         dfs(y)
5:     end for
6: end procedure

7: procedure generate()
8:     Let dfs_order be a global variable
9:     dfs_order ← empty list
10:    dfs(1)
11:    return dfs_order
12: end procedure

---

令 $D$ 为 generate() 返回的数组。

由于每棵合法的树对应一个合法的 $f$ 数组，而 $f$ 的合法取值有 $(n - 1)!$ 种（因为每个 $f_i$ 可以从 $1$ 到 $i - 1$ 中任选一个），所以总共有 $(n - 1)!$ 棵不同的树。

现在，小青鱼想知道：对于所有 $(n - 1)!$ 种可能的 $f$ 配置，最终能生成多少种不同的 DFS 序列 $D$？我们认为两个 DFS 序列 $D$ 和 $D'$ 不同，当且仅当存在某个 $1 \le i \le n$，使得 $D_i \ne D'_i$。

由于这个数可能非常大，你的任务是计算该数对一个给定素数 $P$ 取模的结果。

$n\leq 800$。

Solution

考虑怎么判断一个序列 $a$ 合法。

从前往后扫序列，维护当前扫到的 $a_i$ 的父链 $anc_1,anc_2,\ldots,anc_k$。加入一个数，就是选择 $anc_{j}<x$ 的最大的 $j$，并把 $x$ 的父亲设为 $anc_{j-1}$。

那么这么建出来的树一定满足下面的条件：对于每个点 $x$，把 $x$ 的儿子从小到大拿出来，设为 $u_1,u_2,\ldots,u_m$，同时设 $v_i$ 为 $u_i$ 最大的儿子，如果没有即为 $0$。然后需要满足 $\forall 2\leq i\leq m,u_i<v_{i-1}$。

---

考虑把满足条件的树的形态拿出来并对这样的树的拓扑序计数。

而这种树的拓扑图为 $x\to u_1,u_i\to u_{i+1},u_{i+1}\to v_i$，是个普通的 DAG，不是很好计数。

注意到如果没有 $u_{i+1}\to v_i$，整张图就是个外向树了。

所以考虑把这些边做容斥，即把 $[u_{i+1}<v_i]$ 变为 $1-[v_i<u_{i+1}]$，这等价于选择一些 $u_{i+1}\to v_i$ 的边删掉，剩下的进行反向，变为 $v_i\to u_{i+1}$。

如果 $u_i<v_i<u_{i+1}$，则可以把 $u_i\to u_{i+1}$ 删掉，剩下的图就是外向树了。

显然一个外向树的 DAG 数为 $\displaystyle n!\cdot\prod\frac{1}{sz_i}$。

---

求方案有个直观的想法是设 $f_{i}$ 表示 $i$ 个点的答案，转移时枚举根最左边的子树的大小。

如果 $u_1$ 的边为 $u_1\to u_{2}$ 则可以转移，但是如果 $u_1$ 的边为 $v_1\to u_2$，则 $u_1$ 所有儿子的子树大小都会变，这就不能转移了。

所以需要加一维 $j$，即 $f_{i,j}$ 表示大小为 $i$ 的子树，往根最右边加一个大小为 $j$ 的子树 $u_{m+1}$，同时要求 $u_{m}$ 连的是 $u_m\to u_{m+1}$ 的答案。

转移时同样枚举最左边的子树大小即可。转移方程：

$$f_{i,j}=\sum_{k=1}^{i-1}{f_{i-k,j}\times\frac{i-k+j}{i+j}\times f_{k,0}\times\frac{k}{i-1+j}}-\sum_{k=1}^{\color{red}{i-2}}{f_{i-k,j}\times\frac{i-k+j}{i+j}\times f_{k,i-1-k+j}}$$

注意：这里如果 $u_1$ 连的是 $v_1\to u_2$，则需要满足根至少有 $2$ 个儿子，即 $k<i-1$，否则就连向那个凭空加入的子树了，这与状态矛盾。

时间复杂度：$O(n^3)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 805;

int n, mod;
int inv[kMaxN], f[kMaxN][kMaxN];

int qpow(int bs, int64_t idx = mod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (int64_t)bs * bs % mod)
    if (idx & 1)
      ret = (int64_t)ret * bs % mod;
  return ret;
}

inline int add(int x, int y) { return (x + y >= mod ? x + y - mod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + mod); }
inline void inc(int &x, int y) { (x += y) >= mod ? x -= mod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += mod : x; }

void prework() {
  for (int i = 1; i <= n; ++i) inv[i] = qpow(i);
}
  
void dickdreamer() {
  std::cin >> n >> mod;
  prework();
  for (int i = 0; i <= n; ++i) f[0][i] = 1;
  for (int i = 0; i <= n - 1; ++i) f[1][i] = inv[i + 1];
  for (int i = 2; i <= n; ++i) {
    for (int j = 0; j <= n - i; ++j) {
      for (int k = 1; k <= i - 1; ++k) {
        inc(f[i][j], 1ll * f[i - k][j] * (i - k + j) % mod * inv[i + j] % mod * f[k][0] % mod * k % mod * inv[i - 1 + j] % mod);
        if (k < i - 1)
          dec(f[i][j], 1ll * f[i - k][j] * (i - k + j) % mod * inv[i + j] % mod * f[k][i - 1 - k + j] % mod);
      }
    }
  }
  int ans = f[n][0];
  for (int i = 1; i <= n; ++i) ans = 1ll * ans * i % mod;
  std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}