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)
    

    class BucketRAQ:
        """ 1 点に対する質問クエリ、区間に対する加算クエリ (Range Add Query)"""

        def __init__(self, total_size: int, chunk_size: int=512):
            if total_size < chunk_size:
                chunk_size = total_size
                # raise ValueError(f"BucketRAQ.__init__(): chunk size should be <= total_size. got total: {total_size}, chunk: {chunk_size}")
            self.size = total_size    # 列の長さ
            self.chunk_size = chunk_size    # 何個ごとに bucket として分割されるか
            self.chunk_num = (total_size + chunk_size - 1) // chunk_size    # bucket の個数
            self.bucket_add = [0] * self.chunk_num
            self.data = [0] * self.size
        

        def _parent(self, data_ind: int) -> int:
            """データインデックスからバケットのインデックスを得る"""
            return data_ind // self.chunk_size
        
        def _child(self, bucket_ind: int) -> Tuple[int, int]:
            """バケットインデックスから管轄データのインデックス範囲 [l, r) を得る"""
            l = bucket_ind * self.chunk_size
            r = min((bucket_ind + 1) * self.chunk_size, self.size)
            return l, r
        
        
        def build(self, L: Sequence[Num]) -> None:
            """ O(n) で初期配列 L に対応したバケットを構築する"""
            for i, num in enumerate(L):        
                self.data[i] = num
        
        
        def range_add(self, l: int, r: int, num: Num) -> None:
            """ O(lgn) で [l,r) の区間に num を足す"""
            if not (0 <= l <= r <= self.size):
                raise IndexError(f"Bucket_RAQ.range_add(): invalid slices (0 <= l <= r <= {self.size} is required). got l: {l}, r: {r}")
            for bucket_ind in range(self.chunk_num):
                # 現在の bucket の管轄範囲は [i, j)
                i, j = self._child(bucket_ind)
                if r <= i:
                    break
                if j <= l:
                    continue
                # 対象区間が bucket を包み込んでいる時
                if l <= i and j <= r:
                    self.bucket_add[bucket_ind] += num
                    self.bucket_add[bucket_ind] %= mod    # mod
                # 部分的にかぶっている時、現在のバケットに含まれている対象区間の部分区間のみ計算する
                else:
                    for data_ind in range(max(l, i), min(r, j)):
                        self.data[data_ind] += num
                        self.data[data_ind] %= mod    # mod


        def get(self, i: int) -> Num:
            """ O(1) で L[i] を得る"""
            return (self.bucket_add[self._parent(i)] + self.data[i]) % mod    # mod
    

    n, k = mi()
    intervals = [lmi() for _ in range(k)]
    bucket = BucketRAQ(2 * n + 1)
    bucket.data[0] = 1
    for i in range(n):
        p = bucket.get(i)
        # print(p)
        # print(bucket.data)
        for l, r in intervals:
            bucket.range_add(i+l, i+r+1, p)
    print(bucket.get(n-1))
        

        


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys, copy, itertools,heapq
input = sys.stdin.readline

n,k = map(int, input().split())
LR = [list(map(int, input().split())) for i in range(k)]
S = []
for i in range(k):
  a = LR[i][1] - LR[i][0]
  b = LR[i][0]
  for j in range(a+1):
    S.append(b)
    b += 1
S.sort()
    
DP = [0] * n
DP[0] = 1  # 0が1番目
for i in range(n):
  for j in S:
    if i+j > n-1:
      continue #list外となる
    else:
      DP[i+j] = (DP[i+j] + DP[i]) % 998244353

ans = DP[n-1] % 998244353

#print(LR)
#print(S)
#print(DP)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import bisect

mod = 998244353

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

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

for i in range(k):
    l, r = map(int,input().split())
    area[l] += 1
    if r+1 <= n:
        area[r+1] -= 1
        

area = list(itertools.accumulate(area))    
able = [i for i,v in enumerate(area) if v==1]

for i in range(1,n+1):
    for d in able:
        if i-d <= 0:
            break
        dp[i] = (dp[i]+dp[i-d])%mod

print(dp[n]%mod)

Submission status: Time Limit Exceeded

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

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))
def cum_sum(lst):
    cums = [0] * (len(lst)+1)
    cums[1] = lst[0]
    for i in range(2,len(lst)+1):
        cums[i] = cums[i-1] + lst[i-1]
    return cums

n,k = mp()
mod = 998244353
s = [0]*(n+3)
for i in range(k):
    a,b = mp()
    s[a] += 1
    s[b+1] -= 1
