uoj961

uoj961

形式化题意：求计算满足以下两个条件的 $n$ 个标记顶点的有向图的数量：

1. 图必须是 DAG。
2. 不存在三个站点 $(a, b, c)$，使得 $a$ 无法到达 $b$，$b$ 无法到达 $c$，且 $c$ 无法到达 $a$。

在偏序集理论中，第二个条件等价于要求该偏序集的宽度不超过 $2$，并且它是一个弱序。

具体来说，满足条件的图的结构可以描述为：顶点被划分为若干个有序的层级 $L_1, L_2, \dots, L_k$。

• 对于任意 $u \in L_i, v \in L_j$，如果 $i < j$，则 $u$ 可以到达 $v$。
• 同一层级 $L_i$ 内的顶点之间互不可达。
• 为了不违背第二个条件，每个层级的大小 $|L_i|$ 只能是 $1$ 或 $2$。

考虑 dp，我们需要构建一个有 $n$ 个顶点的图，可以看作是在 $n-s$ 个顶点的合法图上，新增一个大小为 $s$ ($s \in \{1, 2\}$) 的顶层。

• 为了保证连通性，新层级 $L_{new}$ 与紧邻的上一层级 $L_{prev}$ 之间必须全连接（即 $L_{prev}$ 中的每个点到 $L_{new}$ 中的每个点都要有边，或者通过传递性可达，但在 DAG 构造中通常意味着所有 $u \in L_{prev}, v \in L_{new}$ 的边在传递归约中存在）。
• 新层级 $L_{new}$ 可以接收来自更早层级（$L_{1} \dots L_{prev-1}$）的任意数量的边。这些边是“选的，因为即使没有直接连边，也可以通过 $L_{prev}$ 间接到达。

定义 $dp[i][s]$ 为由 $i$ 个顶点组成，且最后一层大小为 $s$ 的好图的数量。其中 $s \in \{1, 2\}$。

假设我们要计算 $dp[i][s]$，我们枚举上一层的大小 $prev\_s \in \{1, 2\}$。

• 当 $s=1$ 时（$M = i - 1 - prev\_s$）:$$dp[i][1] = \binom{i}{1} \times \left( dp[i-1][1] \cdot 2^{(i-2) \times 1} + dp[i-1][2] \cdot 2^{(i-3) \times 1} \right)$$
• 当 $s=2$ 时（$M = i - 2 - prev\_s$）:$$dp[i][2] = \binom{i}{2} \times \left( dp[i-2][1] \cdot 2^{(i-3) \times 2} + dp[i-2][2] \cdot 2^{(i-4) \times 2} \right)$$ 即：$$dp[i][2] = \binom{i}{2} \times \left( dp[i-2][1] \cdot 2^{2i-6} + dp[i-2][2] \cdot 2^{2i-8} \right)$$

答案即为 $(dp[n][1] + dp[n][2]) \pmod P$。