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:
# -*- coding: utf-8 -*-
# D

import sys
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):
    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] += sum(dp[i-r[j]+1:i-l[j]+1]) % mod
# print(dp)
print(dp[2*n-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(v) for v in input().split()]

link = []
for k in range(K):
    L, R = [int(v) for v in input().split()]

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

link.sort()
count = [1]

for i in range(1, N):
    v = 0
    for l in link:
        if i < l:
            break
        v += count[i - l]
    count.append(v % 998244353)

print(count[-1])

Submission status: Time Limit Exceeded

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

N,K = map(int, input().split())
LR = set()
for i in range(K):
    l,r = map(int, input().split())
    for val in range(l,r+1,1):
        LR.add(val)

count = [0] * N
count[0] = 1
for pos in range(N):
    if count[pos] > 0:
        for mv in LR:
            if pos + mv < N:
                count[pos+mv] += count[pos]
                #print(pos+1,mv)

ans = count[N-1] % 998244353
print(ans)

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 :
            continue
        for dis in range(L, R+1):
            if n - dis >= 1:
                dp[n] += dp[n - dis]
            else:
                break

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

Submission status: Time Limit Exceeded

Solution code:
def main():
  N, K = map(int, input().split())
  dis = []
  mod = 998244353
  for _ in range(K):
    L, R = map(int, input().split())
    if L == R:
      dis.extend([L])
    else:
      dis.extend(list(range(L, R+1)))
  
  lst = [0] * (N+1)
  lst[0] = 1
  for i in range(1, N):
    for j in dis:
      lst[i] += lst[i-j]
    if lst[i] >= mod:
      lst[i] = lst[i] % mod
  print(lst[i])
  
main()

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

    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:
N,K=map(int,input().split())
A=[0 for i in range(2*10**5+1)]
A[1]=1
S=[]
for i in range(K):
  L,R=map(int,input().split())
  for i in range(L,R+1):
    S.append(i)
S.sort()
import copy
mod=998244353
for i in range(1,N):
  for j in range(len(S)):
    if i+S[j]<=N:
      A[S[j]+i]+=A[i]
      A[S[j]+i]%=mod
    else:
      S=S[:j]
      break

    
print(A[N])

Submission status: Time Limit Exceeded

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

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

S = []
for lr in sorted(LR, key=lambda x:x[0]):
    S += list(range(lr[0], lr[1]+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 - s]

print(dp[-1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
dp=[0]*(N)
dp[0]=1
mod=998244353
L=list()
for i in range(K):
  a,b=map(int,input().split())
  L.append([a,b])
for i in range(N):
  for j in range(K):
    a,b=L[j]
    if i>=b:
      dp[i]+=sum(dp[i-b:i-a+1])
    elif i>=a:
      dp[i]+=sum(dp[:i-a+1])
    dp[i]%=mod
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
L=list()
R=list()
dp=[0]*N
dp[0]=1
for i in range(K):
    l,r=map(int,input().split())
    L.append(l)
    R.append(r)
for i in range(0,N):
    for k in range(K):
        for j in range(L[k],R[k]+1):
            if i+j>N-1:
                break
            else:
                dp[i+j]+=dp[i]%998244353
print(dp[N-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
t = sys.stdin.readlines()
N,K = map(int, t[0].split())
S = []
for i in range(K):
    L,R = map(int, t[1+i].split())
    S += [ j for j in range(L,R+1)]
S = set(S)

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


for j in range(1,N):
    for s in S:
        if j + s > N or step[j] == 0:
            continue
        step[j+s] += (step[j]%998244353)
        step[j+s] %= 998244353
    
print(step[N])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
w = [0]*1000000
s = []
for _ in range(k):
  l,r = map(int,input().split())
  if l==r:
    s.append(l)
  else:
    for i in range(l,r+1):
      s.append(i)
s.sort()

w[1] = 1
for i in range(2,n+1):
  for num in s:
    if i-num < 1:
      break
    w[i] += w[i-num]
    w[i] = w[i]%998244353
print(w[n])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
allowed_jump = []
for i in range(k):
    l, r = map(int, input().split())
    allowed_jump.extend([l+i for i in range(r-l+1)])
    allowed_jump.sort()
ans = [0 for i in range(n)]
ans[0]=1
for i in range(n):
    for jump in allowed_jump:
        if i-jump>= 0:
            ans[i] += ans[i-jump]
print(ans[n-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
S = set()
mod = 998244353
for i in range(k):
    l,r = map(int,input().split())
    for x in range(l,r+1):
        S.add(x)
    #print(S)
    
dp = [0]*(n+1)
dp[0] = 1
for j in range(n):
    for i in S:
        #print(j,i)
        if j-i >=0:
            dp[j] += dp[j-i]
print(dp[n-1]%mod)

Submission status: Time Limit Exceeded

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

MOD = 998244353  # type: int


def solve(N: int, K: int, L: "List[int]", R: "List[int]"):
    routes = [0 for _ in range(N)]
    # routes[0] = Decimal(1)
    routes[0] = 1
    moves = []

    c = []
    for k in range(K):
        c.append([L[k], R[k]])
    c = sorted(c)
    for k in c:
        moves += list(range(k[0], k[1]+1))

    moves = sorted(moves)
    for i in range(1, N):
        tmp = 0
        for m in moves:
            if i < m: break
            # tmp += Decimal(routes[i - m])
            tmp += (routes[i - m])
            # print(i, m, tmp)
        routes[i] = tmp % MOD
    # print(routes)
    return routes[N-1] % MOD


# 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))
    print(solve(N, K, L, R))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np  # 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)

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


print(int(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N, K = MI()
    s = set()
    mod = 998244353
    for i in range(K):
        l, r = MI()
        for j in range(l, r+1):
            s.add(j)
    dp = [0] * (N+1)
    dp[1] = 1
    for i in range(1, N):
        for ss in s:
            idx = i + ss
            if idx < N+1:
                dp[i+ss] += dp[i] % mod
        # print(dp)
    # for ss in s:
    #     for i in range(ss, N, ss):
    #         dp[i] += 1
    # print(dp)
    print(dp[N] % mod)
            
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 998244353
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

#bisect.bisect_left(list,key)はlistのなかでkey未満の数字がいくつあるかを返す
#つまりlist[i] < x となる i の個数
#bisect.bisect_right(list, key)はlistのなかでkey以下の数字がいくつあるかを返す
#つまりlist[i] <= x となる i の個数
#これを応用することで
#len(list) - bisect.bisect_left(list,key)はlistのなかでkey以上の数字がいくつあるかを返す
#len(list) - bisect.bisect_right(list,key)はlistのなかでkeyより大きい数字がいくつあるかを返す
#これらを使うときはあらかじめlistをソートしておくこと！

n,k = MI()
l_r = LLI(k)
li = [0 for _ in range(n)]
li[0] = 1
for i in range(n):
    for s in l_r:
        l = s[0]
        r = s[1]
        for j in range(l,r+1):
            if i+j < n:
                li[i+j] += li[i]
print(li[-1]%mod)

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

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

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


print(masu[-1])

Submission status: Time Limit Exceeded

Solution code:

import numpy as np

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

move_list = []
checker = np.zeros(N+1 ,dtype = int)
for LR in LRs:
    for i in range(LR[0], LR[1]+1):
        checker[i] = 1

for index, check in enumerate(checker):
    if(check == 1):
        move_list.append(index)

#print(move_list)

dp = np.zeros(N+1, dtype = int)
dp[1] = 1

for i in range(1, N+1):
    for j in move_list:
        if(i < j):
            continue
#        print(i,j)
        dp[i] += dp[i-j]
        dp[i] = dp[i] % 998244353

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(v) for v in input().split()]

link = []
for k in range(K):
    L, R = [int(v) for v in input().split()]

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

link.sort()
#link.reverse()
#print(link)

count = [0, 1]

for i in range(2, N + 1):
    v = 0
    for l in link:
        if i < l:
            break
        v += count[i - l]
    count.append(v)

print(count[-1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
import numpy as np
setrecursionlimit(10 ** 8)

mod = 998244353

def main():
    from builtins import int, map
    N, K = map(int, input().split())
    LR = [tuple(map(int, input().split())) for _ in range(K)]
    # print(N, K, LR)
    
    possible = np.zeros(N + 1, dtype=np.int)
    possible[1] = 1
    for k in range(1, N + 1):
        for (l, r) in LR:
            if possible[k] > 0:
                possible[k+l:k+r+1] += possible[k]
                possible[k+l:k+r+1] %= mod
    ans = possible[N] % mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    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
    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:
            A[i+s] += A[i]
    print(A[N-1] % 998244353)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(110000)

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)


dp_memo = [-1] * 300000
dp_memo[1] = 1

def dp(v):
    if dp_memo[v] != -1:
        return dp_memo[v]
    ret = 0
    for d in D:
        if v - d < 1:continue
        ret += dp(v - d)
    ret %= 998244353
    dp_memo[v] = ret
    return ret

print(dp(N))

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):
    b.append(0)
    for j in a:
        b[-1]+=b[-j-1]
print(b[-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

S = []
for l,r in LR:
    for _ in range(l,r+1):
        S.append(_)
S = list(set(S))
S.sort()

dp = [0] * (N+1)
dp[1] = 1
tmp = 0
for i in range(2,N+1):
    for s in S:
        if i - s >= 1:
            tmp += dp[i-s]
            dp[i] += tmp
            tmp = 0
        else:
            break
    dp[i] %= MOD
print(dp[-1])

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 = defaultdict(int)
	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())

li = [0]*(n+2)
lis = []
lis2 =[0]*(3*n)
lis2[1]=1

for i in range(k):
    l,r = map(int, input().split())
    for j in range(l,r+1):
        lis.append(j)

for i in range(1,n+1):
    for j in lis:
        lis2[i]%=998244353
        lis2[i+j]+=lis2[i]

print(lis2[n])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
section = [0] * (n + 2)

for i in range(k):
    left, right = map(int, input().split())
    section[left] += 1
    section[right + 1] -= 1

numbers = []
cnt = 0
for i in range(1, n + 1):
    cnt += section[i]
    if 0 < cnt:
        numbers.append(i)

    
d = [0] * (n + 1)
d[1] = 1

for i in range(1, n + 1):
    for j in numbers:
        if i - j <= 0:
            continue
    
        d[i] += d[i - j]
        d[i] %= 998244353
    
print(d[n])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K = map(int, input().split())
L = list()
R = list()
for _ in range(K):
    a,b = map(int, input().split())
    for _1 in range(_):
        x,y = L[_1],R[_1]
        if x <= a <= y or x <= b <= y :
            L[_1] = min(a,x)
            R[_1] = max(b,y)
            break
    else:
        L.append(a)
        R.append(b)
sep = len(L)


MOD = 998244353
dp = np.zeros(N+10,dtype=np.int64)
dp[1] = 1
for i in range(1,N+1):
    for l, r in zip(L,R):
        dp[min(N + 1, i + l):min(N + 1, i + r + 1)] += dp[i]
        # print(dp)

print(dp[N]%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())
    for i in range(L, R+1):
        s.append(i)


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

print(dp[N-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)
def countWays(arr, m, N):
    count = [0 for i in range(N + 1)]
    count[0] = 1
    for i in range(1, N + 1):
        for j in range(m):
            if (i >= arr[j]):
                count[i] += count[i - arr[j]]
    return count[N]
print(countWays(S,len(S),N-1)%998244353)

Submission status: Time Limit Exceeded

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

arr=[]
for i in range(K):
    a,b=map(int,input().split())
    for j in range(a,b+1):
        if j not in arr:
            arr.append(j)



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:
mod = 998244353
n, k = map(int, input().split())
s = []
for _ in range(k):
    l, r = map(int, input().split())
    s.extend([x for x in range(l, r+1)])
s.sort()
score = [0 for _ in range(n)]
score[0] = 1
for i in range(n):
    for x in s:
        if i+x >= n:
            break
        score[i+x] = (score[i]+score[i+x])%mod

print(score[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)]
S = set()
for i in LR:
    for j in range(i[0], i[1]+1):
        S.add(j)
L = list(S)

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

    t = [j for j in L if j <= i]

    for j in t:
        dp[i] += dp[i-j]

print(dp[-1] % 998244353)

Submission status: Time Limit Exceeded

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

import sys


def main():
    mod = 998244353
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def mi():     return map(int, input().split())
    def debug(x): print(x, file=sys.stderr)
    

    n, k = mi()
    intervals = [tuple(mi()) for _ in range(k)]
    N = 2 * n + 1
    
    # N: 処理する区間の長さ
    LV = (N-1).bit_length()
    N0 = 2**LV
    data = [0]*(2*N0)
    lazy = [0]*(2*N0)

    def gindex(l, r):
        L = (l + N0) >> 1; R = (r + N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1

    # 遅延伝搬処理
    def propagates(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if not v:
                continue
            lazy[2*i-1] = (lazy[2*i-1] + v) % mod
            lazy[2*i] = (lazy[2*i] + v) % mod
            data[2*i-1] = (data[2*i-1] + v) % mod
            data[2*i] = (data[2*i] + v) % mod
            lazy[i-1] = 0

    # 区間[l, r)にxを加算
    def update(l, r, x):
        *ids, = gindex(l, r)
        propagates(*ids)
        L = N0 + l; R = N0 + r
        while L < R:
            if R & 1:
                R -= 1
                lazy[R-1] = (lazy[R-1] + x) % mod
                data[R-1] = (data[R-1] + x) % mod
            if L & 1:
                lazy[L-1] = (lazy[L-1] + x) % mod
                data[L-1] = (data[L-1] + x) % mod
                L += 1
            L >>= 1; R >>= 1
    
    # [l] を求める
    def get(l):
        propagates(*gindex(l, l+1))
        return data[N0+l-1]



    update(0, 1, 1)
    for i in range(n):
        p = get(i)
        # print(p)
        for l, r in intervals:
            if i + l < n:
                update(i + l, min(i + r + 1, n + 1), p)
    
    # print(query(n-1, n))
    print(get(n-1))


if __name__ == "__main__":
    main()

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 = 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())
mod=998244353
dp=[0]*n
dp[0]=1
l=[list(map(int,input().split(" "))) for i in range(k)]
for i in range(1,n):
    for j in range(k):
        for m in range(l[j][0],l[j][1]+1):
            if i-m>=0:
                dp[i]+=dp[i-m]%mod
            else:
              break
print(dp[n-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n, k = i_map()
    l = []
    for i in range(k):
        a,b = i_map()
        for k in range(a,b+1):
            l.append(k)

    ans = [0]*n*2
    for i in l:
        ans[i] += 1

    for i in range(n):
        if ans[i] > 0:
            for k in l:
                ans[i+k] += ans[i]
                ans[i+k]= ans[i+k] % 998244353
    print(ans[n-1] % 998244353)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from sys import exit

import sys
sys.setrecursionlimit(1000000000)
mod = 998244353

#############
# Main Code #
#############

#####segfunc#####
def segfunc(x, y):
    return min(x, y)
#################

#####ide_ele#####
ide_ele = 2 ** 63 - 1
#################

class LazySegmentTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    add(l, r, x): 区間[l, r)にxを加算 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        num: n以上の最小の2のべき乗
        data: 値配列(1-index)
        lazy: 遅延配列(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.data = [ide_ele] * 2 * self.num
        self.lazy = [0] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.data[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])

    def gindex(self, l, r):
            """
            伝搬する対象の区間を求める
            lm: 伝搬する必要のある最大の左閉区間
            rm: 伝搬する必要のある最大の右開区間
            """
            l += self.num
            r += self.num
            lm = l >> (l & -l).bit_length()
            rm = r >> (r & -r).bit_length()

            while r > l:
                if l <= lm:
                    yield l
                if r <= rm:
                    yield r
                r >>= 1
                l >>= 1
            while l:
                yield l
                l >>= 1

    def propagates(self, *ids):
        """
        遅延伝搬処理
        ids: 伝搬する対象の区間
        """
        for i in reversed(ids):
            v = self.lazy[i]
            if not v:
                continue
            self.lazy[2 * i] += v
            self.lazy[2 * i + 1] += v
            self.data[2 * i] += v
            self.data[2 * i + 1] += v
            self.lazy[i] = 0

    def add(self, l, r, x):
        """
        区間[l, r)の値にxを加算
        l, r: index(0-index)
        x: additional value
        """
        *ids, = self.gindex(l, r)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.lazy[l] += x
                self.data[l] += x
                l += 1
            if r & 1:
                self.lazy[r - 1] += x
                self.data[r - 1] += x
            r >>= 1
            l >>= 1
        for i in ids:
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1]) + self.lazy[i]


    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.data[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.data[r - 1])
            l >>= 1
            r >>= 1
        return res

# 1 ~ Nまで
N, K = getNM()
que = [getList() for i in range(K)]

# 通りの数を求める問題
# dp？
# 組み合わせ？

# goの要素を足して行ってN = 1を達成できればいい
# ただしgoの数が多い
# ナップサックは無理

# 重複あり部分和
# 部分和の通り

# どうすればN - 1の組み合わせができるか
# ソートする？
# 足し合わせ？


dp = [0] * (N + 1)
seg = LazySegmentTree([0] * (N + 1), segfunc, ide_ele)
dp[1] = 1
seg.add(1, 2, 1)

# dpする
for i in range(1, N):
    dp[i] = seg.query(i, i + 1) % mod
    for l, r in que:
        if i + l <= N:
            seg.add(i + l, min(i + r + 1, N + 1), dp[i])
print(seg.query(N, N + 1) % mod)

Submission status: Time Limit Exceeded

Solution code:
# range update
# point query

M = 998244353

# on demand
class SegmentTreeNodeOD:
	def __init__(self, start, end):
#		print("s", start, end)
		self.value = 0
		self.start = start
		self.end = end
		self.width = end - start
		self.left = None
		self.right = None
	
	def add(self, start, end, value):
		if self.start >= start and self.end <= end:
			self.value = (self.value + value) % M
		elif self.width > 1 and (self.start < end and start < self.end):
			if self.left == None:
				w2 = self.width // 2
				self.left = SegmentTreeNodeOD(self.start, self.start + w2)
				self.right = SegmentTreeNodeOD(self.start + w2, self.end)
			self.left.add(start, end, value)
			self.right.add(start, end, value)
	
	def sum(self, index):
		s = 0
		if self.start <= index and index < self.end:
			s = (s + self.value) % M
			if self.left != None:
				s = (s + self.left.sum(index) + self.right.sum(index)) % M
		return s
	
class SegmentTreeOD:
	def __init__(self, n):
		width = 1
		while width < n:
			width *= 2
		self.root = SegmentTreeNodeOD(0, width)
		self.root.value = 0
	
	def add(self, start, end, value):
		self.root.add(start, end, value)
	
	def sum(self, index):
		return self.root.sum(index)
	
N, K = map(int, input().split())

sects = []
for _ in range(K):
	sects.append(tuple(map(int, input().split())))

st = SegmentTreeOD(N + 1)
st.add(1, 2, 1)

for i in range(N):
#	print(st.to_list())
	count = st.sum(i)
	for R, L in sects:
		st.add(i + R, i + L + 1, count)

#print(st.to_list())

print(st.sum(N))