Teleporting Takahashi 2

题目描述

有一个由 $N$ 个顶点和 $N+M$ 条有向边构成的简单有向图 $G$。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $N+M$。 边 $i$ $(1 \leq i \leq N)$ 是从顶点 $i$ 指向顶点 $i+1$。（这里，将顶点 $N+1$ 视为顶点 $1$。）
边 $N+i$ $(1 \leq i \leq M)$ 是从顶点 $X_i$ 指向顶点 $Y_i$。
Takahashi 在顶点 $1$。在每个顶点处，他可以移动到从当前顶点出发有一条出边指向的任意顶点。 计算他恰好移动 $K$ 次的方案数。 也就是说，求满足以下三个条件的整数序列 $(v_0, v_1, \dots, v_K)$（长度为 $K+1$）的数量：

$1 \leq v_i \leq N$ 对于 $i = 0, 1, \dots, K$。 $v_0 = 1$。 对于 $i = 1, 2, \ldots, K$，存在一条从顶点 $v_{i-1}$ 到顶点 $v_i$ 的有向边。

由于该数量可能非常大，请对 $998244353$ 取模后输出。

输入格式

输入按下列格式由标准输入提供： $N$ $M$ $K$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_M$ $Y_M$

输出格式

输出对 $998244353$ 取模后的方案数。

6 2 5
1 4
2 5

5

10 0 200000

1

199 10 1326
122 39
142 49
164 119
197 127
188 145
69 80
6 120
24 160
18 154
185 27

451022766

提示

$2 \leq N \leq 2 \times 10^5$ $0 \leq M \leq 50$ $1 \leq K \leq 2 \times 10^5$ $1 \leq X_i, Y_i \leq N$, $X_i \neq Y_i$ 所有 $N+M$ 条有向边两两不同。 所有输入值均为整数。 上图表示图 $G$。Takahashi 有五种移动方式：

顶点 $1 \to$ 顶点 $2 \to$ 顶点 $3 \to$ 顶点 $4 \to$ 顶点 $5 \to$ 顶点 $6$ 顶点 $1 \to$ 顶点 $2 \to$ 顶点 $5 \to$ 顶点 $6 \to$ 顶点 $1 \to$ 顶点 $2$ 顶点 $1 \to$ 顶点 $2 \to$ 顶点 $5 \to$ 顶点 $6 \to$ 顶点 $1 \to$ 顶点 $4$ 顶点 $1 \to$ 顶点 $4 \to$ 顶点 $5 \to$ 顶点 $6 \to$ 顶点 $1 \to$ 顶点 $2$ 顶点 $1 \to$ 顶点 $4 \to$ 顶点 $5 \to$ 顶点 $6 \to$ 顶点 $1 \to$ 顶点 $4$

标签: AtCoder|abc372F

来源

AtCoder|abc372F