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:
n,k = map(int,input().split())
mod = 998244353
s = []
for i in range(k):
    l,r =map(int,input().split())
    if l == r:
        if l < n:
            s.append(l)
    else:
        for i in range(l,r+1):
            if i < n:
                s.append(i)
    s = list(set(s))
s = sorted(s)

min1 = s[0]
tansa = sorted(s[:])
road = n-1
count=0
while tansa != []:
    search = tansa.pop()
    road-=search
    save = road
    for i in range(n//min1+1):
        count+=len(s)
        for e in s:
            road-=e
            if road<0:
                count-=1
            road = save
    road = n-1
print(road)

Submission status: Runtime Error

Solution code:
import numpy as np

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

D = []

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

    for i in range(L, R+1):
        D.append(i)

D.sort()

dp = np.zeros(300000)
dp[1] = 1

for d in D:
    for i in range(1, N//d)
        dp += np.roll(dp, i * d)
    dp %= 998244353

print(int(dp[N]))

Submission status: Runtime Error

Solution code:
m = 998244353

N,K = map(int,input().split())
s=set()
for i in range(K):
    i1,i2 = map(int,input().split())
    s.update(set(range(i1,i2+1)))
memo = [-1]*(N+1)
def saiki(n):
    if n == 1:
        return 1
    elif n <=0:
        return 0
    elif memo[n] != -1:#use memo
        return memo[n]

    count = 0
    for i in s:
        count += saiki(n-i)
        count = count % m
    memo[n] = count
    
    return count
print(saiki(N))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b
def ceil(x):
    return math.ceil(x)
def floor(x):
    return math.floor(x)

def main():
    mod = 998244353
    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())

    S = set()
    for i in range(K):
        for j in range(L[i], R[i] + 1):
            S.add(j)

    dp = [0] * N
    dp[0] = 1
    for s in S:
        dp[s] += 1
    for i in range(N):
        if dp[i] != 0:
            for s in S:
                if i + s <= N - 1:
                    dp[i + s] += 1
    print(dp[N - 1] % mod)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

L.extend(R)
LR = list(set(L))

count = 0
for j in range(N):
  h = list(itertools.combinations_with_replacement(LR, j))
  print(h)

  for i in range(len(h)):
    if sum(h[i]) == N - 1:
      count += 1
      if len(h[i]) > 1:
        if h[i][0] != h[i][i]:
          count += 1

    
      
print(count)

Submission status: Runtime Error

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

S = []
for l, r in A:
    for i in range(l, r + 1):
        S.append(i)

dp = [0]*N
dp[0] = 1

for i in range(1, N):
    c = 0
    for j in S:
        if i - j >= 0:
            c += dp[i-j]
    dp[i] = c

print(dp[N-1]%998244353

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(2000)


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

S = list()
for l,r in LR:
  S.extend(list(range(l, r+1)))
S = sorted(S)

@lru_cache(maxsize=1000)
def an(n):
    if n == 1:
        return 1
    elif n < 1:
        return 0
    return sum([an(n-d)%998244353 for d in S])%998244353

print(an(N))

Submission status: Runtime Error

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

import numpy as np
from numba import njit,i8

N,K=map(int,readline().split())
DIV = 998244353
steps = []
for i in range(K):
  l,r = map(int,readline().split())
  for j in range(l, r + 1):
    steps.append(j)
    
steps = sorted(steps)
steps = np.array(steps, dtype = int)

@njit(i8(i8[:]),cache = True)
def solve(steps):
  dp = np.zeros(N, dtype = int)
  dp[0] = 1
  for i in range(len(dp)):
    for s in steps:
      if i + s >= len(dp):
        break
      dp[i + s] += dp[i]
      dp[i + s] %= DIV
      
  return dp[-1]

print(solve())

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
mod = 998244353
lr = []
for i in range(k):
  l,r = map(int,input().split())
  lr.append(l)
  lr.append(r)
S = list(set(lr))
n-=1
rout=0
def travel(n,S,rout):
  for s in S:
    if n<s:
      continue
    if n-s>0:
      return travel(n-s,S,rout)
    else:
      rout+=1
travel(n,S,rout)
print(rout%mod)

Submission status: Runtime Error

Solution code:
M=998244353
y=lambda:map(int,input().split())
n,k=y()
q=set()
for i in range(k):
    a,b=y()
    for j in range(a,b+1):q.add(j)
s=[(n,n+1)]
t=[[-1,-1]for i in range(n)]
t[0]=[1,0]
while s:
    v=s[-1][0]
    if t[v-1][1]<0:
        t[v-1][1]=0
        for i in q:
            if v-i>0:
                if t[v-i-1][0]>=0:t[v-1][0]+=t[v-i-1][0]
                else:s.append((v-i,v));t[v-1][1]+=1
    if t[v-1][1]==0:t[s[-1][1]][0]+=t[v-1][0];t[s[-1][1]][1]-=1;s.pop()
print(t[-1])

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(0) % 998244353)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import numpy as np
import sys
sys.setrecursionlimit(10**6)
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=np.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 functools
n, k = map(int, input().split())
s = set()
for i in range(k):
    k1, k2 = map(int, input().split())
    s.add(k1)
    s.add(k2)
@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:
N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]

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


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

    if n == 0:
        return 1

    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:
