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:
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):
        if dp[i][j]!=0:
            for k in arr:
                if 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:
import sys
def input(): return sys.stdin.readline().rstrip()

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

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

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

for i in range(2,N+1):
    count = 0
    for l,r in zip(L,R):
        if l < i and i - r > 1:
            count += dp[i-l] - dp[i-r-1]
        elif l < i:
            count += dp[i-l]
    dp[i] = dp[i-1] + count

print((dp[N] - dp[N-1])% 998244353)

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()
for i in range(k):
  l,r = map(int, input().split())
  s |= {_ for _ in range(l,r+1)}
a = [0]*(2*10**5+1)
a[1] = 1
for i in range(2*10**5):
  for d in s:
    if i+d <= 2*10**5:
      a[i+d] += a[i]%998244353
    else:
      break
print(a[n]%998244353)

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]

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,k=map(int,input().split())
    xy = [map(int, input().split()) for _ in range(k)]
    x, y = [list(i) for i in zip(*xy)]
    slist=[]
    for j in range(k):
        jlist=list(range(x[j],y[j]+1))
        slist.extend(jlist)
    alist=[1]
    blist=[0]*(n-1)
    alist.extend(blist)
    for r in range(n):
        for sa in slist:
            if r+sa<=n-1:
                alist[r+sa]=(alist[r]+alist[r+sa])%998244353
    ans=alist[n-1]
    answer=ans%998244353
    print(answer)


main()

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())
  for j in range(l,r+1):
    s.append(j)
s.sort()
cnt = [0]*n
cnt[0] = 1
for i in range(n):
  for d in range(len(s)):
    if i+s[d] <= n-1:
      cnt[i+s[d]] += cnt[i]
    elif i+s[d] > n-1:
      break
print(cnt[-1] % mod)

Submission status: Time Limit Exceeded

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

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

area.sort()
d = [0] * N


def func(pos):
    for a in area:
        for i in range(a[0], a[1]+1):
            if pos - i > -1:
                d[pos] += d[pos-i] % 998244353
            else:
                return


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

