Problem:


Score : 400 points

Problem Statement

There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.

Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.

You are given an integer K that is less than or equal to 10, and K non-intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K].
Let S be the union of these K segments.
Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.

When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.

To help Tak, find the number of ways to go to Cell N, modulo 998244353.

Constraints

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] and [L_j, R_j] do not intersect (i \neq j) 

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
L_1 R_1
L_2 R_2
:
L_K R_K

Output

Print the number of ways for Tak to go from Cell 1 to Cell N, modulo 998244353.

Sample Input 1

5 2
1 1
3 4

Sample Output 1

4

The set S is the union of the segment [1, 1] and the segment [3, 4], therefore S = \{ 1, 3, 4 \} holds.

There are 4 possible ways to get to Cell 5:

1 \to 2 \to 3 \to 4 \to 5,

1 \to 2 \to 5,

1 \to 4 \to 5 and

1 \to 5.

Sample Input 2

5 2
3 3
5 5

Sample Output 2

0

Because S = \{ 3, 5 \} holds, you cannot reach to Cell 5.
Print 0.

Sample Input 3

5 1
1 2

Sample Output 3

5

Sample Input 4

60 3
5 8
1 3
10 15

Sample Output 4

221823067

Note that you have to print the answer modulo 998244353.



Sample input:
5 2
1 1
3 4


Sample output:
4

Submission status: Runtime Error

Solution code:
# -*- coding: Shift-JIS -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 998244353

class BIT2:
    """ 区間加算BIT(区間加算・区間合計取得) """
    def __init__(self, N):
        self.N = (N+1)
        self.data0 = [0] * (N+1)
        self.data1 = [0] * (N+1)
        
    def _add(self, data, k, x):
        while k < self.N: #k <= Nと同義
            data[k] += x
            k += k & -k

    def _sum(self, data, k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s

    def add(self, l, r, x):
        """ 区間[l,r)に値xを追加 """
        self._add(self.data0, l, -x*(l-1))
        self._add(self.data0, r, x*(r-1))
        self._add(self.data1, l, x)
        self._add(self.data1, r, -x)

    def sum(self, l, r):
        """ 区間[l,r)の和を取得 """
        return self._sum(self.data1, r-1) * (r-1) + self._sum(self.data0, r-1) - self._sum(self.data1, l-1) * (l-1) - self._sum(self.data0, l-1)
    
N, K = map(int, readline().split())
bit = BIT2(N)
d = []
for _ in range(K):
    L,R = map(int, readline().split())
    d.append((L,R))
    
d = sorted(d)
bit.add(1,2,1)

for i in range(2,N+1):
    for k in range(K):
        L,R = d[k]
        if i-L > 0:
            tmp = bit.sum(max(1,i-R),i-L+1)%MOD
            bit.add(i,i+1,tmp)
        else:
            break
print(bit.sum(N,N+1))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
s = []
for i in range(k):
    l, r = map(int, input().split())
    s += list(range(l, r+1)

mod = 998244353
dp = [0] * (n+1)
dp[1] = 1
s = sorted(s)
for i in range(1, n):
    dp[i] %= mod
    for add in s:
        if i+add <= n:
            dp[i+add] += dp[i]
print(dp[n] % mod)

Submission status: Runtime Error

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
# from numba import njit,i8


# @njit(i8(i8,i8,i8,i8[:,:],i8[:],i8,i8))
def give_dp(N,K,mod,LR,dp,l,r):
    for i in range(N):
        if i > 0:
            dp[i] += dp[i-1]
            dp[i] %= mod
        for k in range(K):
            l = LR[k][0]
            r = LR[k][1]
            if i + l < N:
                dp[i+l] += dp[i]
                dp[i+1] %= mod
            if i + r < N:
                dp[i+r+1] -= dp[i]
                dp[i+1] %= mod
    return dp[-1]


def main():
    N,K = map(int,input().split())
    LR = [list(map(int,input().split())) for i in range(K)]
    # LR = np.array(LR)

    mod = 998244353

    dp = [0 for i in range(N)]
    dp[0] = 1
    dp[1] = -1
    # dp = np.array(dp)

    res = give_dp(N,K,mod,LR,dp,0,0)
    res %= mod

    print(res)



main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200000)

K, N = map(int, input().split())
num_list = []
for i in range(N):
    L, R = map(int, input().split())
    num_list += list(range(L, R+1))
    
num_set = set(sorted(num_list))
 
counted = {}
def recursion(n, count):
    if n == 0:
        return 1
    elif n < 0:
        return 0
    for i in num_set:
        if i <= 0:
            continue
        if n-i in counted:
            r = counted[n-i] 
        else:
            r = recursion(n-i, 0)
            counted[n-i] = r 
        count += r
    return count
output = recursion(K-1, 0)        
print(output%998244353)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000)