N, K = list(map(int, input().split()))
L = [list(map(int, input().split())) for i in range(K)]
LL=[]
for l in L:
    LL += l
S = set(LL)

c=['.' for i in range(N-1)]
c.append("g")
count=0

def dfs(x):
    global count
    if not (x < N):  #探索範囲外になった場合はreturn
        return
    if c[x] == "g":  # ゴールを見つけたらカウント
        count+=1

    for s in S:
        dfs(x + s)

dfs(0)
print(count % 998244353)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
s=[]
dp=[0,1]
for i in range(k):
  a,b=map(int,input().split())
  if b==n:
    s.extend(list(range(a,b)))
  else:
    s.extend(list(range(a,b+1)))
s.sort()
for i in range(2,n+1):
  tmp=0
  for j in s:
    if i-j>=1:
      tmp+=dp[i-j]
    else:
      break
  dp.append(tmp%998244353)
print(dp[-1])

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])-1:
            plot[a,posit+c]+=plot[a-1,posit]
xx=np.sum(plot[:,int(num[0])-1])
print(xx%998244353)

Submission status: Runtime Error

Solution code:
# ABC179-D Leaping Tak
goalN, shugosuK = map(int, input().strip().split(' '))
# print(goalN, shugosuK)
shugo = []
wa = []
for i in range(shugosuK):
    shugo = list(map(int, input().strip().split(' ')))
    # print('shugo', shugo)
    wa = wa + shugo
    # print('wa', wa)
    # wa = set(wa)
# print(wa)
wa = list(set(wa))
# print(wa)
l = len(wa)

def dfs(pos, cnt):
    for i in range(l):
        newpos = pos + wa[i]
        if newpos == goalN:
            pos = newpos
            cnt += 1
            return cnt
        elif newpos > goalN:
            pos = newpos
            return cnt
        elif newpos < goalN:
            pos = newpos
            dfs(pos, cnt)

cnt = dfs(1, 0)
cnt = cnt % 998244353
print(cnt)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list([1]+[0]*(n-1))
lst=[]
for i in range(k):
    x,y=map(int,input().split())
    lst+=list(range(x,y+1))

from functools import lru_cache
@lru_cache(maxsize = None)
def f()
    for j in lst:
        if j<=i:a[i]+=a[i-j]
for i in range(1,n):f()
print(a[-1]%998244353)

Submission status: Runtime Error

Solution code:
mod = 998244353
n, k = map(int, input().split())
lr = [list(map(int, input().split())) for i in range(k)]
dp = [0 for i in range(n + 1)]
dp[0] = 1
cum = [0, 1]
cur = [0 for i in range(k)]
for i in range(1, n + 1):
    cnt = 0
    for j in range(k):
        r = (i - (lr[j][1] - lr[j][0] + 1))
        l = r - (lr[j][1] - lr[j][0])
        print(l, r, cum)
        if l <= 0:
            continue
        cnt += cum[r] - cum[l - 1]
    dp[i] = dp[i - 1] + cnt
    cum.append(cnt + cum[-1])
print(dp[n])

Submission status: Runtime Error

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

d_set = set()

for k in range(K):
    L,R = map(int, input().split())
    d_set |= set(list(range(L,R+1)))

dp = [0] * (N+1)
# init
for d in d_set:
    dp[d] = 1

for i in range(N):
    for d in d_set:
        if i+d > N:
            d_set.remove(d)
        dp[i+d] += dp[i]

print(dp[N-1]%MOD)

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)]
list=[]
count=0
for j in range(K):
  for num in range(L[j],R[j]+1):
    list.append(num)
from collections import deque
que = deque()
for i in range(len(list)):
    que.append(list[i])

while que:
    seq = que.popleft()
    if sum(seq) == N:
      count+=1
    else:
      for i in range(list.index(seq[-1]), len(list)):
           seq_next = seq + list[i]
           que.append(seq_next)
print(count)

Submission status: Runtime Error

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

l = list(set(l))
dp = [0]*(n+1)
dp[1] = 1

