Leaping Tak

题目描述

有 $N$ 个单元格排成一行，从左到右编号为 $1, 2, \ldots, N$。 Tak 住在这些单元格中，目前在单元格 $1$。他试图按下面描述的过程到达单元格 $N$。 给定一个整数 $K$，且 $K \le 10$，以及 $K$ 个不相交的区间 $[L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]$。 记 $S$ 为这 $K$ 个区间的并集。 这里，区间 $[l, r]$ 表示满足 $l \leq i \leq r$ 的所有整数 $i$ 的集合。

当你在单元格 $i$ 时，从 $S$ 中选择一个整数 $d$ 并移动到单元格 $i + d$。你不能移出这些单元格。

为帮助 Tak，找出到达单元格 $N$ 的方法数，对 $998244353$ 取模。

输入格式

从标准输入读取数据，格式如下： $N$ $K$ $L_1$ $R_1$ $L_2$ $R_2$ $:$ $L_K$ $R_K$

输出格式

输出 Tak 从单元格 $1$ 到单元格 $N$ 的方法数，对 $998244353$ 取模。

5 2
1 1
3 4

4

5 2
3 3
5 5

0

5 1
1 2

5

60 3
5 8
1 3
10 15

221823067

提示

$2 \leq N \leq 2 \times 10^5$ $1 \leq K \leq \min(N, 10)$ $1 \leq L_i \leq R_i \leq N$ $[L_i, R_i]$ 和 $[L_j, R_j]$ 不相交（$i \neq j$） 输入中的所有数值均为整数。集合 $S$ 是区间 $[1,1]$ 与区间 $[3,4]$ 的并集，因此 $S = \{ 1, 3, 4 \}$。 到达单元格 $5$ 有 $4$ 种可能的方式：

$1 \to 2 \to 3 \to 4 \to 5$， $1 \to 2 \to 5$， $1 \to 4 \to 5$ 和 $1 \to 5$。
因为 $S = \{ 3, 5 \}$，所以你无法到达单元格 $5$。 输出 $0$.
注意需要对 $998244353$ 取模后输出答案。

标签: AtCoder|abc179D

来源

AtCoder|abc179D