K, N = map(int, input().split())
num_list = []
for i in range(N):
    L, R = map(int, input().split())
    num_list += list(range(L, R+1))
num_set = set(sorted(num_list))

counted = {}

def recursion(n):
    count = 0
    for i in num_set:
        if n-i < 0:
            continue
        elif n-i in counted:
            r = counted[n-i]
        else:
            r = recursion(n-i)
            counted[n-i] = r 
        count += r
    return count

output = recursion(K-1)        
print(output%998244353)

Submission status: Runtime Error

Solution code:
# inp.readline()
# int(inp.readline())
# out.write()
# raw_input()
# map(int,raw_input().split())
# map(int,inp.readline().split())
# for _ in xrange(input()):
# print "Case #"+str(_+1)+": "+ 
if __name__ == "__main__":
    from sys import stdin as inp, stdout as out,setrecursionlimit as srl
    from collections import Counter,defaultdict,deque
    from heapq import *
    def upd(idx,v):
      while idx<len(b):
        b[idx]=(b[idx]+v)%mod
        idx+=(idx&-idx)
    def acc(idx):
        s=0
        while idx>0:
            s=(s+b[idx])%mod
            idx-=(idx&-idx)
        return s
    for _ in xrange(1):
        n,k=map(int,inp.readline().split())
        a=[map(int,inp.readline().split()) for i in xrange(k)]
        b=[0]*(n+1)
        b[1]=1
        mod=998244353
        for i in xrange(2,n+1):
          for l,r in a:
            upd(i,acc(i-l+1)-acc(max(0,i-r)))
        print (acc(n+1)-acc(n))%mod

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <list>
#include <string>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <iomanip> // setprecisionを使用するのに必要 cout << fixed << setprecision(15) << p でpを小数点以下15桁表示
using namespace std;
#define REPD(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) REPD(i, 0, n)
#define DIV0 1000000007
typedef long long ll;
#define fin(ans) cout << (ans) << '\n'
/*

*/
int main()
{
    int N,K;
    cin >> N >> K;
    int LR[N][2];
    REP(i,K) cin >> LR[i][0] >> LR[i][1];
    ll mmm = 998244353;
    vector<ll> DP(N+1);
    vector<ll> DPsum(N+1);
    DP[1] = 1;
    DPsum[1] = 1;
    for(int i = 2; i <= N; i++){
        REP(j,K){
            //where come from?
            int li = i-LR[j][1];//min
            int ri = i-LR[j][0];//max
            if(ri < 0) continue;
            li = max(li,1);
            DP[i] = ((DP[i]+(DPsum[ri]-DPsum[li-1])%mmm)+mmm)%mmm;
        }
        //累積和の更新
        DPsum[i] = (DPsum[i-1]+DP[i])%mmm;
    }
    fin(DP[N]);
    return 0;
}

Submission status: Runtime Error

Solution code:
K, N = map(int, input().split())
num_list = []
for i in range(N):
    L, R = map(int, input().split())
    num_list += list(range(L, R+1))
num_set = set(sorted(num_list))

counted = {}
def recursion(n):
    count = 0
    if n == 0:
        return 1
    elif n < 0:
        return 0
    for i in num_set:
        if i<=0:
            continue
        if n-i < 0:
            continue
        elif n-i in counted:
            r = counted[n-i]
        else:
            r = recursion(n-i)
            counted[n-i] = r 
        count += r
    return count

