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: Time Limit Exceeded

Solution code:
from sys import stdin, stdout
import heapq
import cProfile
from collections import Counter, defaultdict, deque
from functools import reduce
import math
import threading
import sys
import time


def get_int(): return int(stdin.readline().strip())


def get_tuple(): return map(int, stdin.readline().split())


def get_list(): return list(map(int, stdin.readline().split()))

mod = 998244353
n,k = get_tuple()
st = list()
for _ in range(k):
    x,y = get_tuple()
    st.append([x,y])

dp = [1]
pref_sum = 1
last_val = 0
for i in range(1,n):
    curr_sum = 0
    for x,y in st:
        if i-x>=0:
            curr_sum += dp[i-x]
        if i - y >= 1:
                curr_sum -= dp[i - y - 1]
    pref_sum += curr_sum
    last_val = curr_sum
    dp.append(pref_sum)
diff = (dp[-1]-dp[-2])
if diff>0:
    print(diff%mod)
else: print(0)
# print(pref_sum)
# print(st,dp)
# print(dp[n-2]%mod)

Submission status: Time Limit Exceeded

Solution code:
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))

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]
    dp[i] = dp[i] % 998244353

print(dp[-1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
s=[]
dp=[0]*(n+5)
for i in range(k):
     l,r =map(int,input().split())
     s.append([l,r])
      
s.sort()
dp[0]=1
dp[s[0][0]]=1
for i in range(s[0][0]+1,n):
    for j in s:
        if j[0]>i:
            break
        for k in range(j[0],j[1]+1):
            if i< k:
                break
            else:
                dp[i]+= dp[i-k] 
                dp[i] %= 998244353
print(dp[n-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
MOD = 998244353
N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]

S = list()
for lr in LR:
    for i in range(lr[0], lr[1]+1):
        S.append(i)

dp = [0]*(N+1) # dp[i] : iに行く方法
dp[1] = 1

memo1 = deque()
memo2 = deque()

for i in range(1, N+1):
    # for s in S:
    #     if i + s <= N:
    #         dp[i + s] += dp[i]
    #         dp[i + s] %= MOD
    while(len(memo1)):
        # l = m[1]
        # r = m[2]
        m = memo1.popleft()
        if m[1] <= i and i <= m[2]:
            dp[i] += m[0]
            dp[i] %= MOD
        
        if not(m[2] < i):
            memo2.append(m)
    
    while(len(memo2)):
        tmp = memo2.popleft()
        memo1.append(tmp)
    
    for lr in LR:
        memo1.append([dp[i], lr[0] + i, lr[1] + i])
    
print(dp[N])

Submission status: Time Limit Exceeded

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

for _ in range(K):
  L, R = map(int, input().split())
  S.extend(range(L,R+1))
  
S.sort()

DP =[0]*N
DP[0] = 1

for i in range(N-1):
  if i + S[0] >= N:
    break
  if DP[i] == 0:
    pass
  else:
    for j in S:
      if i+j<N:
        DP[i+j] += DP[i]
      else:
        break

print(DP[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
p = 998244353
N, K = map(int, input().split())
lst = [tuple(map(int, input().split())) for i in range(K)]
lstd = []
for i in range(K):
    lstd.extend(list(range(lst[i][0], lst[i][1]+1)))

lstd.sort()

dp=[[0] * (N+1) for j in range(N+1)]
#初期化
for i in lstd:
    dp[i][1] = 1

for k in range(2, N):
    for m in range(k, N):
        for d in lstd:
            if d >= m:
                break
            else:
                dp[m][k] = (dp[m][k] + dp[m-d][k-1]) % p
answer = 0
for i in range(1, N):
    answer = (answer + dp[N-1][i]) % p
print(answer)

Submission status: Time Limit Exceeded

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

S = []

for i in range(K):
    for j in range(L[i][0], L[i][1] + 1):
        S.append(j)

S.sort()

dp = [0] * N

for x in range(N):
    for y in S:
        if x > y:
            dp[x] += dp[x - y]

    if x in S:
        dp[x] += 1

print(dp[N - 1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np

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


S = []
for k in range(K):
    for i in range(LR[k][0], LR[k][1] + 1):
        S.append(i)
min_S = min(S)
memo = [-1 for _ in range(N)]

def move(x):
    res = -1
    if memo[x] != -1:
        res = memo[x]
        return res
    elif x < 0:
        res = 0
    elif x == 0:
        res = 1
    else:
        tmp = 0
        S_cand = [s for s in S if s <= x]
        for s in S_cand:
            if x-s == 0 or x-s >= min_S:
                tmp += move(x - s)
        res = tmp
    if x >= 0:
        memo[x] = res
    return res

for i in range(min(10, N)):
    move(i)
res =  move(N - 1) % 998244353
print(res)
# print(memo)

Submission status: Time Limit Exceeded

Solution code:
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


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: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
l = []
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(1, n+1):
    for j in l:
        if i+j < n+1:
            dp[i+j] += dp[i]%998244353

print(dp[n]%998244353)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    import numpy as np

    N, K = map(int, input().split())
    S = set()
    section = []
    for _ in range(K):
        l, r = map(int, input().split())
        section.append((l, r + 1))
        for n in range(l, r + 1):
            S.add(n)
    MOD = 998244353

    dp = np.zeros(N, dtype=np.int64)
    dp[0] = 1
    for i in range(N):
        # for d in S:
        #     if i >= d:
        #         dp[i] += dp[i - d] % MOD
        for left, right in section:
            right = min(i + right, N)
            left = i + left
            dp[left:right] += dp[i]
    print(dp[-1] % MOD)
    # print(dp)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split(" "))
a=[]
d=[]
e=[]
for k in range(K):
    l,r=map(int,input().split(" "))
    d.append(l)
    e.append(r)
d.sort()
e.sort()
for k in range(K):
    a+=list(range(d[k],e[k]+1))
a.sort()
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%998244353)
print(b[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import numpy as np
n, k = map(int, input().split())
s_list = []
a_list = np.zeros((n + 1) * 2, dtype=int)
a_list[1] = 1
for i in range(k):
    l, r = map(int, input().split())
    s_list.append([l, r + 1])

for i in range(1, n):
    a_list[i] %= 998244353
    if a_list[i] == 0:
        continue
    for l, r in s_list:
        if i + l > n:
            continue
        if i + r > n + 1:
            a_list[(i+l):(n+1)] += a_list[i]
        else:
            a_list[(i+l):(i+r)] += a_list[i]
print(a_list[n] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
L = [0] * K
R = [0] * K
S = set()
for k in range(K):
    L[k],R[k] = map(int,input().split())
for k in range(K):
    for n in range(L[k], R[k] + 1):
        S.add(n)
dp = [0] * (N+1)
dp[1] = 1
S = sorted(S)
for i in range(1,N+1):
    for s in S:    
        if i-s <= 0:
            break
        dp[i] += dp[i-s]
        if dp[i] >= 498244353:
            dp[i] -= 998244353
while dp[N] >= 998244353:
    dp[N] -= 998244353
while dp[N] < 0:
    dp[N] += 998244353    
print(dp[N])

Submission status: Time Limit Exceeded

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
                
    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: Time Limit Exceeded

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))
for i in range(1,n):
    for j in lst:
        if j<=i:a[i]+=a[i-j]
print(a[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
dp = [0 for i in range(n)]

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

s = sorted(s)

dp[0] = 1
for i in range(n):
  for a in s:
    if i+a < n:
      dp[i+a] = (dp[i+a] + dp[i]) % 998244353

print(dp[-1])

Submission status: Time Limit Exceeded

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

dp = [0] * (N+1)
mv = list()
for i in range(K):
    l, r = list(map(int, input().split()))
    for j in range(l, r+1):
        mv.append(j)

def solve(N, dp, mv):
    for i in range(1, N+1):
        for j in range(len(mv)):
            if i+mv[j]>N: break
            if dp[i] == 0: continue
            dp[i+mv[j]] = (dp[i+mv[j]] + dp[i]) % MOD

dp[1] = 1
mv.sort()
solve(N, dp, mv)

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 8)


N, K = map(int, input().split())
M = 998244353
S = set()
for _ in range(K):
    L, R = map(int, input().split())
    for i in range(L, R + 1):
        S.add(i)


@lru_cache(None)
def dp(i):
    if i < 1:
        return 0
    elif i == 1:
        return 1
    else:
        res = 0
        for d in S:
            res += dp(i - d)
            res %= M
        return res
print(dp(N) % M)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
LR = set()
MOD = 998244353
import sys
sys.setrecursionlimit(10**6)

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: Time Limit Exceeded

Solution code:
def dfs():
    pass


def main():
    n,k = map(int, input().split())
    dl = []
    for _ in range(k):
        l,r = map(int, input().split())
        for i in range(l,r+1):
            dl.append(i)

    dl.sort()
    MOD = 998244353
    dp = [0]*(n+1)
    dp[1] = 1
    for i in range(n):
        for d in dl:
            if i+d > n:break
            dp[i+d] += dp[i]
            dp[i+d]%=MOD

    print(dp[n])



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = []
for _ in range(K):
    x, y = map(int, input().split())
    for i in range(x, y+1):
        S.append(i)
S.sort()
S_use = []
len_S = len(S)
now = 0
ALL = [0] * (N)
ALL[0] = 1
for i in range(N):
    if now < len_S:
        if S[now] < i+1:
            S_use.append(S[now])
            now += 1
    for k in S_use:
        ALL[i] += ALL[i-k]
        ALL[i] = ALL[i] % 998244353
print(ALL[N-1])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
s=[]
ans=0
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
  tmp%=998244353
  dp.append(tmp)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, K = map(int, input().split())
MOD = 998244353
dp = [0 for _ in range(N)]
dp[0] = 1

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

for i in range(N):
    tmp = dp[i]
    for k in range(K):
        if i+L[k] < N:
            for d in range(L[k], R[k]+1):
                if i+d < N:
                    dp[i+d] += tmp
                    dp[i+d] %= MOD

ans = dp[N-1] % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
readline = stdin.readline
def i_input(): return int(readline().rstrip())
def i_map(): return map(int, readline().rstrip().split())
def i_list(): return list(i_map())

MOD = 998244353

import numpy as np
from numba import jit

@jit
def main():
    N, K = i_map()
    S = set()
    dp = np.zeros(N + 1, dtype=int)
    for _ in range(K):
        L, R = i_map()
        S = S | set(range(L, R + 1))
    S = list(S)
    S.sort()
    dp[1] = 1
    for n in range(2, N + 1):
        for s in S:
            if n - s >= 1:
                dp[n] += dp[n - s] % MOD
            else:
                break
    print(dp[N] % MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 8)


N, K = map(int, input().split())
M = 998244353
S = set()
for _ in range(K):
    L, R = map(int, input().split())
    for i in range(L, R + 1):
        S.add(i)


@lru_cache(None)
def dp(i):
    if i < 1:
        return 0
    elif i == 1:
        return 1
    else:
        res = 0
        for d in S:
            res += dp(i - d)
            res %= M
        return res
print(dp(N) % M)

Submission status: Time Limit Exceeded

Solution code:
import sys
#import string
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np
#import sympy

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    elif x == 0:
            return default
    else:
        return my_index(l,x-1)

def solve():
    #n = int(stdin.readline().rstrip())
    n,k = map(int, stdin.readline().rstrip().split())
    #l = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    s = []
    for i in range(k):
        l,r = map(int, stdin.readline().rstrip().split())
        for j in range(l,r+1):
            s.append(j)
    s.sort()
    points = [0] * n
    points[-1] = 1
    index = 0

    for i in range(n-2,-1,-1):
        if s[0] > n-1-i:
            continue
        p=0
        for j in range(index+1):
            p += points[i+s[j]]
        points[i] = p
        if index == len(s)-1:
            continue
        elif s[index + 1] == n-i:
            index += 1

    print(points[0]%998244353)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

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

for i in range(n):
  for j in S:
    if i+j < n:
      dp[i+j] += dp[i]
      dp[i+j] = dp[i+j]%998244353
      
print(dp[n-1]%998244353)

Submission status: Time Limit Exceeded

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

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

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

S = []

for left, right in L:
    S.extend(range(left, right+1))

S = sorted(list(set(S)))

n_list = [0] * N
n_list[0] = 1

for idx, value in enumerate(n_list):
    if S[0] + idx >= N:
        break
    if value == 0:
        continue
    for s in S:
        next_idx = s + idx
        if next_idx >= N:
            break
        n_list[next_idx] += value

print(n_list[-1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    mod = 998244353
    dp = [0] * (n + 1)
    dp[1] = 1
    delta = []
    for _ in range(k):
        l, r = map(int, input().split())
        for i in range(l, r + 1):
            delta.append(i)
    delta.sort()
    for i in range(n):
        for d in delta:
            if i + d > n:
                break
            dp[i + d] += dp[i]
            dp[i + d] %= mod
    print(dp[n])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
input = sys.stdin.readline
read = lambda: list(map(int, input().strip().split()))

MOD = 998244353
def main():
	arr = []
	n, k = read()
	for _ in range(k):
		a, b = read()
		arr.extend(range(a, b+1))
	# arr.sort()
	dp = [0]*(n+1)
	dp[1] = 1
	for j in range(1, n+1):
		for i in arr:
			if j >= i:
				dp[j] += dp[j-i]
				dp[j] %= MOD
			# else:
			# 	break
		# print(i, dp)
	print(dp[n])

		



	

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
lis = [list(map(int,input().split())) for _ in range(K)]
 
T = []
 
for i in range(K):
    for j in range(lis[i][0],lis[i][1]+1):
        T.append(j)
        if i==0:
            S = set(T)
        else:
            S = S | set(T)
    T = []
 
lis = list(S)
dp  = [0]*(N+1)
dp[1] = 1
MOD = 998244353
 
for i in range(2,N+1):
    for j in lis:
        if i>j:
            dp[i] += dp[i-j]

print(dp[N]%MOD)

Submission status: Time Limit Exceeded

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

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

ls = []
mod = 998244353

for _ in range(K):
    l, r = map(int, input().split())
    for i in range(l, r + 1):
        ls.append(i)

dp = [0] * (N + 1)
dp[1] = 1

ls.sort()

for j in range(1, N):
    for x in ls:
        if x + j > N:
            break
        else:
            dp[x + j] += dp[j] % mod
            dp[x + j] %= mod

print(dp[N] % mod)
# print(dp)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

N,K=map(int,input().strip().split())
inf=998244353
S=[]
for _ in range(K):
    L,R=map(int,input().strip().split())
    for i in range(L,R+1):
        S.append(i)

dp=[-1 for _ in range(N)]
dp[0]=1
def rec(n,S,dp):
    if dp[n-1]!=-1:
        return dp[n-1]
    else:
        dp[n-1]=0
        for j in range(len(S)):
            x=n-S[j]
            if x>0:
                if dp[x-1]!=-1:
                    dp[n-1]+=dp[x-1]%inf
                else:
                    dp[x-1]=rec(x,S,dp)
                    dp[n-1]+=dp[x-1]
        dp[n-1]=dp[n-1]%inf
        return dp[n-1]

print(rec(N,S,dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)

def main():
    mod = 998244353

    N, K = map(int, sys.stdin.readline().strip().split())

    step = []
    for _ in range(K):
        L, R = map(int, sys.stdin.readline().strip().split())
        step.append((L, R))
    step.sort(reverse=True)

    dp = [False] * (N + 1)
    dp[1] = 1
    dp[0] = 0


    def solve(u):
        if u <= 0:
            return 0

        if dp[u] is not False:
            return dp[u]
        
        dp[u] = 0
        for L, R in step:
            R = min(R, u)
            L = min(L, u)

            for i in range(L, R + 1):
                dp[u] += solve(u - i)

        return dp[u]


    solve(N)

    print(dp[-1] % mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import sys
import itertools

from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)
mod = 998244353

n, k = map(int, input().split())
s = []
l = []
r = []

for i in range(k):
    l_,r_ = map(int, input().split())
    l.append(l_)
    r.append(r_+1)
    # s = s + list(range(l,r+1))

dp = [0] * 2*n
dp[n] = 1
# print(dp)

for i in range(n+1, 2*n):
    cumsum = list(itertools.accumulate(dp))
    for j in range(k):
        # print(i-r[j]+1,i-l[j]+1)
        # print(j, dp[i-r[j]+1:i-l[j]+1])
        dp[i] += cumsum[i-l[j]]-cumsum[i-r[j]] % mod
# print(dp)
print(dp[2*n-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(k)]

ab.sort()

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

for i in range(1,n):
    res = 0
    for j in ab:
        if j[0] > i:
            break
        elif j[1] >i:
            res += sum(dp[0:(i-j[0])+1])
        else:
            res += sum(dp[(i-j[1]):(i-j[0])+1])
    dp[i] = (dp[i] +res) % 998244353 

print(dp[n-1]%998244353 )

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(k)]
MOD = 998244353
cand = []
for l, r in lr:
    for i in range(l, r+1):
        cand.append(i)
cand.sort()
# print(cand)
dp = [0] * (n+1)
dp[0] = 1
for i in range(1, n+1):
    tmp = 0
    for num in cand:
        if i - num >= 0:
            tmp += dp[i-num]
            tmp %= MOD
        else:
            dp[i] = (tmp % MOD)
            break
    dp[i] = (tmp % MOD)
print(dp[-2])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import math
import itertools

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,k = readInts()
pos = set()
for _ in range(k):
	l,r = readInts()
	for i in range(l,r+1):
		pos.add(i)

pos = sorted(list(pos))

dp = [-1]*(n+1)
dp[n]=1
ans = 0
for i in range(n-1,0,-1):
	t = 0
	for j in pos:
		if n-i>=j:
			t+=dp[i+j]
		else:
			break
	dp[i]=t%998244353

print(dp[1])

Submission status: Time Limit Exceeded

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

MOD = 998244353  # type: int


def solve(N: int, K: int, L: "List[int]", R: "List[int]"):
    dp = [0] * (N + 1)
    dp[1] = 1
    # s = []
    # for i in range(K):
    #     for j in range(L[i], R[i]+1):
    #         s.append(j)
    # s.sort()
    for i in range(1, N+1):
        # for j in s:
        for s in range(K):
            for j in range(L[s], R[s]+1):
                if i - j >= 1:
                    dp[i] += dp[i-j]
                    dp[i] %= MOD
                else:
                    break
    print(dp[N]%MOD)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    L = [int()] * (K)  # type: "List[int]"
    R = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    solve(N, K, L, R)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np

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


S = []
for k in range(K):
    for i in range(LR[k][0], LR[k][1] + 1):
        S.append(i)
min_S = min(S)
memo = [-1 for _ in range(N)]

def move(x):
    res = -1
    if memo[x] != -1:
        res = memo[x]
        return res
    elif x < 0:
        res = 0
    elif x == 0:
        res = 1
    else:
        tmp = 0
        S_cand = [s for s in S if s <= x]
        for s in S_cand:
            if x-s == 0 or x-s >= min_S:
                tmp += move(x - s)
        res = tmp
    if x >= 0:
        memo[x] = res
    return res

for i in range(N):
    move(i)
res =  move(N - 1) % 998244353
print(res)
# print(memo)

Submission status: Time Limit Exceeded

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

lr.sort( key = lambda x:x[0])

masu = [0 for i in range(n)]
masu[0] = 1

for i in range(1,n):
    for j in lr:
        if i - j[0] >= 0:
            for k in range(j[0],min(i+1, j[1])+1):
                masu[i] += masu[i-k]
                masu[i] %= 998244353
        else:
            break

print(masu[-1])

Submission status: Time Limit Exceeded

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

dp = [0] * (N + 1)
dp[1] = 1

for i in range(2, N+1):
    sum_list = [0 for L, R in S]

    j = 0
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if sum_list[j] == 0:
            t = sum(dp[LL:RR+1])
            sum_list[j] = t
            dp[i] += t
        else:
            if LL >= 2:
                sum_list[j] -= dp[1]
            sum_list[j] += dp[RR]
            dp[i] += sum_list[j]
        j += 1

    dp[i] %= MOD

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:

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

kukan = ([0] * (N + 1))
# make table of number
for i in range(K):
    left, right = map(int, input().split())
    kukan[left:right + 1] = [1] * (right - left + 1)
key = []
for i in range(len(kukan)):
    if kukan[i] == 1:
        key.append(i)
# not using kukan after here
dp = [0] * N
dp[0] = 1
# max N*N
for i in range(N):
    for num in key:
        if (i + num) <= N - 1:
            dp[i + num] += dp[i]
        else:
            break
print(dp[N - 1] % (998244353))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
MOD = 998244353
nums = []
for _ in range(K):
    inp = list(map(int, input().split()))
    nums += [i for i in range(min(inp), max(inp) + 1)]
nums = list(set(nums))


ns = [0 for _ in range(N)]
ns[0] = 1
for i in range(1, N):
    for j in range(0, i):
        if i - j in nums:
            ns[i] += ns[j]
print(ns[-1] % MOD)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
L = []
R = []
for _ in range(K):
  l, r = map(int, input().split())
  L.append(l)
  R.append(r)
L.sort()
R.sort()
DP = [0] * N
DP[0] = 1

for i in range(N):
  for j in range(len(L)):
    for k in range(L[j], R[j] + 1):
      if 0 <= i - k < N:
        DP[i] += DP[i - k]
print(DP[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
N, K = map(int, input().split())
s = set()
for i in range(K):
    l, r = map(int, input().split())
    s.add(l)
    s.add(r)
s = list(s)
ans = [0]
def deepsearch(i):
    if N == i:
        ans[0] += 1
        return 0
    elif N < i:
        return 0
    else:
        for j in s:
            deepsearch(i+j)


deepsearch(1)
print(ans[0]%998244353)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
numl = []
for i in range(K):
  l, r = map(int, input().split())
  numl = numl + list(range(l, r+1))
numl.sort()
#print(numl)
ans = [0] * N
ans[0] = 1
for i in range(N-1):
  for j in numl:
    if i + j < N:
      ans[i + j] = (ans[i + j] + ans[i]) % 998244353
    else:
      break
print(ans[N-1])

Submission status: Time Limit Exceeded

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

mod = 998244353

for _ in range(K):
    L, R = map(int,input().split())
    # for d in range(L, R+1):
    #     moves.append(d)
    moves.append((L, R))
moves.sort()

dp = [0] * (N + 1)
dp[1] = 1
# for dis in moves:
#     dp[dis] = 1
# print(moves)

for n in range(1, N+1):
    for L, R in moves:
        if n - L <= 0 :
            break
        for dis in range(L, R+1):
            if n - dis >= 1:
                dp[n] += dp[n - dis]
            else:
                break

# print(dp)
print(dp[N] % mod)