Problem:


Score : 400 points

Problem Statement

There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.

Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.

You are given an integer K that is less than or equal to 10, and K non-intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K].
Let S be the union of these K segments.
Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.

When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.

To help Tak, find the number of ways to go to Cell N, modulo 998244353.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq K \leq \min(N, 10)

1 \leq L_i \leq R_i \leq N

[L_i, R_i] and [L_j, R_j] do not intersect (i \neq j) 

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
L_1 R_1
L_2 R_2
:
L_K R_K

Output

Print the number of ways for Tak to go from Cell 1 to Cell N, modulo 998244353.

Sample Input 1

5 2
1 1
3 4

Sample Output 1

4

The set S is the union of the segment [1, 1] and the segment [3, 4], therefore S = \{ 1, 3, 4 \} holds.

There are 4 possible ways to get to Cell 5:

1 \to 2 \to 3 \to 4 \to 5,

1 \to 2 \to 5,

1 \to 4 \to 5 and

1 \to 5.

Sample Input 2

5 2
3 3
5 5

Sample Output 2

0

Because S = \{ 3, 5 \} holds, you cannot reach to Cell 5.
Print 0.

Sample Input 3

5 1
1 2

Sample Output 3

5

Sample Input 4

60 3
5 8
1 3
10 15

Sample Output 4

221823067

Note that you have to print the answer modulo 998244353.



Sample input:
5 2
1 1
3 4


Sample output:
4

Submission status: Time Limit Exceeded

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# 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():
    Num = Union[int, float]
    # 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 ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    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 = [lmi() for _ in range(k)]
    N = 2 * n + 1
    
    # N: 処理する区間の長さ
    INF = 2**31-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:
def solve(S,N):
    mod = 998244353
    DP = [0 for _ in range(N+1)]
    DP[1] = 1
    for i in range(2,N+1):
        for j in range(len(S)):
            if i - S[j] >= 1:
                DP[i] += DP[i-S[j]]
                DP[i] %= mod

    return DP[N]

def main():
    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()
    print(solve(S,N))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

T = []

for i in range(K):
    if i==0:
        for j in range(lis[i][0],lis[i][1]+1):
            T.append(j)
            S = set(T)
        T = []
    else:
        for k in range(lis[i][0],lis[i][1]+1):
            T.append(k)
            S = S | set(T)
        T = []

lis = list(S)
dp  = [0]*(N+1)
dp[1] = 1
MOD = 998244353

for i in range(2,N+1):
    for j in lis:
        if i>j:
            dp[i] += dp[i-j]
            dp[i] %= MOD

print(dp[N]%MOD)

Submission status: Time Limit Exceeded

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

MOD = 998244353

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

mod = 998244353

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


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

for n in range(1, N+1):
    for dis in moves:
        if n - dis >= 1:
            dp[n] += dp[n - dis]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
