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
import sys
sys.setrecursionlimit(10**7)


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

    def dfs(self, i):
        if i == self.N-1:
            return 1
        elif i > self.N-1:
            return 0
        elif self.seen[i]:
            return self.cnt[i]
        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),reverse=True)

    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:
import sys
sys.setrecursionlimit(300000)
def main():
    n, k = map(int, input().split())
    memo = [-1] * (n+1)
    s = []

    def calc(n):
        if memo[n]>=0:
            return memo[n]
        c = 0
        for v in s:
            if v>n:
                break
            if v==n:
                c += 1
            else:
                c += calc(n-v)
        # print(n, c)
        memo[n] = c % 998244353
        return c

    for _ in range(k):
        l, r = map(int, input().split())
        s.extend(range(l, r+1))
    s.sort()

    ans = calc(n-1) % 998244353
    print(ans)
    # print(memo)

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int, input().split())

kukan = np.array([0] * (N + 1))
# make table of number
for i in range(K):
    left, right = map(int, input().split())
    kukan[left:right + 1] = 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

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())
lr = [map(int, input().split()) for _ in range(k)]
l, r = [list(i) for i in zip(*lr)]
s = []

for j in range(k):
  if l[j] == r[j]:
    s.append(l[j])
  else:
    s.extend(range(l[j], r[j]+1))
s = list(set(s))               

list1 = [0 for l in range(n)]
list1[0] = 1

for m1 in range(1,n):
  for m2 in range(len(s)):
    if s[m2] > m1:
      break
    list1[m1] += list1[m1-s[m2]]
      
print(list1[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 for _ in range(4*10**5+1)]
a[1] = 1
for i in range(2*10**5):
  for d in s:
    a[i+d] += a[i]%998244353
  a[i] %= 998244353
print(a[n]%998244353)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
N,K = map(int,input().split())
move = []
for _ in range(K):
    x,y = map(int,input().split())
    for i in range(x,y+1):
        move.append(i)
move.sort()
move = set(move)
memo = [0]*(N+1)
memo[1] = 1
for i in range(1,N):
    if 0<memo[i]:
        for j in move:
            if i+j<=N:
                memo[i+j] += memo[i]
            else:
                break
        
print(memo[-1]%mod)

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] >= 998244353:
            dp[i] -= 998244353
while dp[N] >= 998244353:
    dp[N] -= 998244353
print(dp[N])

Submission status: Time Limit Exceeded

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

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

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

def hantei(i):
    for j in range(k):
        if i >= lr[j][0] and i <= lr[j][1]:
            return True
    return False

for i in range(2, n+1):
    for j in range(1, i):
        if hantei(i - j):
            dp[i] += dp[j]

