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:
import math
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))
count_log = [-1 for i in range(K)]

def recursion(n, count):
    if n == 0:
        return 1
    elif n < 0:
        return 0
    for i in num_set:
        if n-i < 0:
            count += 0
            continue
        elif n-i == 0:
            count += 1
            continue
        elif count_log[n-i] != -1:
            r = count_log[n-i] 
        else:
            r = recursion(n-i, 0)
            count_log[n-i] = r 
        count += r
    return count
output = recursion(K-1, 0)        
print(output%998244353)

Submission status: Runtime Error

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

from functools import lru_cache
#上手くいかない時は下
# from functools32 import lru_cache 

table=[0]*(N+1)
table[1]=1
step=[]
for i in range(K):
    l,r=map(int,input().split())
    for i in range(l,r+1):
        step.append(i)
        
mod=998244353
@lru_cache(None)
def leapy(x):
    if table[x] != 0:
        return table[x]
    for y in step:
        if x>=y+1:
            if table[x-y]!=0:
                table[x] += table[x-y]
                table[x] %= mod
            else:
                equ=leapy(x-y)
                equ %= mod
                table[x] += equ
                table[x-y] = equ
                table[x] %= mod
    return table[x]

#type(leapy(N,table))
print(leapy(N))
#print(table)

Submission status: Runtime Error

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

MOD = 998244353
for _ in range(K):
    L, R = map(int, input().split())
    S |= set(range(L, R + 1))
# print(f'{S=}')

DP = [-1] * (N + 1)
DP[0] = 0
DP[1] = 1


def f(idx):
    ans = 0
    for s in S:
        if idx - s < 0:
            continue
        if DP[idx - s] == -1:
            DP[idx - s] = f(idx - s)
        ans += DP[idx - s]
    return ans % MOD


ans = f(N)
# print(f'{DP=}')
print(ans)
# # 配るDP
# for i in range(1, N + 1):
#     for s in S:
#         DP[i + s] += DP[i]
#     print(f'{DP=}')
#     DP[i] %= MOD
# print(DP[N])

Submission status: Runtime Error

Solution code:
def main():
    N, K = map(int, input().split())
    S = []
    while K !=0:
        L, R = map(int, input().split())
        S += [[L,R]]
        K -= 1
    S.sort()
    A = [1] + [0 for i in range(N + max(s for s in S))]
    for i in range(N):
        for s in S:
            for t in range(s[0], s[1]+1):
            	A[i+t] += A[i]
    print(A[N-1] % 998244353)


main()

Submission status: Runtime Error

Solution code:
def main():
    N, K = map(int, input().split())
    S = []
    while K !=0:
        L, R = map(int, input().split())
        S += [[L,R]]
        K -= 1
    S.sort()
    A = [1] + [0 for i in range(N + max(s for s in S))]
    for i in range(N):
        for s in S:
            for t in range(s[0], s[1]+1):
            A[i+t] += A[i]
    print(A[N-1] % 998244353)


main()

Submission status: Runtime Error

Solution code:

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;

void Main() {
    // input

    int64_t mod = 998244353;
    int64_t N, K;
    cin >> N >> K;
    vector<int64_t> S(2 * K);
    for (int64_t i = 0; i < K; i++) {
        cin >> S[2 * i] >> S[2 * i + 1];
    }
    sort(S.begin(), S.end());
    S.erase(unique(S.begin(), S.end()), S.end());
    

    // process
    int64_t ans[N+1];
    ans[1] = 1;
    ans[0] = 0; // 不要
    for (int64_t n = 2; n <= N; n++) {
        ans[n] = 0;
        for (int64_t i = 0; i < S.size(); i++) {
            if (n - S[i] >= 1) {
                ans[n] += ans[n - S[i]];
                ans[n] %= mod;
            }
        }
        // cout << ans[n] << endl;
    }


    // output
    cout << ans[N] << endl;

}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
mod=998244353
N,K=map(int,input().split())
_S=[]
for _ in range(K):
    l,r=map(int,input().split())
    _S+=list(range(l,r+1))
S=sorted(_S)
dp=[0]*(N+1)
def Leaping_Tak(n,S):
    x=0
    if n==0:
        return 1
    if 0<n<S[0]:
        return 0
    for s in range(S):
        if n-s > 0:
             x += Leaping_Tak(n-s,S)
    return x%mod