import numpy as np
from numba import njit
def main():
    large_num = 998244353
    n, k = map(int, input().split())
    n -= 1
    m = map(int, read().split())
    ma = np.zeros(k)
    mb = np.zeros(k)
    cnt = 0
    for a, b in zip(m, m):
        ma[cnt] = a
        mb[cnt] = b
        cnt += 1

    @njit()
    def sol(n, ma, mb):
        dd = np.zeros(n+1)
        for a, b in zip(ma, mb):
            for i1 in range(a, b+1):
                dd[i1] = 1
        s = [i for i, v in enumerate(dd) if v == 1]
        s = np.array(s)
        dp = np.zeros(n+1)
        dp[0] = 1
        for i1 in range(1, n+1):
            for se in s:
                if se > i1:
                    break
                else:
                    dp[i1] += dp[i1 - se]
            dp[i1] = dp[i1] % large_num
        return dp[-1]

    print(int(sol(n, ma, mb)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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-i] += d[pos] % 998244353
            else:
                return


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

print(d[0] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
jump = []
for _ in range(K):
    l, r = map(int, input().split())
    for i in range(l, r + 1):
        jump.append(i)
jump.sort()
# print(jump)
MOD = 998244353
dp = [0] * N
dp[0] = 1
for i in range(1, N):
    for j in jump:
        if i < j:
            continue
        if dp[i - j]:
            dp[i] += dp[i - j]
            dp[i] %= MOD
# print(dp)
print(dp[-1])

Submission status: Time Limit Exceeded

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

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

dp = [0] * (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] + sum(dp[mn:mx + 1])) % m
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 998244353
    n, k = map(int, input().split())
    s = set()
    global ans
    
    for _ in range(k):
        l, r = map(int, input().split())
        for i in range(l, r+1):
            s.add(i)
    s = list(s)
    
    m = [0] * (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]
        m[i] %= MOD
    print(m[n])

        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

arr.discard(0)


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

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

Submission status: Time Limit Exceeded

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

N,K = (int(x) for x in input().rstrip('\n').split())
As = []
n = [x for x in range(1,N+1)]
for _ in range(K):
  L,R = (int(x) for x in input().rstrip('\n').split())
  As.extend(n[L-1:R])
res_d = {0:1}
for i in range(1,N):
  res_d[i] = sum(res_d.get(i-v,0) for v in As)%998244353
print(res_d[N-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

def main():
    MOD = 998244353

    N, K = map(int, input().split())
    move = []
    for i in range(K):
        l, r = map(int, input().split())
        move.extend(list(range(l, r+1)))
    dpt = [0] * N
    dpt[0] = 1

    for i in range(N):
        for m in move:
            if i + m < N:
                dpt[i+m] = dpt[i] + dpt[i+m]
                dpt[i+m] %= MOD

    print(dpt[-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

T = []

for i in range(K):
    if i==0:
        for j in range(lis[i][0],lis[i][1]+1):
            T.append(j)
            S = set(T)
        T = []
    else:
        for k in range(lis[i][0],lis[i][1]+1):
            T.append(k)
            S = S | set(T)
        T = []

lis = list(S)
dp  = [0]*(N+1)
dp[1] = 1
MOD = 998244353

for i in range(2,N+1):
    for j in lis:
        if i>j:
            dp[i] += dp[i-j]

print(dp[N]%MOD)

Submission status: Time Limit Exceeded

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

S=[]

for i in range(k):
  a,b=map(int,input().split(" "))
  c=list(range(a,b+1))
  S=S+c
S=list(set(S))

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

for i in range(n-1):
  for j in range(int(len(S))):
    k=i+S[j]
    if k<=n-1:
      G[k]=(G[k]+G[i])%998244353

print(G[n-1])

Submission status: Time Limit Exceeded

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

l_r_list_1=[]
for i in range(k):
    for j in range(l_r_list[i][0], l_r_list[i][1]+1):
        l_r_list_1.append(j)

mv_list=list(set(l_r_list_1))

dp = [0]*(n)

for i in range(n):
    for j in range(len(mv_list)):
        if i > mv_list[j]:
            dp[i] += dp[i - mv_list[j]]
        elif i == mv_list[j]:
            dp[i] += 1

print(dp[-1] % 998244353)

Submission status: Time Limit Exceeded

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

MOD = 998244353

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

#t = [1,2,3,5,6,7,8,10,11,12,13,14,15]
#t = [1,2]

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

print(flist[-1]%998244353)

Submission status: Time Limit Exceeded

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

N,K=map(int,readline().split())
DIV = 998244353
steps = []
for i in range(K):
  l,r = map(int,readline().split())
  for j in range(l, r + 1):
    steps.append(j)
    
steps = sorted(steps)

dp = [0] * (N)
dp[0] = 1
for i in range(len(dp)):
  for s in steps:
    if i + s >= len(dp):
      break
    dp[i + s] += dp[i]
    dp[i + s] %= DIV
    
print(dp[-1])

Submission status: Time Limit Exceeded

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

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

MOD = 998244353



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

class BinaryIndexedTree():  #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        while idx:
            res += self.tree[idx]
            res %= MOD
            idx -= idx & -idx
        return res

    def add(self, idx, x):
        while idx <= self.n:
            self.tree[idx] += x
            self.tree[idx] % MOD
            idx += idx & -idx

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res + 1

class RAQandRSQ():
    def __init__(self, n):
        self.bit1 = BinaryIndexedTree(n)
        self.bit2 = BinaryIndexedTree(n)

    def add(self, lt, rt, x):
        self.bit1.add(lt, -x * (lt - 1))
        self.bit1.add(rt, x * (rt - 1))
        self.bit2.add(lt, x)
        self.bit2.add(rt, -x)

    def sum(self, lt, rt):
        rsum = self.bit2.sum(rt - 1) * (rt - 1) + self.bit1.sum(rt - 1)
        lsum = self.bit2.sum(lt - 1) * (lt - 1) + self.bit1.sum(lt - 1)
        return rsum - lsum

R = RAQandRSQ(N)
R.add(1, 2, 1)

for i in range(1, N):
    s = R.sum(i, i + 1)
    for l, r in I:

        R.add(min(i + l, N + 1), min(i + r + 1, N + 1), s)

print(R.sum(N, N + 1) % MOD)

Submission status: Time Limit Exceeded

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


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


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

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

        return ret % MOD

    ret = f(N - 1)
    # debug("count", count)
    return ret % MOD


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


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

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

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

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

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


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


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


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

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

main()

Submission status: Time Limit Exceeded

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

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] % mod

print(dp[n] % mod)

Submission status: Time Limit Exceeded

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

data = []
masu = np.zeros(N)
masu[0] = 1

for i in range(K):
  L, R = map(int,input().split())
  if L == R:
    data.append(L)
  else:
    for j in range(L,R+1):
      data.append(j)

for i in range(N):
  if masu[i] >= 1:
    for j in data:
      if i+j <= N-1:
        masu[i+j] += masu[i]
    if masu[N-1] >= 900000000:
      masu[N-1] = int(masu[N-1]) % 998244353

print(int(masu[N-1])%998244353)

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(1,N):
    for k in range(K):
        for j in range(L[k],R[k]+1):
            if i-j<0:
                break
            else:
                dp[i]+=dp[i-j]%998244353
print(dp[N-1]%998244353)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)
n, k = map(int,input().split())
num = [-1]*(n+1)
num[0] = 0
num[1] = 1
s = set()
MOD = 998244353
for i in range(k):
    l, r = map(int,input().split())
    s = s | set(range(l,r+1))
def numpat(n):
    if n<0:
        return 0
    elif num[n]!=-1:
        return num[n]
    tmp = 0
    for i in s:
        tmp += numpat(n-i)
    num[n]=tmp%MOD
    return num[n]
print(numpat(n))

Submission status: Time Limit Exceeded

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

    dp = [0]*(n*2 + 100)
    dp[1] = 1
    dp[2] = -1
    for i in range(1,n + 1):
        dp[i] += dp[i - 1]
        for l,r in LR:
            if i + l > n:
                continue
            dp[l + i] += dp[i]
            dp[r + i + 1] -= dp[i]        
    print(dp[n]%998244353) 
    return

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

for i in range(k):
    tmp = tuple(map(int, input().split()))
    lists += [i for i in range(tmp[0], tmp[1] + 1)]

lists.sort()

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

for i in range(1, n):
    if len(lists) != k and lists[k] <= i:
        k += 1
    for num in lists[:k]:

        dp[i] += dp[i - num]
        dp[i] %= mod

print(dp[n - 1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
LRs = [tuple(map(int, input().split())) for _ in range(K)]
mod = 998244353
    
mem = [0] * (N)
mem[N-1] = 1

for _i in range(N-1):
    i = N-2 - _i
    for l, r in LRs:
        if i+l < N:
            mem[i] += sum(mem[i+l:min(i+r+1, N)])

    mem[i] %= mod

print(mem[0])

Submission status: Time Limit Exceeded

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

minL = min(i[0] for i in LR)

mod = 998244353

result = [1]
for ni in range(1, N):
  result.append(0)
  if N-minL<ni and ni!=N-1: continue
  for l, r in LR:
    for j in range(l, r+1):
      if ni-j<0: continue
      result[ni] = (result[ni]+result[ni-j]) % mod


print(result[N-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

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

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

Submission status: Time Limit Exceeded

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

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

DP =[[0]*N for _ in range(N)]
DP[0][0] = 1

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

#for i in range(N):
  #print(DP[i])
print(DP[N-1][-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
class BITRAQ:
    def __init__(self, n):
        self.n = n + 1
        self.bit = [[0]*(self.n) for _ in range(2)]
    
    def add_sub(self, p, i, x):
        while i < self.n:
            self.bit[p][i] += x
            i += i & -i
    
    def add(self, l, r, x):
        self.add_sub(0, l, -x * (l - 1))
        self.add_sub(0, r, x * (r - 1))
        self.add_sub(1, l, x)
        self.add_sub(1, r, -x)

    def sum_sub(self, p, i):
        s = 0
        while i > 0:
            s += self.bit[p][i]
            i -= i & -i
        return s
    
    def sum(self, i):
        return self.sum_sub(0, i) + self.sum_sub(1, i) * i

    def get(self, i):
        return self.sum(i) - self.sum(i - 1)

p = 998244353

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

hop = []

for i in range(K):
    hop.append(tuple(map(int, input().split())))

dp = BITRAQ(N)

dp.add(1, 2, 1)

for i in range(N - 1):
    for j in range(K):
        dp.add(i + hop[j][0] + 1, min(N + 1, i + hop[j][1] + 2), dp.get(i + 1) % p)

print(dp.get(N) % p)

Submission status: Time Limit Exceeded

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

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


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


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

Submission status: Time Limit Exceeded

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

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+1)
dp[1] = 1

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

class BIT:
    def __init__(self, n, init=None):
        self.size = n
        if init is None:
            self.v = [0] * (n + 1) # don't use bit[0]
        else:
            self.v = [0] + init
            for i in range(1, n):
                if i + (i & -i) <= n: self.v[i + (i & -i)] += self.v[i]

    def sum(self, i):
        '''
        Calculate a[1] + ... + a[i]
        '''
        S = 0
        while i > 0:
            S += self.v[i]
            i -= i & -i
        return S
    
    def modsum(self, i, mod):
        '''
        Calculate a[1] + ... + a[i]
        '''
        S = 0
        while i > 0:
            S += self.v[i]
            S %= mod
            i -= i & -i
        return S


    def add(self, i, x):
        '''
        set a[i] to be a[i] + x
        '''
        assert i > 0
        while i <= self.size:
            self.v[i] += x
            i += i & -i

N, K = map(int, input().split())
segments = [tuple(map(int, input().split())) for _ in range(K)]
bit = BIT(N + 1)
bit.v[1] = 1
for i in range(1, N + 1):
    temp = bit.sum(i)
    for s, t in segments:
        if i + s <= N:
            bit.add(i + s, temp)
            bit.add(min(i + t + 1, N + 1), -temp)
print(bit.modsum(N, MOD))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
N,K=map(int,input().split())
rangs=[]
for _ in range(K):
    l,r=map(int,input().split())
    for i in range(l,r+1):
        rangs.append(i)
from functools import lru_cache
@lru_cache(maxsize=None)
def dynam(n):
    res=0
    for go in rangs:
        if n==go:
            res+=1
        elif n>go:
            res+=dynam(n-go)
    return res
print(dynam(N-1)%998244353)