output = recursion(K-1)        
print(output%998244353)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    LR = [tuple(map(int, input().split())) for _ in range(K)]
    S = set()
    for start, end in LR:
        for i in range(start, end + 1):
            S.add(i)
    M = dict()
    answer = calc(N, S, M)
    print(answer % 998244353)


def calc(n: int, S: set, M: dict):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n in M:
        return M[n]
    result = 0
    for s in S:
        result += calc(n - s, S, M)
    M[n] = result
    return result


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N,X,M = map(int,input().split())

ans = X
A = X
TF = True
srt = 1000000
retu = dict()
retu[X] = 1
loop = X
for i in range(N-1):
    if TF:
        A = A**2 % M
        if retu.get(A) != None:
          srt = j
          goal = i
          TF = False
          break   
        if TF:
          retu[A] = 1
          loop += A
    else:
      break
      
if N-1 > srt:
    n = (N-srt)//(goal-srt+1)
    saisyo = sum(retu[:srt])
    loop -= saisyo
    print(saisyo + loop*n + sum(retu[srt:N-n*(goal-srt+1)]))
    
else:
    print(sum(retu[:N]))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    LR = [tuple(map(int, input().split())) for _ in range(K)]
    S = set()
    for (start, end) in LR:
        for i in range(start, end + 1):
            S.add(i)
    M = dict()
    answer = calc(N, S, M)
    print(answer % 998244353)


def calc(n: int, S: set, M: dict):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n in M:
        return M[n]
    result = 0
    for s in S:
        result += calc(n - s, S, M) % 998244353
    if n not in M:
        M[n] = result
    return result


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    LR = [tuple(map(int, input().split())) for _ in range(K)]
    S = set()
    for (start, end) in LR:
        for i in range(start, end + 1):
            S.add(i)
    M = dict()
    answer = calc(N, S, M)
    print(answer % 998244353)


def calc(n: int, S: set, M: dict):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n in M:
        return M[n]
    result = 0
    for s in S:
        result += calc(n - s, S, M)
    if n not in M:
        M[n] = result
    return result


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
mod = 998244353
N, K = map(int, input().split())

LR = [map(int, input().split()) for _ in range(K)]
L, R = [list(i) for i in zip(*LR)]

a = []
for i in range(K):
  a.extend(list(range(L[i], R[i] + 1)))
LR = list(set(a))

DP = [0]*N
DP[0] = 1
for i in range(N):
  if i + LR[-1] >= N:
    LR.pop(-1)
  if len(LR) < 1:
    break
  
  for s in LR:
     DP[i + s] += DP[i]


print(DP[N-1] % mod)

Submission status: Runtime Error

Solution code:
mod = 998244353
N, K = map(int, input().split())

LR = [map(int, input().split()) for _ in range(K)]
L, R = [list(i) for i in zip(*LR)]

a = []
for i in range(K):
  a.extend(list(range(L[i], R[i] + 1)))
LR = list(set(a))

print(LR)
DP = [0]*N
DP[0] = 1
for i in range(N):
  if i + LR[-1] >= N:
    LR.pop(-1)
  if len(LR) < 1:
    break
  for s in LR:
    local = i + s
    DP[local] += DP[i]


print(DP[N-1] % mod)

Submission status: Runtime Error

Solution code:
import sys
import copy
#import math
#import itertools
#import numpy as np
#import re

def func(x,m):
    return x**2%m

N,X,M=[int(c) for c in input().split()]
myset = {X}
mydict = {0:X}
A = []
A.append(X)
s = X
i = 0
i_stop = i
#i=0は計算したので1から
for i in range(1,N):
    A.append(func(A[i-1],M))
    if A[i] in myset:
        i_stop = i
        break
    myset.add(A[i])
    mydict[A[i]] = i
    s+=A[i]
    if i == N-1:
        print(s)
        sys.exit(0)
    if A[i] == 0:
        print(s)
        sys.exit(0)

if i!=0 and mydict[A[i_stop]] != i_stop:
    #最後にA[i]が出現したのは？
    A_repeat = A[mydict[A[i_stop]]:i_stop]
    s+=((N-1)-(i_stop-1))//len(A_repeat)*sum(A_repeat)

    for k in range(((N-1)-(i_stop-1))%len(A_repeat)):
        s+=A_repeat[k]