for i in range(2, n+1):
    for j in l:
        cnt = 0
        sa = i-j
        if sa > 0:
            cnt += dp[i-j]
        dp[i] += cnt%998244353

print(dp[n]%998244353)

Submission status: Runtime Error

Solution code:
from numba import jit

import sys
sys.setrecursionlimit(10**9)

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


@njit
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)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
allowed_jump = [False for i in range(n)]
for i in range(k):
    l, r = map(int, input().split())
    for i in range(r-l+1):
        allowed_jump[l+i] = True
allowed_jump2 = []
for i in range(n):
    if allowed_jump[i]:
        allowed_jump2.append(i)
ans = [0 for i in range(n)]
ans[0]=1
for i in range(n):
    for jump in allowed_jump2:
        if i-jump>= 0:
            ans[i] += ans[i-jump]
print(ans[n-1]%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)]
list=[]
count=0
for j in range(K):
  for num in range(L[j],R[j]+1):
    list.append(num)
from collections import deque
que = deque()

que.append(最初の状態)  

for i in range(len(list)):
    que.append(list[i])

while que:
    seq = que.popleft()
    if sum(seq) == N:
      count+=1
    else:
      for i in range(list.index(seq[-1]), len(list)):
           seq_next = seq + list[i]
           que.append(seq_next)
print(count)

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):
    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:
from numba import njit

import sys
sys.setrecursionlimit(10**9)

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


@njit
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)

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 + 2)]


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

    if n == 0:
        return 1

    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:
n, k = map(int, input().split())
s = []
for i in range(k):
  l, r = map(int, input().split())
  for j in range(l, r+1):
    s.append(j)

dp = [-1 for i in range(n+1)]
    
def dfs(A):
  if (A < 0):
    return 0
  if (A == 0):
    return 1
  
  if (dp[A] >= 0):
    return dp[A]
 
  ans = 0
  for i in s:
    ans += dfs(A - i)
    ans %= 998244353
 
  dp[A] = ans
  return ans
if(n == 1):
  if(1 in s):
    print(1)
  else:
    print(0)
  exit()
    
print(dfs(n-1))

Submission status: Runtime Error

Solution code:
 import itertools

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

mod = 998244353

m_list = []

for _ in range(k):
    l, r = map(int, input().split())
    t_list = list(range(l,r+1))
    m_list.append(t_list)

m_list = list(itertools.chain.from_iterable(m_list))

dp = [0]*n
dp[0] = 1

for i in range(n):
    for j in range(len(m_list)):
        dp[i] += dp[i-m_list[j]]

print(dp[n-1] % mod)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
m = 998244353

N,K = map(int,input().split())
s=set()
for i in range(K):
    i1,i2 = map(int,input().split())
    s.update(set(range(i1,i2+1)))
memo = [0]*(N+1)
def saiki(n):
    if n == 1:
        return 1
    elif n <=0:
        return 0
    elif memo[n] != 0:#use memo
        return memo[n]

    count = 0
    for i in s:
        count += saiki(n-i)
        count = count % m
    memo[n] = count
    
    return count
print(saiki(N))

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
        return
    elif N < 0:
        return
    else:
        for x in S:
            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, S)
    print(cnt)

Submission status: Runtime Error

Solution code:
def count(n, S, memo):
    if n < 0:
        return 0
    elif n == 1:
        return 1
    elif memo[n] > -1:
        return memo[n]
    else:
        x = 0
        for s in S:
            x += count(n - s, S, memo)
        memo[n] = x
        return memo[n]


N, K = map(int, input().split())
S1 = set()
for i in range(K):
    L, R = map(int, input().split())
    S1.add(L)
    S1.add(R)
memo = [-1] * (N + 1)
print(count(N, S1, memo) % 998244353)

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


def dfs(n):
    if n < 0:  # あとマイナスマス（行き過ぎ）のとき
        return 0

    if n == 0:  # あと 0 マスのとき
        return 1

    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)  # あと N - d のとき何通り？を全部足す
            ans %= 998244353

    dp[n] = ans
    return dp[n]


print(dfs(N - 1))  # あと N - 1 マスのとき何通り？

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
def dfs(q, here, result):
	# print('q,here1: ', q, here, result)
	if len(q) == 0:
		print(result % 998244353)
		return result
	for i in num:
		# print('i, here: ', i, here)
		if i + here <= n:
			q.append(i + here)
		else:
			break
	# print('q,here2,result: ', q, here, result)
	here = q.pop()
	if here == n:
		result += 1
	dfs(q, here, result)

from collections import deque

