AT_abc179_d [ABC179D] Leaping Tak

题目描述

有一个由 $N$ 个格子组成的格子列，这些格子从左到右依次编号为 $1, 2, \ldots, N$。

住在这个格子上的高桥君现在在第 $1$ 个格子，他想通过下面描述的方法不断移动，最终到达第 $N$ 个格子。

给定一个不超过 $10$ 的整数 $K$，以及 $K$ 个互不相交的区间 $[L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]$，这些区间的并集记为 $S$。其中，区间 $[l, r]$ 表示所有满足 $l \leq x \leq r$ 的整数 $x$ 的集合。

• 当高桥君在第 $i$ 个格子时，他可以从 $S$ 中任选一个整数 $d$，然后移动到第 $i+d$ 个格子。但不能移动到格子列之外。

请你帮高桥君计算，从第 $1$ 个格子到达第 $N$ 个格子的方案数，答案对 $998244353$ 取模。

输入格式

输入按以下格式从标准输入读入。

$N$ $K$ $L_1$ $R_1$ $L_2$ $R_2$ $\ldots$ $L_K$ $R_K$

输出格式

输出高桥君从第 $1$ 个格子到第 $N$ 个格子的方案数，对 $998244353$ 取模。

样例 1

输入

5 2
1 1
3 4

输出

4

样例 2

输入

5 2
3 3
5 5

输出

0

样例 3

输入

5 1
1 2

输出

5

样例 4

输入

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$）
• 所有输入均为整数

样例解释 1

集合 $S$ 是区间 $[1, 1]$ 和区间 $[3, 4]$ 的并集，即 $S = \{1, 3, 4\}$。到达第 $5$ 个格子的方案有如下 $4$ 种：

• 按顺序移动到第 $1, 2, 3, 4, 5$ 个格子。
• 按顺序移动到第 $1, 2, 5$ 个格子。
• 按顺序移动到第 $1, 4, 5$ 个格子。
• 按顺序移动到第 $1, 5$ 个格子。

样例解释 2

$S = \{3, 5\}$，无法到达第 $5$ 个格子，所以输出 $0$。

样例解释 4

请注意，答案需要对 $998244353$ 取模。

由 ChatGPT 4.1 翻译