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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 998244353


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, SS):
    count = [-1] * (N + 10)
    count[0] = 1

    ds = []
    for left, right in SS:
        for i in range(left, right + 1):
            ds.append(i)

    for pos in range(1, N):
        ret = 0
        for i in ds:
            j = pos - i
            if j < 0:
                continue
            ret += count[j]
        count[pos] = ret % MOD

    # ret = f(N - 1)
    ret = count[N - 1]
    return ret % MOD


def main():
    # parse input
    N, K = map(int, input().split())
    SS = []
    for i in range(K):
        SS.append(tuple(map(int, input().split())))
    print(solve(N, K, SS))


# tests
T1 = """
5 2
1 1
3 4
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
4
"""

T2 = """
5 2
3 3
5 5
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
0
"""

T3 = """
5 1
1 2
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
5
"""

T4 = """
60 3
5 8
1 3
10 15
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
221823067
"""

T5 = """
10 1
1 2
"""
TEST_T5 = """
>>> as_input(T5)
>>> main()
55
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=[0 for i in range(2*10**5+1)]
A[1]=1
S=set()
for i in range(K):
  L,R=map(int,input().split())
  for i in range(L,R+1):
    S.add(i)
import copy
mod=998244353
for i in range(1,N):
  temp=S.copy()
  for j in S:
    if j+i>N:
      temp.remove(j)
    else:
      A[j+i]+=A[i]
      A[j+i]%=mod
  S=temp
    
    
print(A[N])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

S = set()
for _ in range(K):
  l, r = map(int, input().split())
  S |= set(range(l, r + 1))

D = np.zeros(N, dtype=int)
D[0] = 1

for n in range(N):
  for s in S:
    if n >= s:
      i = n - s
      D[n] += D[i] % 998244353
      
print(D[N - 1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()
    dp = [0] *(N+1)
    dp[1] = 1
    for i in range(2, N + 1):
        for l,r in LR:
            if i-l>0:
                dp[i] += sum(dp[max(1,i-r):min(N,i-l+1)]) % M
                dp[i] %= M
            else:
                break
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
s = set()
for i in range(k):
    l,r = list(map(int, input().split()))
    L = [i for i in range(l,r+1)]
    s = set(L+list(s))
dp=[0]*(n+1)
dp[1] = 1
p = 998244353

for i in range(1, n):
    for j in s:
        if i+j > n:
            continue
        dp[i+j] += (dp[i])
        dp[i+j] %= p

print(dp[n] % p)

Submission status: Time Limit Exceeded

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,N):
  res.append(sum(res[i-v] for v in As if i-v >= 0)%998244353)
print(res[-1])

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())
    for j in range(l, r + 1):
        S.append(j)

dp = [0] * N * 10

dp[1] = 1

# for i in range(2, N + 1):
#     count = 0
#     for s in S:
#         if i > s:
#             count = (count + dp[i - s]) % 998244353
#     dp[i] += count % 998244353

for i in range(1, N + 1):
    if dp[i] == 0:
        continue
    for s in S:
        if i + s <= N + 1:
            dp[i + s] = (dp[i + s] + dp[i]) % 998244353

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
N,K=map(int,input().split())
mod = 998244353
 
div = set()
for _ in range(K):
  l,r = map(int,input().split())
  for i in range(l,r+1):
    div.add(i)
min_step = min(div)
dp = [-1]*N
dp[0] = 1
def calc(i):
  if dp[i] >= 0: return dp[i]
  #if i < min_step: dp[i]=0; return dp[i]
  if i < min_step: return 0
  tmp = 0
  for j in div:
    if j > i: continue
    dp[i-j] = calc(i-j)
    tmp = (tmp + dp[i-j])%mod
  dp[i] = tmp
  return tmp
print(calc(N-1)%mod)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
lr = []
dp = [0] * N
dp[0] = 1

for _ in range(K):
  l, r = map(int, input().split())
  lr += list(range(l, r + 1))
  
for i in range(0, N - 1):
  if dp[i] == 0:
    continue
    
  for j in range(len(lr)):
    if i + lr[j] > N - 1:
      continue
      
    dp[i + lr[j]] += dp[i]
    
print(dp[N - 1] % 998244353)

Submission status: Time Limit Exceeded

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

    LL.append(L)
    RR.append(R + 1)


keep = 0
dp = [0] * 2 * N
dp[N] = 1
for i in range(1, N):
    for j in range(K):

        keep += (dp[N + i - LL[j]] - dp[N + i - RR[j]])

    dp[N + i] += keep
print(dp[2 * N - 1] % 998244353)

Submission status: Time Limit Exceeded

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

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

dp = [0] * N
dp[0] = 1
for i in range(1, N):
    dpi = 0
    for l, r in D:
        if i - l < 0:
            continue
        r = max(0, i - r)
        l = max(0, i - l + 1)
        dpi += sum(dp[r:l])
    dp[i] = dpi % MOD

print(dp[N-1])

Submission status: Time Limit Exceeded

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

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

# O(N)で解く！
# N-1個目のマスまでdp
for i in range(N-1):
  for j in range(K):
    for k in range(X[j][0], X[j][1]+1):
      if 0 <= i + k <= N-1:
        dp[i+k] += dp[i]
        dp[i+k] %= mod
      else: continue

print(dp[N-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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

steps = tuple(steps)
mod = 998244353

d = dict()
d[0] = 1
for i in range(1, N):
    c = 0
    for s in steps:
        if i - s >= 0:
            c += d[i - s]
            c %= mod
    d[i] = c

print(d[N-1])

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

def main():
    N, K = i_map()
    S = set()
    dp = [0] * (N + 1)
    for _ in range(K):
        L, R = i_map()
        S = S | set(range(L, R + 1))
    dp[1] = 1
    for n in range(1, N + 1):
        if dp[n] == 0:
            continue
        for s in S:
            if n + s <= N:
                dp[n + s] += dp[n] % MOD
    print(dp[N] % MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

sys.setrecursionlimit(N * 3)

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

Solution code:
n, k = map(int,input().split())
S = []
mod = 998244353
for i in range(k):
  l,r  = map(int,input().split())
  S += list(range(l,r+1))
S = sorted(S)
dp = [0]*(n+1)
#print(S)
dp[1] = 1
for i in range(2,n+1):
  for s in S:
    if i-s<1:
      break
    dp[i] += dp[i-s]
    dp[i] %= mod
    
print(dp[n])

Submission status: Time Limit Exceeded

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

arr={0}
for i in range(K):
    a,b=map(int,input().split())
    arr|=set([j for j in range(a,b+1)])

arr.discard(0)


dp=[[0]*N for i in range(N)] 
dp[0][0]=1

ans=0
for i in range(N):
    for j in range(i,N):
        for k in arr:
            if dp[i][j]!=0 and j+k<=N-1:
                dp[i+1][j+k]+=dp[i][j]
    ans+=dp[i][-1]
            
print(ans%998244353)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
LR=set()
inf_=998244353
dp=[0]*(N+100)
dp[1]=1

for i in range(K):
    mini,maxi=map(int,input().split())
    list_=[j for j in range(mini,maxi+1)]
    LR = LR |set(list_)
li=list(LR)
for i in range(2,N+1):
    for j in li:
        try:
            dp[i]+=dp[i-j]
        except IndexError:
            break
print(dp[N]%inf_)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 998244353


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, SS):
    count = [-1] * (N + 10)
    count[0] = 1

    ds = []
    for left, right in SS:
        for i in range(left, right + 1):
            ds.append(i)

    for pos in range(1, N):
        ret = 0
        for i in ds:
            j = pos - i
            if j < 0:
                continue
            ret += count[j]
        count[pos] = ret

    # ret = f(N - 1)
    ret = count[N - 1]
    return ret % MOD


def main():
    # parse input
    N, K = map(int, input().split())
    SS = []
    for i in range(K):
        SS.append(tuple(map(int, input().split())))
    print(solve(N, K, SS))


# tests
T1 = """
5 2
1 1
3 4
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
4
"""

T2 = """
5 2
3 3
5 5
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
0
"""

T3 = """
5 1
1 2
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
5
"""

T4 = """
60 3
5 8
1 3
10 15
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
221823067
"""

T5 = """
10 1
1 2
"""
TEST_T5 = """
>>> as_input(T5)
>>> main()
55
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Time Limit Exceeded

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