print(s)

Submission status: Runtime Error

Solution code:
mod = 998244353
N, K = map(int, input().split())

LR = [map(int, input().split()) for _ in range(K)]
L, R = [list(i) for i in zip(*LR)]

a = []
for i in range(K):
  a.extend(list(range(L[i], R[i] + 1)))
LR = list(set(a))

DP = [0]*N
DP[0] = 1
for i in range(N):
  if i + LR[-1] > N:
    LR.pop(-1)
  for s in LR:
    local = i + s
    if local < N:
      DP[local] += DP[i]


print(DP[N-1] % mod)

Submission status: Runtime Error

Solution code:
import numpy as np  # noqa
import numba
from numba import njit, b1, i4, i8, f8

m = 998244353
N, K = map(int, input().split())

jumps = []
for i in range(K):
    l, r = map(int, input().split())
    jumps.append(np.array([l, r]))

jumps = np.array(jumps)


@njit((i8, i8, i8[:, :]), cache=True)
def main(N, m, jumps):
    dpsum = np.zeros(N + 1)
    dp = np.zeros(N + 1)
    dp[1] = dpsum[1] = 1

    for i in range(2, N + 1):
        for j, jump in enumerate(jumps):
            mn = max(0, i - jump[1])
            mx = max(mn, i - jump[0])
            dp[i] = (dp[i] + dpsum[mx] - dpsum[mn - 1]) % m
        dpsum[i] = (dp[i] + dpsum[i - 1]) % m
    return dp[N]


print(int(main(N, m, jumps)))

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
hani = [0 for i in range(n)]#i-1がふくまれているか
kumi = [-1 for i in range(n+1)] #iマス目に行く通り
min = n
for i in range(k):
    l,r = map(int,input().split())
    if l < min:
        min = l
    for j in range(l-1,r):
        hani[j] = 1
kumi[0] = 1
for i in range(1,min):
    kumi[i] = 0
kumi[min] = 1

def countt(n,hani,kumi):
    if kumi[n-1] < 0:
        an = 0
        for i in range(0,n-2):
            if hani[i] == 1:
                if kumi[n-i-2] == -1:
                    kumi = countt(n-i-1,hani,kumi)
                an += kumi[n-i-2]
        kumi[n-1] = an
    return kumi

kumi = countt(n,hani,kumi)
ans = kumi[-2]
print(ans % 998244353)

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
hani = [0 for i in range(n)]#i-1がふくまれているか
kumi = [-1 for i in range(n+1)] #iマス目に行く通り
min = n
for i in range(k):
    l,r = map(int,input().split())
    if l < min:
        min = l
    for j in range(l-1,r):
        hani[j] = 1
kumi[0] = 1
if min > 1:
    for i in range(1,min):
        kumi[i] = 0
kumi[min] = 1

def countt(n,hani,kumi):
    if kumi[n-1] < 0:
        an = 0
        for i in range(0,n-1):
            if hani[i] == 1:
                if kumi[n-i-2] == -1:
                    kumi = countt(n-i-1,hani,kumi)
                an += kumi[n-i-2]
        kumi[n-1] = an
    return kumi

kumi = countt(n,hani,kumi)
ans = kumi[-2]
print(ans % 998244353)

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
hani = [0 for i in range(n)]#i-1がふくまれているか
kumi = [-1 for i in range(n+1)] #iマス目に行く通り
min = n
for i in range(k):
    l,r = map(int,input().split())
    if l < min:
        min = l
    for j in range(l-1,r):
        hani[j] = 1
kumi[0] = 1
for i in range(1,min):
    kumi[i] = 0
kumi[min] = 1

def countt(n,hani,kumi):
    if kumi[n-1] < 0:
        an = 0
        for i in range(0,n-1):
            if hani[i] == 1:
                if kumi[n-i-2] == -1:
                    kumi = countt(n-i-1,hani,kumi)
                an += kumi[n-i-2]
        kumi[n-1] = an
    return kumi