ans=Leaping_Tak(N-1,S)
print(ans)

Submission status: Runtime Error

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

L = [0]*K
R = [0]*K

for i in range(K):
    L[i], R[i] = map(int, input().split())

L = sorted(L)
R = sorted(R)

mod = 998244353

def c(n):
    if n == 1:
        return 1
    else:
        ans = 0
        for i in range(K):
            for j in range(L[i],R[i]+1):
                if n-j < 1:
                    return ans % mod
                ans += c(n-j) % mod
        return ans % mod

print(c(N) % mod)

Submission status: Runtime Error

Solution code:
import math
K, N = map(int, input().split())
num_set = []
for i in range(N):
    L, R = map(int, input().split())
    num_set += list(range(L, R+1))
count_log = [-1 for i in range(K)]

def recursion(n, count):
    if n == 0:
        return 1
    elif n < 0:
        return 0
    for i in num_set:
        if n-i < 0:
            count += 0
            continue
        elif n-i == 0:
            count += 1
            continue
        elif count_log[n-i] != -1:
            r = count_log[n-i] 
        else:
            r = recursion(n-i, 0)
            count_log[n-i] = r 
        count += r
    return count
output = recursion(K-1, 0)        
print(output%998244353)

Submission status: Runtime Error

Solution code:
n, k = map(int,input().split())
lr = [map(int, input().split()) for _ in range(k)]
l, r = [list(i) for i in zip(*lr)]
step = []
for i in range(k):
  step.extend(list(range(l[i],r[i]+1)))
step.sort()

m = 998244353
dp = [-1]*n
dp[0] = 1
def solve(n):
  ans = 0
  if dp[n] != -1:
    return dp[n]
  else:
    for s in step:
      if n>=s:
        ans += solve(n-s)
      else:
        break
    dp[n] = ans
    return dp[n]
  
a = solve(n-1)
print(a%m)

Submission status: Runtime Error

Solution code:
import numpy as np
mod = 998244353

n, k = input().split()
n, k = int(n), int(k)
s = []
for i in range(k):
    l, r = input().split()
    for j in range(int(l), int(r)+1):
        s.append(j)

f = [-1] * n
f[0] = 1

def func(i):
    sum = 0
    for j in s:
        if j <= i:
            if (f[i-j] == -1):
                sum += func(i-j)
            else:
                sum += f[i-j]
            sum %= mod
    f[i] = sum
    return sum

print(func(n-1))

Submission status: Runtime Error

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

N,K = (int(x) for x in input().rstrip('\n').split())
As = []
n = [x for x in range(1,N+1)]
for _ in range(K):
  L,R = (int(x) for x in input().rstrip('\n').split())
  As.extend(n[L-1:R])
res = [1]
for i in range(1,As[-1]):
  res.append(sum(res[i-v] for v in As if i-v >= 0)%998244353)
for i in range(As[-1],N):
  res.append(sum(res[i-v] for v in As)%998244353)
print(res[-1])

Submission status: Runtime Error

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

from functools import lru_cache
#上手くいかない時は下
# from functools32 import lru_cache 

table=[0]*(N+1)
table[1]=1
step=[]
for i in range(K):
    l,r=map(int,input().split())
    for i in range(l,r+1):
        step.append(i)
        
mod=998244353
@lru_cache(None)
def leapy(x):
    for y in step:
        if x>=y+1:
            if table[x-y]!=0:
                table[x] += table[x-y]
                table[x] %= mod
            else:
                equ=leapy(x-y)
                table[x] += equ
                table[x-y] = equ
                table[x-y] %=mod
                table[x] %= mod
    return table[x]

#type(leapy(N,table))
print(leapy(N))
#print(table)

Submission status: Runtime Error

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

mod = 998244353

n, k = list(map(int, input().split()))

lr = []
# sets = set([])
for i in range(k):
    l, r = list(map(int, input().split()))
    # sets.update(set(range(l, r+1)))
    lr.append((l, r))
# print(sets)

lr.sort()

np_lists = np.zeros(n, dtype=int)
np_lists[0] = 1

# lists = [0]*n
# lists[0] = 1

for i in range(n):
    # now = lists[i]
    # for j in sets:
    #     if (i+j) < n:
    #         lists[i+j] += now
    now = np_lists[i] % mod
    for j in range(k):
        l, r = lr[j]
        if i+l >= n:
            k = j
            break
        np_lists[i+l:i+r+1] += now % mod


