题目详情
返回题库题目描述
你是一只毛毛虫,想要飞离地球前往空间站。
空间站位于距离地球n千米的位置,在1~n-1的每整数千米位置都有一个休息站。 你最开始在地球上,距离地球0千米。 为了飞到空间站,你准备了m种火箭,其中第i号火箭能够前进Lᵢ~Rᵢ千米。 为了顺利到达空间站,有如下的限制条件:
1、每种火箭可以重复使用,且没有使用顺序的限制。
2、每次前进后,如果无法到达空间站,你需要到达距离地球整数千米的位置的休息站,在休息站修整后重新使用某种火箭,直到到达空间站。
3.、宇宙很大,一旦和地球的距离超出了n千米就会失联,迷失在宇宙中,因此要避免这种情况。
出发前,你想算算顺利到达空间站有几种方案,因为方案数可能很多,你只需要输出方案数对 998244353取模的结果。 前进次数不同或前进次数相同但是存在某一步前进距离不同,则认为两个方案不同。
输入描述
第一行两个空格隔开的正整数n和m。
接下来m行,第i+1行两个空格隔开的正整数$L_i , R_i$描述第i个火箭的能力。
对于所有数据,$1 \leq n \leq 10^5$ , $ 1 \leq m \leq 200 $ , $ 1 \leq L_i \leq R_i \leq n $ 。 每个测试点的具体限制见下表:
| 测试点编号 | 约束 |
|---|---|
| 1-3 | $m=1,L_{1}=R_{1}$ |
| 4-5 | $L_{i}=R_{i}$ |
| 6-9 | $1\le n\le1000$ |
| 10-13 | 对于任意$1\le i<m$保证$R_{i}<L_{i+1}$ |
| 14-20 | 没有其他限制 |
输出描述
输出一行一个非负整数表示方案数对998244353取模的结果。
提示
【样例解释1】
第一个火箭可以让你前进1、2或3千米,第二个火箭可以让你前进2千米。到达1千米位置的休息站的方案只有一个,就是从地球前进1千米。 到达2千米位置的休息站的方案有两个,一个是前进2千米,一个是前进1千米再前进1千米。 到达3千米的空间站的方案有四个,分别是前进3、前进2再前进1、前进1前进2、前进1前进1再前进1。询问你到达3千米的空间站的方案数,所以输出4。
【样例解释2】
只有一种火箭,可以让你前进3或4千米。到达3千米和4千米位置的休息站的方案都是1。 无论怎么前进都只能停在中间或者距离超出5千米,无法顺利到达空间站,因此到达空间站的方案为0。