Leaping Tak SOLUTION AtCoder Beginner Contest 179

Leaping Tak SOLUTION

There are N cells organized straight, numbered 1 , 2 , … , N from left to right. Tak lives in these cells and is as of now on Cell 1 . He is attempting to arrive at Cell N by utilizing the system depicted underneath. You are given a number K that is not exactly or equivalent to 10 , and K non-meeting portions [ L 1 , R 1 ] , [ L 2 , R
2 ] , … , [ L K , R K ] . Let S be the association of these K portions. Here, the portion [ l , r ] signifies the set comprising everything being equal I that fulfill l ≤ I ≤ r . �When you are on Cell I , pick a number d from
S what’s more, move to Cell I + d . You can’t move out of the cells. To help Tak, locate the quantity of approaches to Cell N , modulo 998244353 .
Requirements
2 ≤ N ≤ 2 × 10
5 1 ≤ K ≤ min ( N , 10 )
1 ≤ L I ≤ R I ≤ N [ L I , R I ]
also, [ L j , R j ] try not to cross ( I ≠ j )
All qualities in input are whole numbers.
Information
Information is given from Standard Input in the accompanying configuration:
N K L 1 R 1 L 2 R 2 : L K R K
Yield
Print the quantity of ways for Tak to go from Cell
1
to Cell
N
, modulo
998244353
.
Test Input 1
Duplicate
5 2
1
3 4
Test Output 1
Duplicate
4
The set
S
is the association of the section
[ 1 , 1 ] also, the fragment [ 3 , 4 ] , accordingly S = { 1 , 3 , 4 } holds.
There are 4 potential approaches to get to Cell 5 : 1 → 2 → 3 → 4 → 5 , 1 → 2 → 5 , 1 → 4 → 5
also, 1 → 5 .
Test Input 2
Duplicate
5 2
3
5
Test Output 2
Duplicate
0
Since
S = { 3 , 5 } holds, you can’t reach to Cell 5 . Print 0
.
Test Input 3
Duplicate
5 1
1 2
Test Output 3
Duplicate
5
Test Input 4
Duplicate
60 3
5 8
1 3
10 15
Test Output 4
Duplicate
221823067
Note that you need to print the appropriate response modulo
998244353
.

Leave a Comment