# print(lists[-1] % mod)
print(np_lists[-1] % mod)

Submission status: Runtime Error

Solution code:
import math
K, N = map(int, input().split())
num_set = []
for i in range(N):
    L, R = map(int, input().split())
    num_set += list(range(L, R+1))
#print(num_set)
count_log = [-1 for i in range(K)]

def recursion(n, count):
    if n == 0:
        return 1
    elif n < 0:
        return 0
    for i in num_set:
        #print(n, i, n-i)
        if n-i < 0:
            count += 0
            continue
        if count_log[n-i] != -1:
            r = count_log[n-i] 
        else:
            r = recursion(n-i, 0)
            count_log[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(30000)
M=998244353
y=lambda:map(int,input().split())
n,k=y()
s=set()
for i in range(k):
    a,b=y()
    for j in range(a,b+1):s.add(j)
d={1:1}
def v(n):
    if n<1:return 0
    if n in d:return d[n]
    r=sum(v(n-i)for i in s)%M
    d[n]=r
    return r
print(v(n))

Submission status: Runtime Error

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

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):
    dp = np.zeros(N + 1)
    dp[1] = 1
    for i in range(2, N + 1):
        for j in jumps:
            mn = max(0, i - j[1])
            mx = max(mn, i - j[0])
            dp[i] = (dp[i] + np.sum(dp[mn:mx + 1])) % m
    return dp[N]


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

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()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000)
M=998244353
y=lambda:map(int,input().split())
n,k=y()
s=set()
for i in range(k):
    a,b=y()
    for j in range(a,b+1):s.add(j)
d={1:1}
def v(n):
    if n<1:return 0
    if n in d:return d[n]
    r=sum(v(n-i)for i in s)%M
    d[n]=r
    return r
print(v(n))

Submission status: Runtime Error

Solution code:
def get():
    return [int(x) for x in input().split()]

n, k = get()
s = set()
for _ in range(k):
    start, end = get()
    [s.add(x) for x in range(start, end+1)]
memo = {}
def rec(N):
    if N < 1:
        return 0
    elif N == 1:
        return 1
    ans = 0
    for i in s:
        if i > N:
            break
        if N-i not in memo:
            memo[N-i] = rec(N-i)
        ans += memo[N-i]
        ans %= 998244353
    return ans
print(rec(n))

Submission status: Runtime Error

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

S = set()
LR = []
for _ in range(k):
    tmp = list(map(int, input().split()))
    LR.append(tmp)

for i in LR:
    l, r = int(i[0]), int(i[1])
    for j in range(l, r + 1):
        S.add(j)

diff = n-1

ans = 0

MOD = 998244353

def dfs(A):
    if sum(A) == diff:
        return 1
    if sum(A) > diff:
        return 0
    res = 0
    for v in list(S):
        A.append(v)
        res = max(dfs(A)+res, dfs(A))
        res %= MOD
        A.pop()
    return res


print(dfs([]))

Submission status: Runtime Error

Solution code:
import numpy as np
n, k = map(int, input().split())
sec = np.array([], dtype=np.int)
masu = np.zeros(n, dtype=np.int)
masu[0] = 1
for i in range(k):
    l, r = map(int, input().split())
    sec = np.hstack([sec, np.arange(l,r+1)])
sec.sort()

for i in range(n):
    until = np.where(i+sec > n)
    for step in sec[:until]:
        masu[i + step] += masu[i]
        masu[i + step] %= 998244353

print(masu[-1])

Submission status: Runtime Error

Solution code:

mod =998244353

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

lr_list = []
for i in range(K):
    L, R = map(int,input().split())
    lr_list += list(range(L,R+1))
dp = [0]*N

min_lr_list = min(lr_list)

dp[min_lr_list] = 1

for i in range(min_lr_list+1,N):

    for j in lr_list:
        if i>j:
            dp[i] += dp[i-j]
            dp[i] %=mod
        elif i == j:
            dp[i] += 1
            dp[i] %=mod

print(dp[-1])

Submission status: Runtime Error