s = cum_sum(s)[1:]
se = set()
for i in range(n+1):
    if s[i] > 0:
        se.add(i)
se = list(se)
dp = [0]*(n+1)
dp[1] = 1
for i in range(2, n+1):
    for j in range(len(se)):
        if i - se[j] > 0:
            dp[i] += dp[i-se[j]]
            dp[i] %= mod
print(dp[n])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
s=[]
data=set(s)
for i in range(k):
    x,y=map(int,input().split())
    while(1):
        data.add(x)
        if(x>=y):
            break
        x+=1
        
dp=[0 for i in range(n+1)]
dp[1]=1
for i in range(1,n):
    for j in data:
        if(i+j<=n):
            dp[i+j]+=dp[i]
print(dp[n]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

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

def main():
    MOD = 998244353

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

    n_row = N//min(move) + 1

    dpt = np.array([[0] * N for i in range(n_row)], dtype="int64")
    dpt[0][0] = 1

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

    result = 0
    for i in range(n_row):
        result += dpt[i][-1]
    print(result%MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,k=map(int,input().split())
can=[]
for i in range(k):
    l,r=map(int,input().split())
    for j in range(l,r+1):
        can.append(j)
table=[0]*n
table[0]=1
que=[0]
heapq.heapify(que)
can.sort()
while que:
    now=heapq.heappop(que)
    for j in can:
        if now+j<n:
            table[now+j]+=table[now]
            if not now+j in que:
                heapq.heappush(que,now+j)
print(table[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

mod=998244353

n,k=nii()
hanni=[]
for i in range(k):
  l,r=nii()
  hanni+=[j for j in range(l,r+1)]

dp=[0]*n
dp[0]=1
for i in range(n):
  for j in hanni:
    if i-j>=0:
      dp[i]+=dp[i-j]
      dp[i]=dp[i]%mod

print(dp[-1])

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 q in range(l,r+1):
        S.add(q)
ps = [0] * N
for a in S:
    if a < N:
        ps[a] = 1
for i in range(N):
    for a in S:
        if i-a >= 0:
            ps[i] += ps[i-a]
print(ps[N-1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K = [int(a) for a in input().split()]
dp = [0]*N
dp[0] = 1
k = [0]*N
for _ in range(K):
    L,R = [int(a) for a in input().split()]
    for i in range(L,R+1): k[i-1]=1
#print(dp,k)
f = 998244353
for i in range(1,N):
    dp[i] = np.dot(dp[:i],k[:i][::-1]) %f
    #print(dp,dp[:i],k[:i][::-1])
print(int(dp[-1]))

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())
    L = [x for x in range(l,r+1)]
    S = S + L
    #print(S)
    
dp = [0]*(n+1)
dp[0] = 1
for j in range(n):
    for i in S:
        #print(j,i)
        if j-i >=0:
            dp[j] += dp[j-i]
print(dp[n-1]%mod)

Submission status: Time Limit Exceeded

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

dp=[0]*(n+1)
dp[0]=1
s=[]
for i in range(k):
    l,r=map(int,input().split())
    s.extend( [j for j in range(l,r+1)] )

for i in range(1,n+1):
    tmp=0
    for j in range(len(s)):
        tmp+=dp[i-s[j]]
    dp[i]=tmp%mod
print(dp[-2])

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+=[i for i in range(l,r+1)]
    S.sort()

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

for i in range(2,N+1):
    for j in S:
        if i<j:
            break
        else:
            dp[i]+=dp[i-j]
#print(S)
#print(dp)
print(dp[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
mod = 998244353
s = set()
for _ in range(k):
    l, r = map(int, input().split())
    s = s.union(set(list(range(l, r+1))))

s = sorted(list(s))
leap = [0 for _ in range(n + 1)]
leap[1] = 1
for i in range(1, n):
    base = leap[i]
    if base == 0:
        continue
    for j in s:
        if i + j > n:
            break
        leap[i+j] += base
        leap[i+j] %= mod

print(leap[n])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = []
for j in range(K):
    LRj = list(map(int, input().split()))
    for s in range(LRj[0], LRj[1] + 1):
        S.append(s)

m =  998244353

# print(S)

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

ans = dp[N - 1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
#coding: utf-8

P = 998244353
N, K = (int(x) for x in input().split())
S = [[int(x) for x in input().split()] for _ in range(K)]
S.sort()

DP = [0] * (N + 1)

DP[0] = 1
for now in range(N):
    for s in S:
        for i in range(s[0], s[1]+1):
            if now + i < N:
                DP[now + i] += DP[now]
                DP[now + i] %= P
print(DP[N-1] % P)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from typing import Collection

n,k = map(int,input().split())
lr = [tuple(map(int,input().split())) for i in range(k)]

s = list()
for li,ri in lr:
    s.extend(list(range(li,ri+1)))

"""dp = [0]*(n+10)
dp[0] = 1
q = deque([0])
while(q):
    print(dp)
    now = q.popleft()
    for si in s:
        if now+si < n:
            dp[now+si] += dp[now]
            q.append(now+si)
print(dp)
print(dp[n-1])
"""
mod = 998244353
ans = [0]*(n)
ans[0] = 1
for i in range(n):
    now = ans[i]
    if now:
        for si in s:
            if i+si < n:
                ans[i+si] += now
#print(ans)
print(ans[-1]%mod)

Submission status: Time Limit Exceeded

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

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

ans_list = [0 for _ in range(N)]
ans_list[-1] = 1

for i in range(N - 1, -1, -1):
    for j in range(len(move_list)):
        step = move_list[j]
        idx = i - step
        if idx < 0:
            continue
        ans_list[idx] += ans_list[i]
ans_num = ans_list[0]
ans_num = ans_num % 998244353
print(ans_num)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
from decimal import Decimal
# from fractions import Fraction
# sys.setrecursionlimit(100000)
mod = 998244353
INF=float('inf')
 
n,k=mdata()
lis=[]
dp=[0]*(n)
dp[0]=1
for i in range(k):
    l,r=mdata()
    for j in range(l,r+1):
        lis.append(j)
lis.sort()
for i in range(1,n):
    for j in lis:
        if j>i:
            break
        dp[i]=(dp[i]+dp[i-j])%mod
out(dp[-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,k  = map(int, input().split())
s = []
alist = [0] * 1_000_000
alist[1] = 1    # start point

for i in range(k):
    s_i = list(map(int, input().split()))
    s.extend([x for x in range(s_i[0], s_i[1] + 1)])

for i in range(n):
    if alist[i] == 0: continue
    for j in range(len(s)):
        alist[i+s[j]] += alist[i]
print(alist[n] % 998244353)

Submission status: Time Limit Exceeded

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

N,K = map(int,input().split())
S = []
MOD = 998244353
for i in range(K):
    l,r = map(int,input().split())
    for x in range(l,r+1):
        S.append(x)
S.sort()
dp = [0]*N
dp[0] = 1

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

print(dp[N-1]%MOD)

Submission status: Time Limit Exceeded

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

MOD = 998244353  # type: int


def solve(N: int, K: int, L: "List[int]", R: "List[int]"):
    dp = [0] * (N + 1)
    dp[1] = 1
    s = []
    for i in range(K):
        for j in range(L[i], R[i]+1):
            s.append(j)
    s.sort()
    for i in range(1, N+1):
        for j in s:
            if i - j >= 1:
                dp[i] += dp[i-j]
                dp[i] %= MOD
            else:
                break
    print(dp[N]%MOD)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    L = [int()] * (K)  # type: "List[int]"
    R = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    solve(N, K, L, R)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

mod=998244353

n,k=nii()
hanni=[]
for i in range(k):
  l,r=nii()
  hanni+=[j for j in range(l,r+1)]

dp=[0]*n
dp[0]=1
for i in range(n):
  for j in hanni:
    if i-j>=0:
      dp[i]+=dp[i-j]
      dp[i]=dp[i]%mod

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
step=[]
for i in range(K):
    l,r=map(int,input().split())
    for i in range(l,r+1):
        step.append(i)
        
dp=[0]*(N+1) #jマス目へ行く方法の個数を収納
dp[1]=1
mod=998244353

for i in range(2,N+1):
    for x in step:
        if i >= x+1:
            dp[i] += dp[i-x]
            dp[i] %= mod
            
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
mod=998244353
dp=[0]*2*n
dp[n]=1
l=[list(map(int,input().split(" "))) for i in range(k)]
for i in range(n,2*n):
    for j in range(k):
        for m in range(l[j][0],l[j][1]+1):
          dp[i]+=dp[i-m]%mod
print(dp[2*n-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(300000)

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

S_tmp = {}
for _ in range(K):
    l, r = map(int, input().split())
    S_tmp.update({ l : r })
#S = []
S_ = []
for l, r in sorted(S_tmp.items(), key=lambda x:x[0]):
    #S.extend( list(range(l,r+1)) )
    S_.append((l,r))


import numpy as np

A = np.array([0 for _ in range(N+1)])

#from functools import lru_cache
#@lru_cache(maxsize=None)

A[1] = 1
for n in range(2,N+1):
    A[n] = sum([ A[max(n-r,1):n-l+1].sum() % L for (l,r) in S_ if l < n ]) % L

print(A[n] % L)

def compute(n):
    if n == 1:
        return 1
    a = 0
    for s in S:
        if s >= n:
            break
        if A[n-s] is None:
            A[n-s] = compute(n-s)
        a += A[n-s]
    return a % L

#print(compute(N) % L)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353


def solve():
    N, K = map(int, input().split())
    S = []
    for _ in range(K):
        l, r = map(int, input().split())
        S += list(range(l, r+1))
    S.sort()
    dp = [0] * N
    dp[0] = 1
    for i in range(N-1):
        for s in S:
            if i + s > N-1:
                break
            dp[i+s] = (dp[i+s] + dp[i]) % mod
    print(dp[-1])


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

D = [1]
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:
MOD = 998244353
N, K = map(int, input().split())
s = set()
for i in range(K):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        s.add(j)
m = max(s)

p = [0] * (N + m)
p[m] = 1
for i in range(m + 1, N + m):
    c = 0
    for j in s:
        c += p[i - j]
    p[i] = (c % MOD)
    

print(p[N + m -1] % MOD)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
#coding: utf-8

P = 998244353
N, K = (int(x) for x in input().split())
S = [[int(x) for x in input().split()] for _ in range(K)]
S.sort()

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

DP[0] = 1
for now in range(N):
    for s in S:
        for i in range(s[0], s[1]+1):
            DP[now + i] += DP[now]
            DP[now + i] %= P
print(DP[N-1] % P)

Submission status: Time Limit Exceeded

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


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

for i in range(K):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        S.add(j)

S = sorted(list(S))
dp = [0] * (N + 1)
flag = [0] * (N + 1)
dp[1] = 1

def f(n):
    if flag[n]:
        return dp[n]
    flag[n] = 1
    ret = dp[n]
    for step in S:
        if n < step:
            break
        ret += f(n - step) % MOD
        ret %= MOD
    dp[n] = ret
    return ret

print(f(N))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
route=[]
mod=998244353
for i in range(k):
  l,r=map(int,input().split())
  for j in range(l,r+1):
    route.append(j)
route.sort()
num=[0]*(n)
num[0]=1
for i in range(n):
  for j in route:
    try:
      num[i+j]+=num[i]
      num[i+j]%=mod
    except:
      break
print(num[n-1])

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np

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


S = []
for k in range(K):
    for i in range(LR[k][0], LR[k][1] + 1):
        S.append(i)

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

def move(x):
    res = -1
    if memo[x] != -1:
        res = memo[x]
    elif x < 0:
        res = 0
    elif x == 0:
        res = 1
    else:
        tmp = 0
        S_cand = [s for s in S if s <= x]
        for s in S_cand:
            tmp += move(x - s)
        res = tmp
    if x >= 0:
        memo[x] = res
    return res

for i in range(N):
    move(i)
res =  move(N - 1) % 998244353
print(res)
# print(memo)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    ds = set()
    for _ in range(k):
        l, r = map(int, input().split())
        ds = ds | {i for i in range(l, r + 1)}
    dp = [0] * (n + 1)
    dp[1] = 1

    for i in range(1, n + 1):
        for d in ds:
            if i + d <= n:
                dp[i + d] = (dp[i + d] + dp[i]) % 998244353

    print(dp[-1] % 998244353)


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

S = list()
for l,r in LR:
  S.extend(list(range(l, r+1)))
S = sorted(S)

path_num_dict = {1:1}
for i in range(2, N+1):
  path_num = 0
  for d in S:
    j = i - d
    if j >= 1:
      path_num += path_num_dict[j] % 998244353
    else:
      break
  path_num_dict[i] = path_num % 998244353
print(path_num_dict[N])

Submission status: Time Limit Exceeded

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

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

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

step = sorted(list(set(list(itertools.chain.from_iterable(step)))))
max_step = len(step) - 1
ok_step = 0
step_iter = 0

if step[0] == 1:
  ok_step = 1
  step_iter = 1

for i in range(2,n+1):
  if step[step_iter]+1 == i:
    ok_step += 1
    if step_iter != max_step:
      step_iter += 1
  for j in range(ok_step):
    dp[i] += dp[i-step[j]] % 998244353
    
print(dp[n]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)
import itertools as it
import collections as cl
from collections import deque
import math
from functools import reduce
from collections import defaultdict
MOD = 998244353


def li():
    return [int(x) for x in input().split()]

N, K = li()

s = set()
for _ in range(K):
    a, b = li()
    for i in range(a, b+1):
        s.add(i)

# dp[i]: マスiに到達する方法の個数
dp = [0] * (N+1)
dp[0] = 1
for i in range(N):
    for j in range(1,N-i):
        if j in s:
            dp[i+j] += dp[i]
            dp[i+j] %= MOD
print(dp[N-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys, copy, itertools,heapq
input = sys.stdin.readline

n,k = map(int, input().split())
LR = [list(map(int, input().split())) for i in range(k)]
S = []
for i in range(k):
  a = LR[i][1] - LR[i][0]
  b = LR[i][0]
  for j in range(a+1):
    S.append(b)
    b += 1
S.sort()
    
DP = [0] * n
DP[0] = 1  # 0が1番目
for i in range(n):
  for j in S:
    if i+j > n-1:
      continue #list外となる
    else:
      DP[i+j] += DP[i]

ans = DP[n-1] % 998244353

#print(LR)
#print(S)
#print(DP)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
dp = [0]*(n+1)
dp[1] = 1
li = []
c = 998244353
for _ in range(k):
    x, y = map(int, input().split())
    for i in range(x, y+1):
        li.append(i)
for i in range(n+1):
    for j in li:
        if i > j:
            dp[i] = (dp[i]+dp[i-j])
print(dp[-1]%c)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    numbers = []
    for _ in range(K):
        L, R = map(int, input().split())
        for i in range(L, R + 1):
            numbers.append(i)
    numbers.sort()
    dp = [0] * N
    dp[0] = 1
    p = 998244353
    for i in range(N):
        for j in numbers:
            if i + j < N:
                dp[i + j] = (dp[i+j] + dp[i]) % p
            else:
                break
    print(dp[N-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dp = [0]*N

for i in range(N):
    for j in range(i):
        if i-j in S:
            dp[i] += dp[j]
    if i+1 in S:
        dp[i] += 1

print(dp[N-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
class BIT(object):
    def __init__(self, N, init=0, mod=1):
        self.N = N
        self.bit = [init for _ in range(N)]
        self.mod = mod

    def add(self, k, w):
        x = k
        while x < self.N:
            self.bit[x] += w % self.mod
            self.bit[x] %= self.mod
            x |= x + 1

    def sum(self, k):
        s = 0
        x = k - 1
        while x >= 0:
            s += self.bit[x]
            s %= self.mod
            x = (x & (x + 1)) - 1
        return s

MOD = 998244353
n, k = map(int, input().split())
seg = [list(map(int, input().split())) for _ in range(k)]
bit = BIT(n, mod=MOD)
bit.add(0, 1)

for i in range(1, n):
    x = 0
    for l, r in seg:
        x += (bit.sum(max(0, i - l + 1)) - bit.sum(max(0, i - r))) % MOD
        x %= MOD
    bit.add(i, x)
print((bit.sum(n) - bit.sum(n - 1)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
# 明らかにdp、あるマスに乗っているときそれまでの履歴とかが全く意味をなさないから
# dp[i]: マス目iにいるときのそこまでの移動方法の合計
# dp[i+1] = dp[i]
# 最悪N*K掛かりそうな気がするけどnumpyなら早いんかなぁ？だとしたら簡単すぎる問題な気もするけど。。。？

N,K = map(int,input().split())
L = 998244353
LR = [0] * K
for i in range(K):
    l,r = map(int,input().split())
    LR[i] = [l,r]
import numpy as np
dp = np.array([0] * (N+1))

dp[1] = 1
for i in range(1,N+1):
    for l,r in LR:
        dp[i+l:i+r+1] += dp[i]
        dp[i+l:i+r+1] %= L

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
N,K=list(map(int,input().split()))
method=[]
for x in range(K):
	a,b=list(map(int,input().split()))
	method += list(range(a,b+1))
method.sort()
#print(method)
nums=[0]*(N+1)
nums[1]=1
for x in range(1,N):
	for step in method:
		if x+step>N:
			break
		nums[x+step]+=nums[x]
		#print(nums[x+step],"+=",nums[x])
print(nums[N]%998244353)
#print(nums)