n, k = (int(each) for each in input().split())
lr = []
global result
global num
global q
result = 0
num = []
for each in range(k):
	lr = [int(each) for each in input().split()]
	for i in range(lr[0], lr[1]+1):
		num.append(i)

q = deque([1])
dfs(q, 1, result)

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(a[0]) % 998244353)

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 < 1:
            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)

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])-1:
	          plot[a,posit+c]+=plot[a-1,posit]
xx=int(np.sum(plot[:,int(num[0])-1]))
if xx>998244353:
  print((xx+1)%998244353)
else:
  print(xx)

Submission status: Runtime Error

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

LR = [list(map(int, input().split())) for i in range(K)]
S = set()
for i in LR:
    for j in range(i[0], i[1]+1):
        S.add(j)
L = sorted(list(S))
print(L)

dp = [0 for i in range(N)]
dp[0] = 1
for i in range(1, N):
    x = bisect.bisect(L, i)
    t = L[:x]
    for j in t:
        dp[i] += dp[i-j]

print(dp[-1] % 998244353)

Submission status: Runtime Error

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

for _ in range(K):
  L, R = map(int, input().split())
  ints = list(set(ints) | set(list(range(L, R + 1))))
  
import numpy as np
ints = np.array(ints)
orig_ints = ints.copy()
ints += 1
count = 0
count += (ints == N).sum()



for k in range(N):
  y, x = np.meshgrid(orig_ints, ints)
  ints = y + x
  #print(y.shape, x.shape)
  #print(ints)
  count += (ints == N).sum()
  
print(count)

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):
    if n == 0:
        return 1
    elif n < 0:
        return 0
    for i in num_set:
        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:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def countWays(arr, m, N):
    count = [0 for i in range(N + 1)]

    # base case
    count[0] = 1

    # Count ways for all values up
    # to 'N' and store the result
    for i in range(1, N + 1):
        for j in range(m):

            # if i >= arr[j] then
            # accumulate count for value 'i' as
            # ways to form value 'i-arr[j]'
            if (i >= arr[j]):
                count[i] += count[i - arr[j]]%998244353
				count[i]%=998244353
                # required number of ways
    return count[N]%998244353


n, k = MAP()
temp = []
for _ in range(k):
    u, v = MAP()
    temp += list(range(u, v + 1))
# print(temp)

print(countWays(temp, len(temp), n-1)%998244353)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
LR = set()
MOD = 998244353

for i in range(K):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        LR.add(j)
#print(list(LR))


class Search:
    def __init__(self):
        self.ans = 0

    def dfs(self, now):
        if now == N:
            self.ans += 1
            return
        if now > N:
            return
        for d in LR:
            self.dfs(d + now)


s = Search()
s.dfs(1)
print(s.ans % MOD)

# LR = [list(map(int,input().split())) for i in range(N)]
# dp = [0] * (N + 1)
# dp[0] = 1
# for i in range(1, N):
#     for d in LR:
#         if i - d < 0: break
#         dp[i] += (dp[i - d]) % MOD
# print(dp[N-1] % MOD)

Submission status: Runtime Error

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

dp = [-1 for i in range(n+1)]
    
def dfs(A):
  if (A < 0):
    return 0
  if (A == 0):
    return 1
  
  if (dp[A] >= 0):
    return dp[A]
 
  ans = 0
  for i in s:
    ans += dfs(A - i)
    ans %= 998244353
 
  dp[A] = ans
  return ans

print(dfs(n-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):
    if table[x] != 0:
        return table[x] 
    else:
        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] %= mod
        return table[x]

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

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):
    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 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(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):
    if dp[n]!=0:
        return dp[n]
    if n==0:
        return 1
    if 0<n<S[0]:
        return 0
    x=0
    for s in range(S):
        if n-s > 0:
             x += Leaping_Tak(n-s,S)
    dp[n]=x
    return x%mod

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

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

counted = {}
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 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:
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) * 2)
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 input_int():
    return(int(input()))

def input_int_list():
    return(list(map(int,input().split())))

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

def run():
    n, k = input_int_map()

    k_set = set()

    ranges = []

    for _ in range(k):
        l, r = input_int_map()
        ranges.append((l, r))

    # k_list = list(k_set)

    result = find_pettern(n - 1, ranges, {})
    result = result % 998244353
    print(result)

def find_pettern(n: int, ranges: [(int, int)], memo: {}) -> int:

    if n < 0:
        return 0

    if n == 0:
        return 1

    if n in memo:
        return memo[n]

    count_num = 0
    for k in ranges:
        for i in range(k[0], k[1] + 1):
            count_num += find_pettern(n - i, ranges, memo)

    memo[n] = count_num

    return count_num

run()