kumi = countt(n,hani,kumi)
ans = kumi[-2]
print(ans % 998244353)

Submission status: Runtime Error

Solution code:
import numpy as np  # noqa
import numba
from numba import njit, b1, i4, i8, f8

m = 998244353
N, K = map(int, input().split())

jumps = []
for i in range(K):
    l, r = map(int, input().split())
    jumps.append([l, r])

jumps = np.array(jumps)


@njit((i8, i8, i8[:, :]), cache=True)
def main(N, m, jumps):
    dpsum = np.zeros(N + 1)
    dp = np.zeros(N + 1)
    dp[1] = dpsum[1] = 1

    for i in range(2, N + 1):
        for j, jump in enumerate(jumps):
            mn = max(0, i - jump[1])
            mx = max(mn, i - jump[0])
            dp[i] = (dp[i] + dpsum[mx] - dpsum[mn - 1]) % m
        dpsum[i] = (dp[i] + dpsum[i - 1]) % m
    return dp[N]


print(int(main(N, m, jumps)))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def input_int_array():
    return map(int, input().split())


def answer():
    n, k = input_int_array()
    spans = [tuple(input_int_array()) for x in range(k)]

    count = [0 for x in range(n)]
    count[0] = 1

    for i in range(n):
        if i > 0:
            count[i] += count[i-1]
        for j in range(k):
            l, r = spans[j]
            for lr in range(l, r + 1):
                if i + lr < n:
                    count[i + lr] += count[i]
                else:
                    break
    print(count[-1] % 998244353)