print(dp[n] % mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

for i in range(1, N):
    # マスiにたどり着くためのパターン数を数える
    cnt = 0
    for j in range(K):
        for k in range(L[j], R[j] + 1):
            if i - k >= 0:
                cnt += dp[i - k]
                cnt %= 998244353
    dp[i] = cnt

print(dp[N - 1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


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


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, LR):
    M = 998244353
    @lru_cache(maxsize=None)
    def f(i):
        if i == N:
            ret = 1
        elif i > N:
            ret = 0
        else:
            ret = 0
            for l, r in LR:
                for d in range(l, r+1):
                    if i+d <= N:
                        ret += f(i+d)
                        ret %= M
                    else:
                        break
        return ret

    return f(1)

def main():
    N, K = read_int_n()
    LR = [read_int_n() for _ in range(K)]
    print(slv(N, K, LR))

    # N = 2 * (10**5)
    # p = [random.randint(1, N) for _ in range(20)]
    # p.sort(reverse=True)
    # LR = []
    # K = 10
    # for i in range(1, 11):
    #     LR.append([2*i-1, 2*i])
    # LR.sort()
    # LR[0][0] = 1
    # print(N, K, LR)

    # print(slv(N, K, LR))



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
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):
    f=bl(num,N-i)
    for n in num[:f+1]:
        if i+n<N:
            dp[i+n]+=dp[i]
            dp[i+n]%mod
#print(dp)
print(dp[-1]%mod)

Submission status: Time Limit Exceeded

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

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

min_interval = min(i for l, r in LR for i in range(l, r + 1))
max_step = (N - 1 + (min_interval - 1)) // min_interval

ans = 0
prev_nodes = [1]
for step in range(1, max_step + 1):
    for i in range(N):
        for l, r in LR:
            for d in range(l, r + 1):
                if N < i + d:
                    continue
                elif N == i + d:
                    ans = (ans + dp[step - 1][i]) % 998244353
                else:
                    dp[step][i + d] += dp[step - 1][i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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 = [0] * 300000
dp[1] = 1

for i in range(2, N+1):
    for d in D:
        if i - d < 1:continue
        dp[i] += dp[i-d]
        dp[i] %= 998244353

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353


def main():
    N, K = map(int, input().split())

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

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

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

    print(dp[N])


main()

Submission status: Time Limit Exceeded

Solution code:
nk=input("").split(" ")
n=int(nk[0])
k=int(nk[1])
listp=[]
for i in range(n):
    listp+=[-1]
listp[0]=1
listlr=[]
for i in range(k):
    lr=input("").split(" ")
    listlr+=[[int(lr[0]),int(lr[1])]]
    



def funcp(n):
    if(listp[n-1]==-1):
        s=0
        for ii in range(k):
            for i in range(n-listlr[ii][1],n-listlr[ii][0]+1):
                if(i>1):
                    s+=funcp(i)
                elif(i==1):
                    s+=1
        s%=998244353
        listp[n-1]=s
        
        return s
    else:
        return listp[n-1]
    
print(funcp(n)%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
import numpy as np
def main():
    large_num = 998244353
    n, k = map(int, input().split())
    n -= 1
    jump = []
    m = map(int, read().split())
    for a, b in zip(m, m):
        jump.append((a, b))
    dp = np.zeros(n+1)
    dp[0] = 1
    for i1 in range(1, n+1):
        for je in jump:
            for se in range(je[0],je[1]+1):
                if se > i1:
                    break
                else:
                    dp[i1] += dp[i1 - se]
        dp[i1] = dp[i1] % large_num

    print(int(dp[-1]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
d = []
for i in range(K):
    L, R = map(int, input().split())
    d.append(L)
    d.append(R)
a=[0]*(N+1)
b=[0]*(N+1)
a[1]=1
b[1]=1
for i in range(2,N+1):
    t=0
    for j in range(K):
        if i-d[2*j]>0:
            t+=b[i-d[2*j]]
        if i-d[2*j+1]-1>0:
            t-=b[i-d[2*j+1]-1]
    a[i]=t
    b[i]=b[i-1]+a[i]
print(a[N]%998244353)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    
    n,k = map(int,input().split())
    tmpset = set()
    for _ in range(k):
        morty,morty1= map(int,input().split())
        for i in range(morty,morty1+1):
            tmpset.add(i)
        
    dp = [0]*(n+1)
    dp[0] = 1
    for i in range(len(dp)):
        if(dp[i]>0):
            for tmp in tmpset:
                if tmp+i<=n:
                    dp[tmp+i]+=dp[i]
                    dp[tmp+i]%=998244353
    print(dp[n-1])


        


    




















if __name__ == "__main__":
    main()

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
  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:
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())
        aa.append([l,r])
    kk[0]=1
    for i in range(n+1):
        if kk[i]!=0:
            for a in aa:
               for j in range(a[0],a[1]+1):
                  if i+j<=n:
                      kk[i+j]+=kk[i]
                      kk[i+j]%=ww

    print(kk[n])
resolve()

Submission status: Time Limit Exceeded

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

n,k = map(int,input().split())
s = []
for i in range(k):
  l,r = map(int,input().split())
  s.append((l,r))
s.sort()
MOD = 998244353

memo = [-1 for _ in range(n+1)]

def f(x):
  if x < 1:
    return 0
  if x == 1:
    return 1
  if memo[x] != -1:
    return memo[x]
  res = 0
  for l,r in s:
    for i in range(l,r+1):
      res += f(x-i)
      res %= MOD
  memo[x] = res
  return res

print(f(n))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
s = set()
lr = []
for _ in range(k):
    # l, r = map(int, input().split())
    lr.append(tuple(map(int, input().split())))
    # for tmp in range(l, r+1):
    #     s.add(tmp)
mod = 998244353

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

for i in range(1, n):
    for l, r in lr:
        for ss in range(l, r+1):
            if i-ss >= 0:
                dp[i] += dp[i-ss]
    dp[i] %= mod

print(dp[-1]%mod)

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-mo]
print(DP[N]%m)

Submission status: Time Limit Exceeded

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

mod = 998244353
i = 1
dp = [0] * (n+1)
dp[i] = 1
for i in range(n+1):
    for lr in s:
        for d in range(lr[0], lr[1]+1):
            if i+d <= n:
                dp[i+d] += dp[i]

print(dp[n] % mod)

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 = [0]*n
dp[0] = 1
for i in range(n):
  for s in step:
    if i>=s:
      dp[i] += dp[i-s]
    else:
      break

print(dp[n-1]%m)

Submission status: Time Limit Exceeded

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

import sys
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    # mod = 1000000007                # 10^9+7
    mod = 998244353
    # inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def mi():     return map(int, input().split())
    def lmi():    return list(map(int, input().split()))
    def debug(x): print(x, file=sys.stderr)
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
    

    n, k = mi()
    intervals = [tuple(mi()) for _ in range(k)]
    N = 2 * n + 1
    
    # N: 処理する区間の長さ
    INF = 2**63-1

    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] += v
            lazy[2*i] += v
            #
            lazy[2*i-1] %= mod
            lazy[2*i] %= mod
            data[2*i-1] += v
            data[2*i] += v
            #
            data[2*i-1] %= mod
            data[2*i] %= 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] += x
                data[R-1] += x
                # 
                lazy[R-1] %= mod
                data[R-1] %= mod
            if L & 1:
                lazy[L-1] += x
                data[L-1] += x
                # 
                lazy[L-1] %= mod
                data[L-1] %= mod
                L += 1
            L >>= 1; R >>= 1
        # for i in ids:
        #     data[i-1] = min(data[2*i-1], data[2*i])

    # # 区間[l, r)内の最小値を求める
    # def query(l, r):
    #     propagates(*gindex(l, r))
    #     L = N0 + l; R = N0 + r

    #     s = INF
    #     while L < R:
    #         if R & 1:
    #             R -= 1
    #             s = min(s, data[R-1])
    #         if L & 1:
    #             s = min(s, data[L-1])
    #             L += 1
    #         L >>= 1; R >>= 1
    #     return s
    
    # [l] を求める
    def get(l):
        propagates(*gindex(l, l+1))
        return data[N0+l-1]



    update(0, 1, 1)
    for i in range(n):
        # p = query(i, i+1)
        p = get(i)
        # print(p)
        for l, r in intervals:
            if i + l < n:
                update(i+l, i+r+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())

LR = [list(map(int,input().split())) for _ in range(K)]
L = [0]*N
for i in range(N):
    if i == 0:
        L[0] = 1
    else:#i>=1のとき
        for j in range(K):#それぞれの区間に対して
            if i - LR[j][0] >= 0:
                L[i] +=sum(L[max(i - LR[j][1],0) : i - LR[j][0] + 1])
               
print(L[N-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil as C, floor as F, sqrt, gcd as G
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ

class Heap:
  def __init__(self, data, reverse=False):
    self.reverse = -1 if reverse else 1
    self.data = [self.reverse * d for d in data]
    HQ.heapify(self.data)
  def push(self, x): return HQ.heappush(self.data, self.reverse * x)
  def pop(self): return self.reverse * HQ.heappop(self.data) 

ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

n, k = I()
steps = set()
mod = 998244353

for _ in range(k):
    l, r = I()
    steps.update([i for i in range(l, r+1)])

ans = 0
# heap = Heap([1])
# seen = set([1])
cache = D(int)
cache[1] = 1

# def go(i):
for i in range(1, n):
    if cache[i] == 0:
        continue
    for step in steps:
        # print(heap.data, seen, cache)
        t = i + step
        if t <= n:
            cache[t] += cache[i]
            cache[t] %= mod

    
print(cache[n])

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 += [ 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:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

p = 998244353

jump = []
for i in range(k):
    a, b = map(int, input().split())
    jump += list(range(a, b+1))

dp = [0]*(n+1+max(jump))
dp[0] = 1
for i in range(n):
    if dp[i]==0: continue
    for j in range(len(jump)):
        dp[i+jump[j]] += dp[i]%p
        dp[i+jump[j]] %= p

print(dp[n-1]%p)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l=[]
for _ in range(k):
    a,b=map(int,input().split())
    for i in range(a,b+1):
        l.append(i)
dp=[0]*(n+1)
for i in range(1,n+1):
    if i in l:
        dp[i]+=1
    for j in l:
        if j<=i:
            dp[i]+=dp[i-j]
            dp[i]%=998244353
print(dp[-2])

Submission status: Time Limit Exceeded

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

def main():
    mod = 998244353
    N, K = map(int, input().split())
    L = [0] * K
    R = [0] * K
    for i in range(K):
        L[i], R[i] = map(int, input().split())

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

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


if __name__ == '__main__':
    main()

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())
  for lr in range(L, R + 1):
    S.add(lr)
S = list(S)
DP = [0] * N
DP[0] = 1
for i in range(N):
  for s in S:
    if 0 <= i - s < N:
      DP[i] += DP[i - s]
print(DP[-1]%998244353)

Submission status: Time Limit Exceeded

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


s = list(set(s))

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

for i in range(2,n+1):
    for j in range(len(s)):
        if i-s[j] > 0:
            ans[i] += ans[i-s[j]]


print(ans[n]%998244353)

Submission status: Time Limit Exceeded

Solution code:
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]
n = 1
while n <= N - 1:
    for i in S:
        s = sum(A[n - i] for s in S for i in range(s[0], s[1] + 1) 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())

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

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


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


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

print(d[0] % 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()
    for _ in range(K):
        l, r = map(int, input().split())
        for n in range(l, r + 1):
            S.add(n)
    MOD = 998244353

    S = sorted(list(S))
    dp = np.zeros(N, dtype=np.int64)
    dp[0] = 1
    for i in range(N):
        for d in S:
            if i < d:
                break
            dp[i] += dp[i - d] % MOD
    print(dp[-1] % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
mod = 998244353

s_list = []
for _ in range(k):
    l, r = map(int, input().split())
    s_list += list(range(l, r + 1))
S = set(sorted(s_list))

ans_array = [0] * (n + 1)
ans_array[1] = 1
for i in range(1, n):
    for d in S:
        if d + i > n:
            break
        ans_array[d + i] = (ans_array[d + i] + ans_array[i]) % mod


print(ans_array[n])

Submission status: Time Limit Exceeded

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

def main():
    mod = 998244353
    N, K = map(int, input().split())
    L = [0] * K
    R = [0] * K
    for i in range(K):
        L[i], R[i] = map(int, input().split())

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

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


if __name__ == '__main__':
    main()

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]
    if dpi == 0:
        continue
    for value in S:
        if i + value >= N:
            continue
        dp[i+value]+=dpi%998244353

print(dp[-1]%998244353)

Submission status: Time Limit Exceeded

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

n,k = map(int,input().split())
s = []
for i in range(k):
  l,r = map(int,input().split())
  s.append((l,r))
MOD = 998244353

memo = [-1 for _ in range(n+1)]

def f(x):
  if x < 1:
    return 0
  if x == 1:
    return 1
  if memo[x] != -1:
    return memo[x]
  res = 0
  for l,r in s:
    for i in range(l,r+1):
      res += f(x-i)
      res %= MOD
  memo[x] = res
  return res

print(f(n))