P11595 [NOISG 2018 Finals] Journey

译自 [NOISG 2018 Finals B. Journey](https://github.com/noisg/sg_noi_archive/tree/master/2018/tasks/journey)。

Kuno 要从 A 市到 B 市旅行，但在路途中他可能会停下来休息。 允许他停留的共有 $N$ 个城市，编号为 $0$ 到 $N-1$，其中 $0$ 号城市表示 A 市，$N-1$ 号城市表示 B 市，编号越大的城市距离 B 市越近。 为了让旅行保持一定的效率，中途停留需要满足以下限制： - 第 $i$ 次停留的城市必须比第 $i-1$ 次离 B 市**严格**更近。特别地，我们认为第 $0$ 次停留的城市是 A 市。 - 从 A 市出发，直到从 B 市结束停留离开，整个过程不能超过 $M$ 天。换句话说，我们不允许你在 A 市停留，但允许你在 B 市停留。 Kuno 在城市之间的移动和停留基于城市之间的航线和城市中的酒店系统。每个城市 $i$ 都存在 $H$ 条用 $(j,k)$ 表示的航线，表示你可以通过这条航线从城市 $i$ 前往城市 $j$，但是一旦使用这条航线，就必须在城市 $j$ 中停留不少于 $k$ 天。**特别地，每个城市都有一条直接前往 B 市的航线**。 注意可能存在完全相同或起点终点相同的航线，此时你需要把它们视为**不同航线**。你应当忽略远离 B 市的航线。 在飞机中度过的时间忽略不计。 到达一个城市即算作在该城市停留，即使停留了 $0$ 天。 你的任务是，对每一个 $d\in[1,m]$，帮助 Kuno 计数他从 A 市出发到从 B 市结束停留返回花费 $d$ 天的方案数。特别地，若方案数超过 $5\times 10^8$，你只需输出 $5\times 10^8+1$。 两个旅行方案不同当且仅当以下三条任意一条成立： 1. 一个旅行方案中需要在城市 $i$ 停留，而另一个不用。 2. 存在一个城市 $i$，使得两个旅行方案离开该城市的时间不同。**特别地，也包括从 B 市离开的时间不同**。 3. 两个行程都从城市 $i$ 到城市 $j$，但使用的航线不同。 例如，对于两个均为 A 市到 C 市，再从 C 市到 D 市，最后从 D 市到 B 市的旅行方案，如果一个是在第二天离开 C 市，另一个是在第三天离开 C 市，那么它们就是不同的方案。此外，如果输入中存在两条同样从 D 市前往 B 市的航线，即便出发时间和到达时间相同，也是不同的方案。 如你仍无法完全理解题意，请阅读**样例解释**。

第一行包含三个整数 $N,M,H$，表示城市数量，旅行天数上限，和每个城市的航线数量。 接下来的输入包含 $N-1$ 行，第 $i$ 行包含 $2H$ 个用空格分割的整数，每两个为一组 $(j,k)$，描述从城市 $i-1$ 出发的 $H$ 条航线。

输出 $m$ 个用空格隔开的整数，依次表示从 A 市出发直至从 B 市结束停留离开共花费恰好 $1,2,3,\cdots ,m$ 天的旅行方案数。注意如果方案数超过 $5\times 10^8$，则应输出 $5\times 10^8+1$。

### 样例 #1 解释 样例 #1 输入描述了一个具有 $4$ 座城市，每个城市有 $3$ 条不同的航线出发的情况： | 出发城市 | 航线 $1$ 终点 | $\text{Min.}$ | 航线 $2$ 终点 | $\text{Min.}$ | 航线 $3$ 终点 | $\text{Min.}$ | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | A 市 | 城市 $1$ | $2$ 天 | 城市 $2$ | $2$ 天 | B 市 | $0$ 天 | | 城市 $1$ | 城市 $2$ | $2$ 天 | 城市 $2$ | $3$ 天 | B 市 | $0$ 天 | | 城市 $2$ | B 市 | $1$ 天 | B 市 | $3$ 天 | B 市 | $0$ 天 | 为了方便表格描述，我们用 $\text{Min.}$ 表示了每条航线对目的地最少停留天数的要求。 所有 $1$ 天的旅行方案如下； | 旅行方案 | 方案 | | :----------: | :----------: | | $1$ | 在第 $1$ 天从 A 市通过航线 $3$ 抵达 B 市，在 B 市停留 $0$ 天。 | 所有 $2$ 天的旅行方案如下： | 旅行方案 | 方案 | | :----------: | :----------: | | $1$ | 在第 $1$ 天从 A 市通过航线 $3$ 抵达 B 市，在 B 市停留 $1$ 天。 | 所有 $3$ 天的旅行方案如下： | 旅行方案 | 方案 | | :----------: | :----------: | | $1$ | 在第 $1$ 天从 A 市通过航线 $1$ 抵达城市 $1$，在城市 $1$ 停留 $2$ 天；在第 $3$ 天从城市 $1$ 通过航线 $3$ 抵达 B 市，在 B 市停留 $0$ 天。 | | $2$ | 在第 $1$ 天从 A 市通过航线 $2$ 抵达城市 $2$，在城市 $2$ 停留 $2$ 天；在第 $3$ 天从城市 $2$ 通过航线 $3$ 抵达 B 市，在 B 市停留 $0$ 天。 | | $3$ | 在第 $1$ 天从 A 市通过航线 $3$ 抵达 B 市，在 B 市停留 $2$ 天。 | 所有 $4$ 天的旅行方案如下： | 旅行方案 | 方案 | | :----------: | :----------: | | $1$ | 在第 $1$ 天从 A 市通过航线 $1$ 抵达城市 $1$，在城市 $1$ 停留 $2$ 天；在第 $3$ 天从城市 $1$ 通过航线 $3$ 抵达 B 市，在 B 市停留 $1$ 天。 | | $2$ | 在第 $1$ 天从 A 市通过航线 $1$ 抵达城市 $1$，在城市 $1$ 停留 $3$ 天；在第 $4$ 天从城市 $1$ 通过航线 $3$ 抵达 B 市，在 B 市停留 $0$ 天。 | | $3$ | 在第 $1$ 天从 A 市通过航线 $2$ 抵达城市 $2$，在城市 $2$ 停留 $2$ 天；在第 $3$ 天从城市 $2$ 通过航线 $3$ 抵达 B 市，在 B 市停留 $1$ 天。 | | $4$ | 在第 $1$ 天从 A 市通过航线 $2$ 抵达城市 $2$，在城市 $2$ 停留 $3$ 天；在第 $4$ 天从城市 $2$ 通过航线 $3$ 抵达 B 市，在 B 市停留 $0$ 天。 | | $5$ | 在第 $1$ 天从 A 市通过航线 $2$ 抵达城市 $2$，在城市 $2$ 停留 $2$ 天；在第 $3$ 天从城市 $2$ 通过航线 $1$ 抵达 B 市，在 B 市停留 $1$ 天。 | | $6$ | 在第 $1$ 天从 A 市通过航线 $3$ 抵达 B 市，在 B 市停留 $3$ 天。 | ### 样例 #2 解释 这组样例中除 A 市外所有城市的出发航线均直接到达 B 市。它满足子任务 $1,3,4$。 ### 样例 #3 解释 这组样例中所有的航线均不限制目的地最少停留天数。它满足子任务 $2,3,4$。 ### 样例 #4 解释 注意若方案数超过 $5\times 10^8$，你只需输出 $5\times 10^8+1$。它满足子任务 $2,3,4$。 ### 子任务 对于 $100\%$ 的数据，$N\le 10^4,M\le 400,H\le 100$，其余输入均在此范围下合法。 | 子任务 | 得分 | 数据范围及特殊性质 | | :----------: | :----------: | :----------: | | $1$ | $20$ | 除 A 市外所有城市的出发航线均直接到达 B 市，$N,M,H\le 10$ | | $2$ | $23$ | 所有的航线均不限制目的地最少停留天数，$N,M,H\le 20$ | | $3$ | $26$ | $N,M,H\le 100$ | | $4$ | $31$ | 无特殊限制 |