answer(

Submission status: Runtime Error

Solution code:
#配るDP
n,k=map(int,input().split())
l=[0]*k
r=[0]*k
for j in range(k):
  l[j],r[j] = map(int,input().split())
p=998244353
dp=[0]*(n+100)
dp[1]=1
dp[2]=-1
for i in range(1,n+1):
  dp[i] += dp[i-1]
  dp[i] %= p
  
  for lj,rj in zip(l,r):
    dp[i+lj] += dp[i]
    dp[i+lj] %= p
    dp[i+rj+1] -= dp[i]
    dp[i+rj+1] %= p
print(dp[n])

Submission status: Runtime Error

Solution code:
p = 998244353
n, k = map(int, input().split())
LRs = []
for j in range(k):
    lj, rj = map(int, input().split())
    LRs.append((lj, rj))
A = [0] * n
i0 = min(lj for lj, rj in LRs)
A[0] = 1
A[i0] = 1
for i in range(i0 + 1, n):
    A[i] = A[i - 1]
    for j in range(k):
        lj, rj = LRs[j]
        if i - lj >= 0:
            A[i] += A[i - lj]
        if i - 1 - rj >= 0:
            A[i] -= A[i - 1 - rj]
        A[i] %= p
print(A[n - 1])

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
hani = [0 for i in range(n)]
kumi = [-1 for i in range(n)]
min = n
for i in range(k):
    l,r = map(int,input().split())
    if l < min:
        min = l
    for j in range(l-1,r):
        hani[j] = 1
for j in range(min-1):
    kumi[j] = 0
kumi[min-1] = 1

def countt(n,hani,kumi):
    an = 0
    for i in range(0,n-1):
        if hani[i] == 1:
            if n-i-2 >= 0:
                if kumi[n-i-2] == -1:
                    kumi = countt(n-i-1,hani,kumi)
                an += kumi[n-i-2]
            else:
                break
    kumi[n-1] = an
    return kumi

kumi = countt(n,hani,kumi)
ans = kumi[-1]
print(ans % 998244353)

Submission status: Runtime Error

Solution code:
mod = 998244353
n,k = map(int,input().split())

t = [False] * 20

for i in range(k):
    l,r = map(int,input().split())
    for j in range(l,r+1,1):
        t[j] = True

s = []
for i,v in enumerate(t):
    if v == True:
        s.append(i)

dp = [0] * (n+5)
dp[1] = 1

for i in range(2,n+1,1):
    for d in s:
        if i-d>=1:
            dp[i] += dp[i-d]

print(dp[n] % mod)

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
hani = [0 for i in range(n)]
kumi = [-1 for i in range(n)]
min = n
for i in range(k):
    l,r = map(int,input().split())
    if l < min:
        min = l
    for j in range(l-1,r):
        hani[j] = 1
for j in range(min-1):
    kumi[j] = 0
kumi[min-1] = 1

def countt(n,hani,kumi):
    an = 0
    for i in range(0,n-1):
        if hani[i] == 1:
            if kumi[n-i-2] == -1:
                kumi = countt(n-i-1,hani,kumi)
            an += kumi[n-i-2]
    kumi[n-1] = an
    return kumi

kumi = countt(n,hani,kumi)
ans = kumi[-1]
print(ans % 998244353)

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
hani = [0 for i in range(n)]
kumi = [-1 for i in range(n)]
for i in range(k):
    l,r = map(int,input().split())
    for j in range(l-1,r):
        hani[j] = 1


def countt(n,hani,kumi):
    if n == 1:
        if hani[0] == 1:
            kumi[0] = 1
        else:
            kumi[0] = 0
    else:
        an = 0
        for i in range(0,n-1):
            if hani[i] == 1:
                if kumi[n-i-2] == -1:
                    kumi = countt(n-i-1,hani,kumi)
                an += kumi[n-i-2]
        kumi[n-1] = an
    return kumi

kumi = countt(n,hani,kumi)
ans = kumi[-1]
print(ans % 998244353)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
MOD = 998244353

lr = []
for _ in range(k):
    l, r = map(int, input().split())
    lr += (list(range(l, r + 1)))

lr.sort()
lr = np.array(lr)

dp = np.zeros(n + n, dtype=np.int64)
dp[0] = 1
dp2 = dp.copy()

for i in range(n):
    idx = i + lr
    dp2[idx] += dp[i]
    dp2 %= MOD
    dp = dp2

print(dp[n - 1])

Submission status: Runtime Error

Solution code:
import functools
n, k = map(int, input().split())
s = set()
for i in range(k):
    k1, k2 = map(int, input().split())
    for i in range(k1, k2+1):
        s.add(i)
@functools.lru_cache(None)
def dp(cur):
    ret = 0
    if cur == n:
        ret +=  1
    for i in s:
        temp = i + cur
        if temp > n:
            continue
        else:
            ret += dp(temp)
    return ret
print(dp(1)%(998244353))

Submission status: Runtime Error

Solution code:
import sys
import itertools

N, K = map(int, input().split())
S = set()

dp = [0] * (N) 
dp[0]=0
q = []


for i in range(K):
    a, b = map(int, input().split())
    for j in range(a-1, b):
        dp[j+1] = 1
        q.append(j+1)

q = sorted(q)

for i in range(1, N):
    for j in q:
        if i - j < 1:
            break
        dp[i] = dp[i] + dp[i-j]
    # if i > 6:
    #     exit()

print(dp[N-1] % 998244353)

Submission status: Runtime Error

Solution code:
K, N = map(int, input().split())
num_list = []
for i in range(N):
    L, R = map(int, input().split())
    num_list += list(range(L, R+1))
    
num_set = set(sorted(num_list))

counted = {}
def recursion(n):
    global counted
    count = 0
    if n == 0:
        return 1
    elif n < 0:
        return 0
    for i in num_set:
        if n-i < 0:
            continue
        elif n-i in counted:
            r = counted[n-i]
        else:
            r = recursion(n-i)
            counted[n-i] = r 
        count += r
    return count

output = recursion(K-1)        
print(output%998244353)

Submission status: Runtime Error

Solution code:
K, N = map(int, input().split())
num_list = []
for i in range(N):
    L, R = map(int, input().split())
    num_list += list(range(L, R+1))
    
num_set = set(sorted(num_list))

counted = {}
def recursion(n):
    count = 0
    if n == 0:
        return 1
    elif n < 0:
        return 0
    for i in num_set:
        if n-i < 0:
            continue
        elif n-i in counted:
            r = counted[n-i]
        else:
            r = recursion(n-i)
            counted[n-i] = r 
        count += r
    return count

output = recursion(K-1)        
print(output%998244353)

Submission status: Runtime Error

Solution code:
MOD = 998244353

N, K = map(int, input().split())
seg = [tuple(map(int, input().split())) for _ in range(K)]
dp = [0] * (N+1)
dp[0] = 1
for i in range(N):
    for s, t in seg:
        dp[i+s] += dp[i]
        dp[i+t;1] -= dp[i]
    dp[i+1] += dp[i]
    dp[i+1] %= MOD
    
print(dp[N-1])

Submission status: Runtime Error

Solution code:
mod = 998244353
n,k = map(int,input().split())

t = [False] * 20

for i in range(k):
    l,r = map(int,input().split())
    for j in range(l,r+1,1):
        t[j] = True

s = []
for i,v in enumerate(t):
    if v == True:
        s.append(i)

dp = [0] * (n+5)
dp[1] = 1

for i in range(2,n+1,1):
    for d in s:
        if i-d>=1:
            dp[i] += dp[i-d]
            dp[i] %= mod

print(dp[n] % mod)

Submission status: Runtime Error

Solution code:
mod = 998244353
n,k = map(int,input().split())

t = [False] * 20

for i in range(k):
    l,r = map(int,input().split())
    for j in range(l,r+1,1):
        t[j] = True

s = []
for i,v in enumerate(t):
    if v == True:
        s.append(i)

dp = [0] * (n+5)
dp[1] = 1

for i in range(2,n+1,1):
    for d in s:
        if i-d>=1:
            tmp = dp[i-d]
            dp[i] += tmp
            dp[n] %= mod

print(dp[n] % mod)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np

input = sys.stdin.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())