print(d[N-1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
P=998244353
N,K=map(int,input().split())
LR=[]
for _ in range(K):
  l,r=map(int,input().split())
  LR+=range(l,r+1)
LR=list(set(LR))
c=[0]*N
c[0]=1
for k in range(N):
  S=LR[:]
  while len(S):
    if S[-1]>k:
      S.pop()
      continue
    c[k]+=c[k-S[-1]]%P
    S.pop()
print(c[-1]%P)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

D = deque([1], N)
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      count += sum(D[i-k] for k in range(l, min(i, r) + 1))
  D.append(count % 998244353)
print(D[-1])

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]
    if x>998244353:
        x=x%998244353
    b.append(x)
print(b[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
from numpy import *
N,K = map(int,input().split())
LR = [list(map(int,input().split())) for k in range(K)]
D = (N+2)*[0]
dp = (N+1)*[0]
dp[1] = 1
mod = 998244353

for L,R in LR:
  D[L]+=1
  D[R+1]-=1

D = cumsum(D)

for i in range(1,N+1):
  for j in range(1,i):
    if D[j]==1:
      dp[i] = (dp[i]+dp[i-j])%mod

print(dp[N])

Submission status: Time Limit Exceeded

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

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

if n > 1000:
  for i in range(1000,n,1000):
    a = solve(i)
a = solve(n-1)
print(a%m)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 8)
n, k = [int(i) for i in input().split()]
mod = 998244353
d = []
for i in range(k):
    l, r = [int(i) for i in input().split()]
    d += list(range(l, r+1))
d.sort()

dp = [-1] * n
dp[-1] = 1

def c(x):
    if dp[x] != -1:
        return dp[x]
    cnt = 0
    for i in d:
        if x + i >= n:
            break
        cnt += c(x + i) if dp[x+i] == -1 else dp[x+i]
    dp[x] = cnt % mod
    return dp[x]

print(c(0))

"""
for i in range(1, n+1):
    index = n - i
    for j in d:
        if index + j >= n: break
        dp[index] = (dp[index] + dp[index + j]) % mod

print(dp[0])
"""

Submission status: Time Limit Exceeded

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

idou = set()
for i in range(0, K):
    L, R = map(int, input().split())
    idou = idou | set(range(L, R + 1))

idou = list(idou)

moves = [0] * N
moves[0] = 1
for i in range(0, N):
    for j in range(0, len(idou)):
        if i + idou[j] < N:
            moves[i + idou[j]] += moves[i]

print(moves[N - 1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
sys.setrecursionlimit(10**7)


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

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


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

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


if __name__ == "__main__":
    main()

Submission status: 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]
        else:
            break
    dp[i] += tmp
    dp[i] %= MOD
    tmp = 0
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500*500)

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

jList = {j for l, r in LR for j in range(l, r+1)}
minL = min(jList)

mod = 998244353

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


print(dp(N-1))

Submission status: Time Limit Exceeded

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


def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    LR_list = [ list(map(int, sys.stdin.readline().split())) for _ in range(K) ]

    step = []

    for l,r in LR_list:
        step.extend( list(range(l, r+1)) )
    
    step.sort()
    

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

    for i in range(N+1):
        for j in step:
            if (i-j) >= 1:
                dp[i] += dp[i-j]
                dp[i] %= mod
            else:
                break
    
    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, n, op, e):
        self.n = 1 << (n - 1).bit_length()
        self.op = op
        self.e = e
        self.data = [e] * (2 * self.n)

    def update(self, k, v):
        k += self.n
        self.data[k] = v
        while k > 0:
            k >>= 1
            self.data[k] = self.op(self.data[2 * k], self.data[2 * k + 1])

    def query(self, left, right):
        left += self.n
        right += self.n
        l_res = self.e
        r_res = self.e
        while left < right:
            if left & 1:
                l_res = self.op(l_res, self.data[left])
                left += 1
            left >>= 1
            if right & 1:
                right -= 1
                r_res = self.op(self.data[right], r_res)
            right >>= 1
        return self.op(l_res, r_res)


MOD = 998244353
N, K, *LR = map(int, open(0).read().split())
segments = [(l, r) for l, r in zip(*[iter(LR)] * 2)]
st = SegmentTree(N + 1, lambda x, y: (x + y) % MOD, 0)
st.update(0, 1)
for i in range(1, N + 1):
    for l, r in segments:
        if i - l < 0:
            continue
        L = max(i - r, 0)
        R = i - l
        st.update(i, st.query(i, i + 1) + st.query(L, R + 1))
print(st.query(N - 1, N))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

mod = 998244353

n, k = map(int, input().split())
s = set()
for _ in range(k):
    l, r = map(int, input().split())
    for i in range(l, r + 1):
        s.add(i)

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

for i in range(1, n + 1):
    for j in range(i):
        if i - j in s:
            dp[i] += dp[j]
            dp[i] %= mod

print(dp[-2])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.buffer.readline


MOD = 998244353

n, k = map(int,input().split())
lr = []
for i in range(k):
    l, r = map(int,input().split())
    lr.append([l,r+1])
            
dp = np.zeros(n+1, dtype=np.int64)
dp[1] = 1
for i in range(1, n+1):
    for j in range(k):
        l, r = lr[j][0], lr[j][1]
        if r > n+1-i:
            r = n+1-i
        if l > n+1-i:
            continue
        dp[i+l:i+r] += dp[i]
        dp[i+l:i+r] %= MOD
        # print(dp)
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
n,k=list(map(int, input("").split()))
s=[]
for i in range(k):
    l,r=list(map(int, input("").split()))
    for j in range(l,r+1):
        s.append(j)
s=list(set(s))
s.sort()
o=[0]*(n+1)
o[1]=1
for i in range(2,n+1):
    for j in s:
        if i-j <= 0 :
            break
        else:
            o[i]+=o[i-j]
print(o[n]%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 = n
    
    # 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), p)
    
    # print(query(n-1, n))
    print(get(n-1))


if __name__ == "__main__":
    main()

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 = (v + count[i - l]) % 998244353
    count.append(v)

print(count[-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 i in range(L, R+1):
        s.append(i)
s.sort()

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
            else:
                break

print(dp[N-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 998244353
    n, k = map(int, input().split())
    s = []
    
    for _ in range(k):
        l, r = map(int, input().split())
        for i in range(l, r+1):
            s.append(i)
        s = sorted(s)
    
    m = [0 for _ in range(n + 1)]
    m[1] = 1
    for i in range(1, n+1):
        for j in s:
            if i+j <= n:
                m[i+j] += m[i]
            else:
                break
    print(m[n]%MOD)
        
if __name__ == '__main__':
    main()

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 = []
    ans = [0]*n*2
    for i in range(k):
        a,b = i_map()
        for k in range(a,b+1):
            l.append(k)
            ans[k] += 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:
n, k = map(int, input().split())
s = set()
for i in range(k):
    a, b = map(int, input().split())
    for j in range(a, b+1):
        s.add(j)

l = list(s)
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:
import numpy as np

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

s = []
for i in range(len(L)):
    tmp = [n for n in range(L[i], R[i]+1)]
    s += tmp

s.sort()
ans = [1]
for i in range(1,N):
    tmp = 0
    for ss in s:
        if len(ans) < ss:
            break
#         print("i ", i)
#         print(ss)
        tmp += ans[i - ss]%m
#         print(ans)
    ans.append(tmp%m)

print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,K = map(int,input().split())
figs = set()
for _ in range(K):
  a,b = map(int,input().split())
  for i in range(a,b+1):
    figs.add(i)
DP = [0]*N
DP[0] = 1
for i in range(N):
  for item in figs:
    if i - item >= 0:
      DP[i] = DP[i - item]+DP[i]
print(DP[-1]%998244353)

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 += [[L,R]]
        K -= 1
    S.sort()
    A = [1] + [0 for i in range(N + max(s[1] for s in S))]
    for i in range(N):
        for s in S:
            for t in range(s[0], s[1]+1):
                A[i+t] += A[i]
    print(A[N-1] % 998244353)


main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 998244353

n, k = map(int,input().split())
lr = []
for i in range(k):
    l, r = map(int,input().split())
    lr.append([l,r+1])
            
dp = np.zeros(n+1, dtype=np.int64)
dp[1] = 1
for i in range(1, n+1):
    for j in range(k):
        l, r = lr[j][0], lr[j][1]
        if r > n+1-i:
            r = n+1-i
        if l > n+1-i:
            continue
        dp[i+l:i+r] += dp[i]
        dp[i+l:i+r] %= MOD
        # print(dp)
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
#ABC179-d
import sys,math,collections,itertools
input = sys.stdin.readline
m=998244353

N,K=list(map(int,input().split()))
DP = [0]*(2*10**5+1)
move = []
for _ in range(K):
    l,r=list(map(int,input().split()))
    move += list(range(l,r+1))
move.sort()
ans = 0
for i in range(2,N+1):
    for mo in move:
        if i-mo<=0:
            break
        elif i-mo==1:
            DP[i]+=1
        else:
            DP[i]=(DP[i]+ DP[i-mo])%m
print(DP[N]%m)

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):
            break
#        print(i,j)
        dp[i] = (dp[i] +dp[i-j]) % 998244353

print(dp[N])

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])
        else:
            continue
print(seg.query(N, N + 1) % mod)

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-min(L)):
    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:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


n, k = LI()
s = set()
for i in range(k):
    l, r = LI()
    s |= set(range(l, r + 1))

# a = len(s)
dp = [0] * (n + 1)
dp[1] = 1
m = max(s)

for i in range(1, n+1):
    for j in range(i-m, i):
        if i-j in s:
            dp[i] += dp[j] % 998244353
            # dp[i] += dp[j]
print(dp[n] % 998244353)

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

Submission status: Time Limit Exceeded

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

dp = [0 for _ in range(3 * N)]
for s in S:
    dp[s + 1] = 1
for i in range(1, N + 1):
    for s in S:
        dp[i] += dp[i - s]
        dp[i] %= mod
print(dp[N] % mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353


def main():
    from bisect import bisect_left
    N, K = (int(i) for i in input().split())
    S = set()
    for _ in range(K):
        le, ri = (int(i) for i in input().split())
        for i in range(le, ri+1):
            S.add(i)

    A = sorted(S)
    memo = [0] * (N+1)
    memo[0] = 1

    def dfs(N):
        if N < 0:
            return 0
        if memo[N] != 0:
            return memo[N]
        ret = 0
        idx = bisect_left(A, N)
        for i in A[idx::-1]:
            ret += dfs(N - i)
            ret %= MOD
        memo[N] = ret
        return ret

    print(dfs(N-1))
    # print(memo, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2*10**5+10)
n,k=map(int, input().split())
a=[]
for i in range(k):
	l,r=map(int, input().split())
	for j in range(l,r+1):
		a.append(j)
dp=[-1]*(n+1)
def dfs(m):
	if m<=0: return 0
	if m==1: return 1
	if dp[m]>=0: return dp[m]
	ans=0
	for i in a:
		ans+=dfs(m-i)
		ans%=998244353
		dp[m]=ans
	return ans
print(dfs(n))