P12445 [COTS 2025] 数好图 / Promet
题目描述
给定正整数 $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$ 取模后的结果。
输入格式
无
输出格式
无
说明/提示
### 样例解释
样例 $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$ |