P12445 [COTS 2025] 数好图 Promet

题目描述

给定正整数 $N$ 和素数 $P$ 。

$\forall K = 0, 1, \dots, N$ ，求出满足以下条件的简单有向图的数量：

图中仅包含 $i \to j$ （ $1 \leq i < j \leq N$ ）的边；
满足以下条件的点 $u$ 恰好有 $K$ 个：
- 存在 $1 \to u$ 和 $u \to N$ 的路径。

只需要输出答案对 $P$ 取模后的结果。

输入格式

$N$ $P$

输出格式

输出一行 $(N + 1)$ 个非负整数，第 $i$ 个数表示 $K = i - 1$ 时的答案。

输入输出样例 #1

输入 #1

1	`2 1000000007`

输出 #1

1 0 1

输入输出样例 #2

输入 #2

1	`3 1000000007`

输出 #2

3 0 3 2

输入输出样例 #3

输入 #3

1	`5 1000000007`

输出 #3

1	`183 0 183 286 250 122`

说明/提示

样例解释

样例 $2$ 解释：

$K = 0$ 的时候，根据定义，下面三个边集合法：

$\emptyset$ ；
${(1, 2)}$ ；
${(2, 3)}$ 。

$K = 2$ 时，合法的边集：

${(1, 3)}$ ；
${(1, 3), (1, 2)}$ ；
${(1, 3), (2, 3)}$ 。

$K = 3$ 时，合法的边集：

${(1, 2), (2, 3)}$ ；
${(1, 2), (1, 3), (2, 3)}$ 。

数据范围

$2 \leq N \leq 2 000$ ；
$10^{8} \leq P \leq 10^{9} + 100$ ；
$P$ 是素数。

子任务

子任务 $0$ 为样例。

子任务编号	$N \leq$	得分
$1$	$7$	$4$
$2$	$18$	$7$
$3$	$50$	$23$
$4$	$100$	$13$
$5$	$300$	$18$
$6$	$2 000$	$35$

题解

先考虑 $k = n$ 的情况。这两个定理是显然的：

所有点都能到 $n$ ，当且仅当 $1$ 到 $n - 1$ 每个点出度不为 0；
$1$ 能到达所有点，当且仅当 $2$ 到 $n$ 每个点入度不为 0。

那么直接施加容斥。用 $f (i, j)$ 表示，后 $i$ 个点中有 $j$ 个点被钦定了入度为 $0$ 的方案数（特别的，倒数第 $i$ 个点此时不能被钦定，只能在转移的时候被钦定。即， $j < i$ ）。这个可以 $O (n^{2})$ 做。

在 $O (n^{2})$ 复杂度内，我们还可以算出 $t$ 个点构成的、满足所有点都在 $1$ 到 $t$ 路径上的 DAG 数量，设为 $g (t)$ 。

对于 $k < n$ 的情况，考虑在 $g (k)$ 的基础上增加点，使得仍然只有这 $k$ 个点满足要求。

将点划分为 3 类：

1 类点，表示在 $1$ 到 $n$ 的路径上（即在我们钦定的 $k$ 个点之中）；
2 类点，表示能从 $1$ 到达的、但不是 1 类点的点；
3 类点，表示不能从 $1$ 到达的点。

记 $o p_{i}$ 表示第 $i$ 个点的类型，显然 $o p_{1} = o p_{n} = 1$ 。我们还需要在 $o p$ 中分配 $k - 2$ 个 $1$ ，以及若干个 $2$ 和 $3$ 。对于每一种分配方式，我们计算所有额外边（不是 1 类和 1 类的连边）的连接方式，乘上 $g (k)$ ，加到 $a n s_{k}$ 中。

对于每个点 $u$ ，我们找到合适的 $v < u$ 并连边：

1 类点：找到编号比它小的 3 类点 $v$ 连边 $v \to u$ ；
2 类点：找到编号比它小的 1、2、3 类点 $v$ 连边 $v \to u$ ，有至少一个这样的 1 或 2 类点 $v$ 连边；
3 类点：找到编号比它小的 3 类点 $v$ 连边 $v \to u$ ；

发现什么？3 类点可以往其后面所有点连边。所以假设所有的 3 类点在 $p_{1}, p_{2}, \dots, p_{z}$ 处，可以产生的贡献为 $2^{\sum_{i = 1}^{z} (n - p_{i})}$ 。

因此我们可以 DP 求出所有的贡献之和，然后将 3 类点删掉，只考虑 1、2 类点之间的贡献。这也可以 $O (n^{2})$ 暴力。

整体时间复杂度为 $O (n^{2})$ ，足以通过本题。