Solution code:
def resolve():
    n, k = map(int, input().split())
    mod = 998244353
    dp = [0] * (2*n)
    imos = [0] * (2*n)
    lr = []
    for i in range(k):
        l, r = map(int, input().split())
        lr.append((l, r+1))
    for l, r in lr:
        imos[l] = 1
        imos[r] = -1
    now = 0
    for i in range(1, n):
        now += imos[i]
        now %= mod
        dp[i] = now
        for l, r in lr:
            imos[min(i+l, n+2)] += now
            imos[min(i+r, n+2)] += -1*now
    print(dp[n-1]%mod)


resolve()

Submission status: Runtime Error

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

L = [0]*K
R = [0]*K

for i in range(K):
    L[i], R[i] = map(int, input().split())

L = sorted(L)
R = sorted(R)

mod = 998244353

def c(n):
    if n < 1:
        return 0
    elif n == 1:
        return 1
    else:
        ans = 0
        for i in range(K):
            for j in range(L[i],R[i]+1):
                if n-j < 1:
                    return ans
                ans += c(n-j) % mod
        return ans % mod

print(c(N) % mod)

Submission status: Runtime Error

Solution code:
M=998244353
y=lambda:map(int,input().split())
n,k=y()
s=set()
for i in range(k):
    a,b=y()
    for j in range(a,b+1):s.add(j)
d={1:1}
def v(n):
    if n<1:return 0
    if n in d:return d[n]
    r=sum(v(n-i)for i in s)%M
    d[n]=r
    return r
print(v(n))

Submission status: Runtime Error

Solution code:
import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict,deque
import math
def main():
    def coun(x, i):
        if dp[i] != 0:
            return dp[i]
        else:
            for j in x:
                if (j + i) <= n - 1:
                    dp[i] += coun(x, i + j)
            return dp[i]

    n, k = map(int, input().split())
    x = []
    for i in range(k):
        a, b = map(int, input().split())
        for j in range(a, b + 1):
            x.append(j)
    mod = 998244353
    dp = [0] * n
    dp[-1] = 1
    print(coun(x, 0) % mod)


# region fastio
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def iterate(start, goal, s):
    if start == goal:
        return 1
    elif start > goal:
        return 0
    else:
        res = 0
        for i in s:
            res += iterate(start+i, goal, s)
        return res

ans = iterate(1, n, s)
ans = ans%998244353
print(ans)

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.append((l,r))
MOD = 998244353

memo = [-1 for _ in range(n+1)]

def f(x):
  if x < 1:
    return 0
  if x == 1:
    return 1
  if memo[x] != -1:
    return memo[x]
  res = 0
  for l,r in s:
    for i in range(l,r+1):
      res += f(x-i)
      res %= MOD
  memo[x] = res
  return res

print(f(n))

Submission status: Runtime Error

Solution code:
import itertools
import math
import collections
def get_integral_value_combination(list, target):
    def a(idx, l, r, t):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(list)):
            a((u + 1), l + [list[u]], r, t)
        return r
    return a(0, [], [], target)

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]
    
n, k = map(int, input().split())
s = []
for i in range(k):
  l, r = map(int, input().split())
  lr = [i for i in range(l, r + 1)]
  s += lr