N, K = MI()

steps = set()
for _ in range(K):
    l, r = MI()
    steps |= set(range(l, r + 1))

dp = np.zeros(N)
dp[0] = 1

for i in range(N):
    for s in steps:
        tmp = i - s
        if tmp >= 0:
            dp[i] += dp[tmp]
            dp[i] %= mod

print(int(dp[N - 1]))

Submission status: Runtime Error

Solution code:
mod = 998244353
n,k = map(int,input().split())

t = [False] * 20

for i in range(k):
    l,r = map(int,input().split())
    for j in range(l,r+1,1):
        t[j] = True

s = []
for i,v in enumerate(t):
    if v == True:
        s.append(i)

dp = [0] * (n+5)
dp[1] = 1

for i in range(2,n+1,1):
    for d in s:
        if i-d>=1:
            dp[i] += dp[i-d]
            dp[n] %= mod

print(dp[n] % mod)

Submission status: Runtime Error

Solution code:
from sys import stdin
#再起?
CON = 998244353
cnt = 0
def move(N, S):
    global cnt
    if N == 0:
        cnt += 1
        #print('ok')
        return
    elif N < 0:
        return
    else:
        for x in S:
            #print(x)
            move(N-x, S)
S = set()
N, K = [int(x) for x in stdin.readline().rstrip().split()]
for i in range(K):
    L, R = [int(x) for x in stdin.readline().rstrip().split()]
    for x in range(L, R+1):
        S.add(x)
move(N-1, S)
cnt %= CON
print(cnt)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
D = []
S = []
T = []
mod = 998244353
for i in range(K):
  D.append(list(map(int, input().split())))
  while(D[i][0] <= D[i][1]):
    S.append(D[i][0])
    D[i][0] += 1

def func(x,S,T):
  for i in range(len(T)):
    if x == T[i][0]:
      return T[i][1]
  count = 0
  for t in S:
    if x-t > 1:
      count += func(x-t,S,T)
    elif x-t == 1:
      count += 1
  T.append((x,count))
  return count%mod

print(func(N,S,T)%mod)

Submission status: Runtime Error

Solution code:
from sys import stdin
#再起?
cnt = 0
def move(N, S):
    global cnt
    if N == 0:
        cnt += 1
        cnt %= 998244353
        #print('ok')
        return
    elif N < 0:
        return
    else:
        for x in S:
            #print(x)
            move(N-x, S)
S = set()
N, K = [int(x) for x in stdin.readline().rstrip().split()]
for i in range(K):
    L, R = [int(x) for x in stdin.readline().rstrip().split()]
    for x in range(L, R+1):
        S.add(x)