N = 2 * n
# N: 処理する区間の長さ

data0 = [0]*(N+1)
data1 = [0]*(N+1)

mod = 998244353
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        x %= mod
        data[k] += x
        data[k] %= mod
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1)%mod)
    _add(data0, r, x*(r-1)%mod)
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def _get(data, k):
    s = 0
    while k:
        s += data[k]
        s %= mod
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

add(1, 2, 1)
for i in range(n):
    now = query(i+1, i+2) 
    for l, r in lrl:
        add(l+i+1, r+i+2, now % mod)

print(query(n, n+1) % mod)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
s = []
for _ in range(k):
    a,b = map(int,input().split())
    for i in range(a,b+1):
        s.append(i)
goal = n-1
flist = [0 for _ in range(n)]#flist[i]でf(i)の値

flist[0] = 1
for current in range(n):
    if flist[current] != 0:
        for num in s:
            if current+num <= n-1:
                flist[current+num] += flist[current]

print(flist[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

@njit
def solve(dpt, N, move, MOD):
    for i in range(N):
        for m in move:
            if i + m < N:
                dpt[i+m] = dpt[i] + dpt[i+m]
                dpt[i+m] %= MOD
    return dpt[N-1]

def main():
    MOD = 998244353

    N, K = map(int, input().split())
    move = []
    for i in range(K):
        l, r = map(int, input().split())
        move.extend(list(range(l, r+1)))
    move = np.array(move)
    dpt = np.zeros(N, dtype='int64')
    dpt[0] = 1

    print(solve(dpt, N, move, MOD))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def fun(a, n):   
    count = [0 for i in range(n)]
    count.insert(0,1)
    for x in range(1, n + 1):
        for c in a:
            if (x-c >= 0):
                count[x] += count[x-c]
    return count[n]%998244353

n,k = map(int,raw_input().split())
s = set()
for i in range(k):
    l,m = map(int,raw_input().split())
    for i in range(l,m+1):
        s.add(i)
arr = list(s)
print(fun(arr,n-1))

Submission status: Time Limit Exceeded

Solution code:
import sys


def sum(i):
    if nums[i] != -1:
        return nums[i]

    else:
        nums[i] = 0
        for k in S:
            if i - k > 0:
                nums[i] += sum(i - k)
            else:
                break
        return nums[i]


sys.setrecursionlimit(999999999)
S = set()
Sa = []
temp = []
temp = list(map(int, input().split()))
N = temp[0]
K = temp[1]
nums = [-1, 1]

for i in range(2, N + 1):
    nums.append(-1)

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

    for k in range(L, R + 1):
        S.add(k)

Sa = list(S)

print(sum(N) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
temparr = input()
temparr = temparr.split()
n = int(temparr[0])
k = int(temparr[1])
dicts = {}
dp = [0 for _ in range(n + 2)]
dp[1] = 1 
arr = []
dicts = {}
for kk in range(k):
    temparr = input()
    temparr = temparr.split()
    f = int(temparr[0])
    l = int(temparr[1]) + 1 
    for i in range(f,l):
        if i not in dicts:
            dicts[i] = 1 
for key, value in dicts.items():
    key = key % 998244353
    arr.append(key)
arr = sorted(arr)
#print(arr)
for i in range(1, n + 1):
    if dp[i] == 0:
        continue 
    for j in arr:
        index = i + j 
        if index > n :
            break 
        dp[index] += dp[i]
        if dp[index] > 998244353:
            dp[index] = dp[index] % 998244353
print(dp[n])

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(list(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 value == 0:
        continue
    if S[0] + idx >= N:
        break
    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:
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):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        dp[i] += sum(dp[LL:RR+1])
    dp[i] %= MOD

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
N, K = map(int, input().split())
S = set()
for _ in range(K):
    L, R = map(int, input().split())
    for j in range(L, R + 1):
        S.add(j)
C = [0] * N
C[0] = 1
for i in range(N):
    for s in S:
        if i + s < N:
            C[i + s] += C[i] % MOD
print(C[N - 1] % MOD)

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

S.sort()

for i in range(1, N):
    for s in S:
        if i - s < 0:break
        dp[i] = (dp[i] + dp[i - s]) % 998244353

print(dp[-1])

Submission status: Time Limit Exceeded

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

L = [0 for _ in range(N)]
R = [0 for _ in range(N)]

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

S = []
for i in range(K):
    for s in range(L[i],R[i]+1):
        S.append(s)

A = [0 for _ in range(N)]

A[0] = 1

for i in range(1,N):
    for s in S:
        if s<=i:
            A[i] += A[i-s] % 998244353
        A[i] = A[i] % 998244353

print(A[N-1])

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

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

for i in range(n):
  for l, r in LR:
    for j in range(l, r + 1):
      if i - j >= 0:
        dp[i] += dp[i - j]
        dp[i] %= MOD

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
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]
for i in range(1, n):
    sum = 0
    for j in s:
        if j <= i:
            sum += f[i-j]
            sum %= mod
    f.append(sum)

print(f[n-1])

Submission status: Time Limit Exceeded

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

mod=998244353
dp=[0]*(N)
dp[0]=1
S=set()

for x in range(0,K):
	a,b=input().split(' ')
	a=int(a)
	b=int(b)
	for y in range(a,b+1):
		S.add(y)

for x in range(1,N):
	for y in range(1,x+1):
		if y in S:
			dp[x]+=dp[x-y]
			dp[x]%=mod

print(dp[N-1])

Submission status: Time Limit Exceeded

Solution code:
## coding: UTF-8

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


able = [False] * (N+1)

for i in range(K):
    L, R = map(int,input().split())
    for j in range(L, R+1):
        able[j] = True

#print(able)

dp = ['a'] + [0] * (N)
dp[1] = 1
#print(dp)

for now in range(2, N+1):
    #print(now)
    point = 0
    for j in range(1, now):
        #print(now, j)
        if(able[j]):
            point += dp[now-j]
            point %= MOD
    dp[now] = point
#print(dp)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n, k = map(int, input().split())
    n-=1
    ww=998244353
    aa=[]
    kk=[0]*(n+1)
    for _ in range(k):
        l, r = map(int, input().split())
        for i in range(l,r+1):
            aa.append(i)
    kk[0]=1
    for i in range(n+1):
        for a in aa:
            if i+a<=n:
                kk[i+a]+=kk[i]
                kk[i+a]%=ww

    print(kk[n])
resolve()

Submission status: Time Limit Exceeded

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

memo = list()

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

Submission status: Time Limit Exceeded

Solution code:
root=[]
n,k = map(int,input().split())
for i in range(k):
    x,y = map(int,input().split())
    root.append([x,y])

toori=[0]*(2*10**5)+[0]*n+[0]*(2*10**5)
toori[2*10**5]=1
cum=[0]*k
for a,i in enumerate (root):
    s=0
    for j in range (i[0],i[1]+1):
        s+=toori[2*10**5+1-j]
    cum[a]=s
aaa=sum(cum)
toori[2*10**5+1]+=aaa


for now in range(2,n):#nowが今の場所
    hueru=0
    for a,i in enumerate (root):
        hueru+=(toori[2*10**5+now-i[0]] - toori[2*10**5+now-1-i[1]])
    aaa+=hueru
    toori[2*10**5+now]+=aaa
    toori[2*10**5+n-1]%=998244353
    


print(toori[2*10**5+n-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
mod=998244353

N,K=map(int,input().split())
LR=[list(map(int,input().split())) for _ in range(K)]
LR.sort()
num=[]
for l in LR:
    for i in range(l[0],l[1]+1):
        num.append(i)


dp=[0 for _ in range(N)]
dp[0]=1
for i in range(N):
    for n in num:
        if i+n<N:
            dp[i+n]+=dp[i]
            dp[i+n]%mod

print(dp[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 998244353


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, SS):
    count = [-1] * (N + 10)
    count[0] = 1

    ds = []
    for left, right in SS:
        for i in range(left, right + 1):
            ds.append(i)

    def f(pos):
        # debug("pos", pos)
        if pos < 0:
            return 0
        if count[pos] > -1:
            return count[pos]
        ret = 0
        for i in ds:
            j = pos - i
            if j < 0:
                continue
            r = f(j)
            count[j] = r
            ret += r

        return ret % MOD

    ret = f(N - 1)

    return ret % MOD


def main():
    # parse input
    N, K = map(int, input().split())
    SS = []
    for i in range(K):
        SS.append(tuple(map(int, input().split())))
    print(solve(N, K, SS))


# tests
T1 = """
5 2
1 1
3 4
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
4
"""

T2 = """
5 2
3 3
5 5
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
0
"""

T3 = """
5 1
1 2
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
5
"""

T4 = """
60 3
5 8
1 3
10 15
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
221823067
"""

T5 = """
10 1
1 2
"""
TEST_T5 = """
>>> as_input(T5)
>>> main()
55
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = []
while K !=0:
    L, R = map(int, input().split())
    S += [i for i in range(L,R+1)]
    K -= 1

A = [1]
n = 1
while n <= N - 1:
    for i in S:
        s = sum(A[n - i] for i in S if n - i >= 0)% 998244353
        A += [s]
        s = 0
        n += 1
print(A[N-1])

Submission status: Time Limit Exceeded

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))
    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)
print(b[-1]%998244353)

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([i for i in range(L, R+1)])

S.sort()

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

for i in range(N):
    dpi = dp[i]
    for value in S:
        if i + value >= N:
            break
        dp[i+value]+=dpi

print(dp[-1]%998244353)

Submission status: Time Limit Exceeded

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_d = {0:1}
for i in range(1,N):
  res_d[i] = sum(res_d.get(i-v,0) for v in As)%998244353
print(res_d[N-1])

Submission status: Time Limit Exceeded

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

MOD = 998244353

lst = []
for _ in range(K):
  l, r = map(int, input().split())
  for i in range(l, r+1):
    lst.append(i)
    
#print(lst)

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

for i in range(N):
  a = dp[i] % MOD
  for j in lst:
    dp[i + j] += a
  #print(dp)
   
print(dp[N-1]% MOD)