s2 = []
for e in s:
  l = [e]
  m = ((n - 1) // e)
  l2 = l * m
  s2 += l2
ans = 0
ans_l = get_unique_list(get_integral_value_combination(s2, n - 1))

for e in ans_l:
  c = collections.Counter(e)
  p = math.factorial(len(e))
  for f in c:
    p = p // math.factorial(c[f])
  ans += p
ans = ans % 998244353
print(ans)

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 dp[-1]

    print(int(sol(n, jump)))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
l = []
r = []
for i in range(k):
    left, right = map(int,input().split())
    l.append(left)
    r.append(right)

s = set()
for i in range(k):
    lr = list(range(l[i],r[i]+1))
    tmp = set(lr)
    s = s|tmp

def iterate(start, goal, s):
    if start == goal:
        return 1
    elif start > goal:
        return 0
    else:
        res = 0
        for i in s:
            res += iterate(start+i, goal, s)
        return res

ans = iterate(1, n, s)
ans = int(ans%998244353)
print(ans)

Submission status: Runtime Error

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

minL = min(i[0] for i in LR)

mod = 998244353

result = [None for _ in range(N)]
result[0] = 1
#for ni in range(1, N):
def dp(ni):
  result[ni] = 0
  for l, r in LR:
    for j in range(l, r+1):
      if ni-j<0: continue
      result_ni_j = dp(ni-j) if result[ni-j] is None else result[ni-j]
      result[ni] = (result[ni]+result_ni_j) % mod
  return result[ni]


print(dp(N-1))

Submission status: Runtime Error

Solution code:
from sys import stdin


class DFS():
    def __init__(self,N,S):
        self.N = N
        self.S = S
        self.seen = [False] * self.N
        self.cnt = [0] * self.N

    def dfs(self, i):
        if i == self.N-1:
            return 1
        elif i > self.N-1:
            return 0
        elif self.seen[i]:
            return self.cnt[i]
        else:
            cnt = 0
            for s in self.S:
                cnt += self.dfs(i+s)
            else:
                self.cnt[i] = cnt % 998244353
                self.seen[i] = True
            return self.cnt[i]


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, K = list(map(int, _in[0].split(' ')))  # type:list(int)
    L_R_arr = []
    for i in range(K):
        _ = list(map(int, _in[i+1].split(' ')))  # type:list(int)
        L_R_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    ans = 0
    S = []
    for L, R in L_R_arr:
        S.extend([i for i in range(L, R+1)])

    dfs = DFS(N, S)
    dfs.dfs(0)
    ans = dfs.cnt[0] % 998244353
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

def main():
  n, k = map(int, input().split())

  n -= 1

  S = sorted({
    i
    for l, r in [map(int, input().split()) for _ in range(k)]
    for i in range(l, r + 1)
  })

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

  def cal(num):
    total = 0
    for s in S:
      if s > num: break

      next_num = num - s

      total += dp[next_num] or cal(next_num)

    dp[num] = total

    return total

  print(cal(n) % 998244353)





main()

Submission status: Runtime Error

Solution code:
def paths(n,ways,c,s):
    if s==n:
        c[0]+=1
        return
    for i in range(len(ways)):
        midpath=s+ways[i]
        if midpath<=n:
            paths(n,ways,c,midpath)
            



n,k=map(int,input().split())
s=set()
for i in range(k):
    a,b=map(int,input().split())
    for i in range(a,b+1):
        s.add(i)
c=[0]
source=1
(paths(n,list(s),c,source))
print(c[0])

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
dp=[0 for i in range(n)]
num=[False for i in range(n)]
dp[0]=1
mod=998244353
for i in range(k):
    l,r=map(int,input().split())
    for j in range(l,r+1):
        num[j]=True
for i in range(n):
    for j in range(n-i):
        if num[j]:
            dp[i+j]+=dp[i]
            dp[i+j]%=mod
print(dp[n-1]%mod)

Submission status: Runtime Error

Solution code:
import sys

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

sys.setrecursionlimit(N + 1)

L = []
R = []
for _ in range(K):
    l, r = list(map(int, input().split()))
    L.append(l)
    R.append(r)

memo = [None] * (N + 1)

def f(x):
    if x < 0:
        return 0
    if memo[x] is None:
        memo[x] = _f(x)
    # print(x, memo[x])
    return memo[x]


def _f(x):
    if x < 1:
        return 0
    if x == 1:
        return 1
    ans = 0
    for k in range(K):
        for i in range(L[k], R[k] + 1):
            ans += f(x - i)
            ans %= MOD
    return ans % MOD

print(f(N) % MOD)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys


def std_in():
    return sys.stdin.readline().strip()


def get_ints():
    return map(int, sys.stdin.readline().strip().split())


def main():
    n, m = map(int, input().split())
    p = [list(map(int, input().split())) for _ in range(m)]
    s = set()
    for pp in p:
        s |= set(range(pp[0], pp[1]+1))
    s = list(s)
    s.sort()
    d = dict()
    d[1] = 1
    ans, d = find(n, s, d)
    print(ans % 998244353)


def find(n, s, d):
    ans = 0
    for ss in s:
        if n - ss <= 0:
            d[n - ss] = 0
        if not n - ss in d.keys():
            d[n - ss], d = find(n - ss, s, d)
        ans += d[n - ss]
    return ans, d


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import heapq

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
S.sort()
next_node = []
for i in S:
    next_node.append(i + 1)
    combinations[i + 1] += 1
    
heapq.heapify(next_node)

while len(next_node) == 0:
    node = heapq.heappop(next_node)
    for i in S:
        next_idx = node + i
        if next_idx > N + 1:
            break
        else:
            combinations[next_idx] += combinations[node]
            if combinations[next_idx] >= 998244353:
                combinations[next_idx] = combinations[next_idx] % 998244353
            heapq.heappush(next_node, next_idx)
print(combinations[-1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(N + 1)

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

L = []
R = []
for _ in range(K):
    l, r = list(map(int, input().split()))
    L.append(l)
    R.append(r)

memo = [None] * (N + 1)

def f(x):
    if x < 0:
        return 0
    if memo[x] is None:
        memo[x] = _f(x)
    # print(x, memo[x])
    return memo[x]


def _f(x):
    if x < 1:
        return 0
    if x == 1:
        return 1
    ans = 0
    for k in range(K):
        for i in range(L[k], R[k] + 1):
            ans += f(x - i)
            ans %= MOD
    return ans % MOD

print(f(N) % MOD)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys


def std_in():
    return sys.stdin.readline().strip()


def get_ints():
    return map(int, sys.stdin.readline().strip().split())


def main():
    n, m = map(int, input().split())
    p = [list(map(int, input().split())) for _ in range(m)]
    s = set()
    for pp in p:
        s |= set(range(pp[0], pp[1]+1))
    s = list(s)
    s.sort()
    print(s)
    d = dict()
    d[1] = 1
    ans, d = find(n, s, d)
    print(ans % 998244353)


def find(n, s, d):
    ans = 0
    for ss in s:
        if n - ss <= 0:
            d[n - ss] = 0
        if not n - ss in d.keys():
            d[n - ss], d = find(n - ss, s, d)
        ans += d[n - ss]
    return ans, d


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

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

L = []
R = []
for _ in range(K):
    l, r = list(map(int, input().split()))
    L.append(l)
    R.append(r)

memo = [None] * (N + 1)

def f(x):
    if x < 0:
        return 0
    if memo[x] is None:
        memo[x] = _f(x)
    # print(x, memo[x])
    return memo[x]


def _f(x):
    if x < 1:
        return 0
    if x == 1:
        return 1
    ans = 0
    for k in range(K):
        for i in range(L[k], R[k] + 1):
            ans += f(x - i)
            ans %= MOD
    return ans % MOD

sys.setrecursionlimit(N)
print(f(N) % MOD)

Submission status: Runtime Error

Solution code:
import numpy as np
num=input().split(' ')
count=0
plot=np.zeros([int(num[0]),int(num[0])])
t=[]
for a in range(int(num[1])):
  tmp=input().split(' ')
  t.append([int(tmp[0])+a for a in range(int(tmp[1])-int(tmp[0])+1)])
for a in range(int(num[0])):
  if a==0:
    plot[0,0]=1
  else:
    for posit in np.where(plot[a-1]>0)[0]:
      for b in t:
        for c in b:
          if posit+c<int(num[0]):
	          plot[a,posit+c]+=plot[a-1,posit]
xx=int(np.sum(plot[:,-1]))
if xx>998244353:
  print(xx%998244353+1)
else:
  print(xx)

Submission status: Runtime Error

Solution code:
from sys import stdin


class DFS():
    def __init__(self,N,S):
        self.N = N
        self.S = S
        self.seen = [False] * self.N
        self.cnt = [0] * self.N

    def dfs(self, i):
        if i == self.N-1:
            return 1
        elif i > self.N-1:
            return 0
        elif self.seen[i]:
            return self.cnt[i]
        else:
            cnt = 0
            for s in self.S:
                cnt += self.dfs(i+s)
            else:
                self.cnt[i] = cnt % 998244353
                self.seen[i] = True
            return self.cnt[i]


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, K = list(map(int, _in[0].split(' ')))  # type:list(int)
    L_R_arr = []
    for i in range(K):
        _ = list(map(int, _in[i+1].split(' ')))  # type:list(int)
        L_R_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    ans = 0
    S = []
    for L, R in L_R_arr:
        S.extend([i for i in range(L, R+1)])
    S = sorted(set(S))
    dfs = DFS(N, S)
    dfs.dfs(0)
    ans = dfs.cnt[0] % 998244353
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split(" "))
a=[]
for k in range(K):
    l,r=map(int,input().split(" "))
    a+=list(range(l,r+1))
b=[0 for i in range(a[-1]-1)]
b.append(1)
for i in range(N-1):
    x=0
    for j in a:
        x+=b[-j]
    b.append(x)
print(b[-1]%998244353)