move(N-1, S)
print(cnt)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(set(sum([list(map(int, input().split())) for i in range(k)], [])))

def dfs(i):
  cnt = 0
  if i > n:
    return 0
  elif i == n:
    return 1
  for x in a:
    cnt += dfs(i+x)
  return cnt

print(dfs(1) % 998244353)

Submission status: Runtime Error

Solution code:
from collections import deque
import bisect

N, K = list(map(int, input().split(" ")))
S = []
for _ in range(K):
    a, b = list(map(int, input().split(" ")))
    S.extend(range(a, b+1))


combinations = [0] * (N + 1)
combinations[1] = 1
checked = [False] * (N + 1)
S.sort()
next_node = []
for i in S:
    next_node.append(i + 1)
    combinations[i + 1] += 1
next_node = deque(next_node)
while len(next_node) > 0:
    node = next_node.popleft()
    if checked[node]:
        # check済みならskip
        continue
    else:
        checked[node] = True
    for i in S:
        next_idx = node + i
        if next_idx > N:
            break
        else:
            combinations[next_idx] += combinations[node]
            if combinations[next_idx] >= 998244353:
                combinations[next_idx] = combinations[next_idx] % 998244353
            bisect.insort_left(next_node, next_idx)
print(combinations[-1])

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]

dp = [-1 for _ in range(N + 1)]
dp[0] = 1


def dfs(n):
    if n < 0:
        return 0

    if 0 <= dp[n]:
        return dp[n]

    ans = 0
    for l, r in LR:
        for d in range(l, r + 1):
            ans += dfs(n - d)
            ans %= 998244353

    dp[n] = ans
    return dp[n]


print(dfs(N - 1))

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines

def main():
    large_num = 998244353
    n, k = map(int, input().split())
    n -= 1
    dd = [0] * (n+1)
    m = map(int, read().split())
    ab = zip(m, m)
    for a, b in ab:
        for i1 in range(a, b + 1):
            dd[i1]=1
    s = [i for i, v in enumerate(dd) if v]
    dp = [0] * (n + 1)
    dp[0]=1
    s = tuple(s)
    for i1 in range(1, n+1):
        for se in s:
            if se > i1:
                break
            else:
                dp[i1] += dp[i1 - se]
        dp[i1] = dp[i1] % large_num
    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
mod = 998244353
n,k = map(int,input().split())

t = [False] * 20

for i in range(k):
    l,r = map(int,input().split())
    for j in range(l,r+1,1):
        t[j] = True

s = []
for i,v in enumerate(t):
    if v == True:
        s.append(i)

dp = [0] * (n+5)
dp[1] = 1

for i in range(2,n+1,1):
    for d in s:
        if i-d>=1:
            dp[i] += dp[i-d]
    dp[n] %= mod

print(dp[n] % mod)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
D = []
S = []
T = []
mod = 998244353
for i in range(K):
  D.append(list(map(int, input().split())))
  while(D[i][0] <= D[i][1]):
    S.append(D[i][0])
    D[i][0] += 1

def func(x,S,T):
  for i in range(len(T)):
    if x == T[i][0]:
      return T[i][1]
  count = 0
  for t in S:
    if x-t > 1:
      count += func(x-t,S,T)
    elif x-t == 1:
      count += 1
  T.append((x,count))
  return count

print(func(N,S,T)%mod)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
import numpy as np
from numba import njit
def main():
    large_num = 998244353
    n, k = map(int, input().split())
    n -= 1
    jump = []
    m = map(int, read().split())
    for a, b in zip(m, m):
        jump.append((a, b))
    jump = np.array(jump)
    @njit
    def sol(n, jump):
        dp = np.zeros(n+1)
        dp[0] = 1
        for i1 in range(1, n+1):
            for je in jump:
                for se in range(je[0],je[1]+1):
                    if se > i1:
                        break
                    else:
                        dp[i1] += dp[i1 - se]
                        dp[i1] = dp[i1] % large_num
        return int(dp[-1])
    print(sol(n, jump))

if __name__ == '__main__':
    main()