题目描述
给定正整数 $N$ 和素数 $P$。
$\forall K=0,1,\ldots,N$，求出满足以下条件的简单有向图的数量：
- 图中仅包含 $i\to j$（$1\le i\lt j\le N$）的边；
- 满足以下条件的点 $u$ 恰好有 $K$ 个：
- 存在 $1\to u$ 和 $u\to N$ 的路径。
只需要输出答案对 $P$ 取模后的结果。
输入格式
$N$ $P$
输出格式
输出一行 $(N+1)$ 个非负整数，第 $i$ 个数表示 $K=i-1$ 时的答案。
输入输出样例 #1
输入 #1
1 | |
输出 #1
1 | |
输入输出样例 #2
输入 #2
1 | |
输出 #2
1 | |
输入输出样例 #3
输入 #3
1 | |
输出 #3
1 | |
说明/提示
样例解释
样例 $2$ 解释：
$K=0$ 的时候，根据定义，下面三个边集合法：
- $\varnothing$；
- ${(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\le N\le 2,000$；
- $10^8\le P\le 10^9+100$；
- $P$ 是素数。
子任务
子任务 $0$ 为样例。
| 子任务编号 | $N\le$ | 得分 |
|---|---|---|
| $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$ 到达的点。
记 $op_i$ 表示第 $i$ 个点的类型，显然 $op_1 = op_n = 1$。我们还需要在 $op$ 中分配 $k-2$ 个 $1$，以及若干个 $2$ 和 $3$。对于每一种分配方式，我们计算所有额外边（不是 1 类和 1 类的连边）的连接方式，乘上 $g(k)$，加到 $ans_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)$，足以通过本题。
