Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

Constraints

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

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

1 \leq L_i \leq R_i \leq N

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
L_1 R_1
L_2 R_2
:
L_K R_K

Output

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

Sample Input 1

5 2
1 1
3 4

Sample Output 1

4

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

There are 4 possible ways to get to Cell 5:

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

1 \to 2 \to 5,

1 \to 4 \to 5 and

1 \to 5.

Sample Input 2

5 2
3 3
5 5

Sample Output 2

0

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

Sample Input 3

5 1
1 2

Sample Output 3

5

Sample Input 4

60 3
5 8
1 3
10 15

Sample Output 4

221823067

Note that you have to print the answer modulo 998244353.



Sample input:
5 2
1 1
3 4


Sample output:
4

Submission status: Time Limit Exceeded

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

D = []

for _ in range(K):
    L, R = map(int, input().split())

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

D.sort()

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

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

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
s = []
ans = 0

for i in range(k):
    L,R = map(int,input().split())
    
    for j in range(L,R+1):
        s.append(j)
    
s = sorted(set(s))

import collections
q = collections.deque()

q.append(1)
    
while q:
    now = q.popleft()
        
    for i in s:
        if now + i < n:
            q.append(now+i)
        elif now + i == n:
            ans += 1
            break
        else:
            break
            
    ans %= 998244353
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
tuples = []
for i in range(K):
    L,R = map(int,input().split())
    tuples.append((L,R))
M = [0]*(N+1)
M[1]=1
for i in range(1,N+1):
    for t in tuples:
        if t[0] > i:
            continue
        for LS in range(t[0],t[1]+1):
            if LS <= i-1:
                M[i] += M[i-LS]
print(M[N] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
n,k = (int(x) for x in input().split())
s = []
for _ in range(k):
    a,b = (int(x) for x in input().split())
    s+=list(range(a,b+1))
mod = 998244353
    
l = [0]*(n)
s = sorted(s)
min_num = s[0]
for i in range(min_num,n):
    for j in s:
        if j < i:
	        l[i] += (l[i-j])
    if i in s:
        l[i] += 1
    l[i] %= mod
print(l[n-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 998244353

n, k = map(int, input().split())
dp = [0] * n
dp[0] = 1
dp[1] = -1
delta = []
for _ in range(k):
    l, r = map(int, input().split())
    delta.append((l, 1))
    delta.append((r+1, -1))

total = 0
for i in range(n):
    total += dp[i]
    for p, d in delta:
        if i + p >= n:
            continue
        dp[i + p] += total * d
print(total % 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)))
  
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]

print(dp[n-1]%m)

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,1]
b=[0,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.append(t)
    b.append(b[i-1]+a[i])
print(a[N]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    M = []
    mod = 998244353
    for i in range(K):
        a, b = map(int, input().split())
        for j in range(a, b+1):
            M.append(j)
    M = set(M)
    dp = [0]*(N+1)
    dp[1] = 1
    for i in range(2,N+1):
        for s in M:
            if i-s >= 1:
                dp[i] += dp[i-s]%mod
    print(dp[N]%mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
mod = 998244353
step = []
for _ in range(K):
    L,R = map(int,input().split())
    for i in range(L,R+1):
        step.append(i)
step.sort()
dp = [0]*N
dp[0] = 1
for i in range(N-1):
    for j in step:
        if i+j <= N-1:
            dp[i+j] += dp[i] %mod
            dp[i+j] %= mod
        else:
            continue
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
def once(S,m,n):
    a=[]
    for i in range(len(S)):
        for j in range(len(m)):
            a+=[m[j]-S[i]]
    a.sort(reverse=True)
    for j in range(len(a)):
        if a[j]==1:
            n+=1
    for j in range(len(a)):
        if a[len(a)-1]<=1:
            a.remove(a[len(a)-1])
    m=a
    return m,n
def route(N,S):
    n=0
    m=[]
    for j in range(len(S)):
        m+=[N-S[j]]
    for i in range(len(m)):
        if m[i]==1:
            n+=1
    m.sort(reverse=True)
    for j in range(len(m)):
        if m[len(m)-1]<=1:
            m.remove(m[len(m)-1])
    while m!=[]:
        k=[once(S,m,n)[0],once(S,m,n)[1]]
        m=k[0]
        n=k[1]

    return n%998244353
Na,Ka=input().split()
N=int(Na)
K=int(Ka)
S=[]
for i in range(K):
    x,y=input().split()
    S+=[i for i in range(int(x),int(y)+1)]
print(route(N,S))

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):
        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(500*500)

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 = [None for _ in range(N)]
result[0] = 1
#for ni in range(1, N):
def dp(ni):
  result[ni] = 0
  for l, r in LR:
    for j in range(l, r+1):
      if ni-j<0: continue
      result_ni_j = dp(ni-j) if result[ni-j] is None else result[ni-j]
      result[ni] = (result[ni]+result_ni_j) % mod
  return result[ni]


print(dp(N-1))

Submission status: Time Limit Exceeded

Solution code:
#!/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]
    print(dp[N - 1] % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

mod = 998244353

N, K = map(int, input().split())
LR = []

for _ in range(K):
    l, r = map(int, input().split())
    LR.append((l, r))

dp = np.array([0] * (N+1))
dp[1] += 1

for i in range(1, N+1):
    now = dp[i] % mod
    if now:
        for l, r in LR:
            try:
                dp[i+l:i+r+1] += now
            except:
                break

print(dp[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
LR = [tuple(map(int,input().split())) for _ in range(K)]
d = [0]*N
ans = [0]*N
ans[0] = 1
MOD = 998244353
for i in range(N):
    x = ans[i]
    for k in range(K):
        L, R = LR[k]
        if i+L < len(d):
            d[i+L] += x
            d[i+L] %= MOD
        if i+R+1 < len(d):
            d[i+R+1] -= x
            d[i+R+1] %= MOD
    for j in range(i+2, len(d)):
        d[j] += d[j-1]
        d[j] %= MOD
    for j in range(len(d)):
        ans[j] = (ans[j]+d[j]) % MOD
        d[j] = 0
print(ans[-1] % MOD)

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 j in range(l, r + 1):
        step.append(j)
step.sort()
lg = len(step)
dp = [0 for _ in range(n + 1)]
dp[1] = 1
for i in range(n + 1):
    for j in step:
        if j < i:
            dp[i] += dp[i - j] 
        else:
            break

print(dp[n]% 998244353)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
lr = []
for _ in range(k):
    l, r = map(int, input().split())
    lr.append((l, r))
mod = 998244353
dp = [0]*(2*n+1)
dp[0] = 1
dp[1] = -1
now = 1
for i in range(n):
    for l, r in lr:
        dp[i+l] += now
        dp[i+r+1] -= now
    now += dp[i+1]
print(sum(dp[:n])%mod)

Submission status: Time Limit Exceeded

Solution code:

dp = []
syugo = set()

def main():
    global syugo
    global dp
    n, k = map(int, input().split())

    for i in range(k):
        s, e = map(int, input().split())
        for j in range(s, e+1):
            syugo.add(j)

    dp = [0]*n

    for i in range(n):
        for j in syugo:
            if i - j ==0 :
                dp[i] = dp[i] + 1
            elif i - j  > 0:
                dp[i] = dp[i] + dp[i-j]
    ##    rec(n-1)

    print(dp[n-1]%998244353)
main()

Submission status: Time Limit Exceeded

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

mod = 998244353

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

for i in range(1, N):
    for l, r in LR:
        for x in range(l, r+1):
            y = i+x
            if y > N:
                break
            dp[y] += dp[i]
            dp[y] %= mod

print(dp[N])

Submission status: Time Limit Exceeded

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

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

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 998244353

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

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

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

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

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

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

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

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


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

        res = self.ide_ele

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

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

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

"""
go = set()
for l, r in que:
    for i in range(l, r + 1):
        go.add(i)
"""

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

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

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

"""
ナイーブな解法
go = list(go)

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

for i in range(1, N + 1):
    for j in range(len(go)):
        if i + go[j] <= N:
            dp[i + go[j]] += dp[i]
    dp[i] %= mod
print(dp[N] % mod)
"""

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


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, k = map(int, input().split())
sec = np.array([], dtype=np.int)
masu = np.zeros(n, dtype=np.int)
masu[0] = 1
for i in range(k):
    l, r = map(int, input().split())
    sec = np.hstack([sec, np.arange(l,r+1)])
sec.sort()

for i in range(n):
    for step in sec:
        if i+step < n:
            masu[i + step] += masu[i]
            masu[i + step] %= 998244353

print(masu[-1])

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

    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:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def countWays(arr, m, N):
    count = [0 for i in range(N + 1)]

    # base case
    count[0] = 1

    # Count ways for all values up
    # to 'N' and store the result
    for i in range(1, N + 1):
        for j in range(m):

            # if i >= arr[j] then
            # accumulate count for value 'i' as
            # ways to form value 'i-arr[j]'
            if (i >= arr[j]):
                count[i] += count[i - arr[j]]%998244353

                # required number of ways
    return count[N]%998244353


n, k = MAP()
temp = []
for _ in range(k):
    u, v = MAP()
    temp += list(range(u, v + 1))
# print(temp)

print(countWays(temp, len(temp), 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([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:
            break
        dp[i+value]+=dpi%998244353

print(dp[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
num_list = [0] * N
num_list_pure = []
num_list[0] = 1
for i in range(K):
    L,R = map(int,input().split())
    for j in range(L,R+1):
        num_list_pure.append(j)
num_list_pure.sort()
for i in range(1,N):
    for j in range(len(num_list_pure)):
        num_tmp = num_list_pure[j] 
        if num_tmp <= i:
            num_list[i] += num_list[i - num_tmp]
        else:
          break
print(num_list[N-1] % 998244353)

Submission status: Time Limit Exceeded

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

mod = 998244353

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 998244353
    n, k = map(int, input().split())
    s = []
    
    for _ in range(k):
        l, r = map(int, input().split())
        for i in range(l, r+1):
            s.append(i)
    
    m = [0 for _ in range(n + 1)]
    m[1] = 1
    for i in range(1, n+1):
        for j in s:
            if i+j <= n:
                m[i+j] += m[i]
    print(m[n]%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(range(L,R+1))
  
S.sort()

DP =[0]*N
DP[0] = 1

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


m = 998244353

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

for i in range(n):
    for j in range(i):
        d = i - j
        for a in range(k):
            if d >= l[a] and d <= r[a]:
                dp[i] = (dp[i] + dp[j]) % m
                break

print(dp[n-1])

Submission status: Time Limit Exceeded

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

for _ in range(K):
  l, r = map(int, input().split())
  lr += list(range(l, r + 1))
  
for i in range(0, N - 1):
  if dp[i] == 0:
    continue
    
  for j in range(len(lr)):
    if i + lr[j] > N - 1:
      continue
      
    dp[i + lr[j]] += dp[i] % m
    
print(dp[N - 1] % m)

Submission status: Time Limit Exceeded

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

nums = []

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


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

for i in range(2, N + 1):
    for l, r in nums:
        if i - l > 0:
            # print(i, l, r)
            # r = min(r, N)
            dp[i] += cumsum[i - l] - cumsum[max(i - r - 1, 0)]
    cumsum.append(cumsum[-1] + dp[i])

print(dp[-1] % MOD)
# print(dp)
# print(cumsum)

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:
            break
        dp[i+value]+=dpi

print(dp[-1]%998244353)

Submission status: Time Limit Exceeded

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

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

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

S = set()

for left, right in L:
    S = S | set(range(left, right+1))

S = sorted(list(S))

n_list = [0] * N
n_list[0] = 1

for idx, value in enumerate(n_list):
    if value == 0:
        continue
    if S[0] + idx >= N:
        break
    for s in S:
        next_idx = s + idx
        if next_idx >= N:
            break
        n_list[next_idx] += value

print(n_list[-1] % 998244353)

Submission status: Time Limit Exceeded

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

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

S.sort()
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) % 998244353
        A += [s]
        s = 0
        n += 1

print(A[N-1])

Submission status: Time Limit Exceeded

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

mod = 998244353

N, K = map(int, sys.stdin.readline().strip().split())

step = []
for _ in range(K):
    L, R = map(int, sys.stdin.readline().strip().split())
    step.append((L, R))
step.sort()

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


def solve(u):
    if u <= 0:
        return 0

    if dp[u] is not False:
        return dp[u]
    
    dp[u] = 0
    for L, R in step:
        for i in range(L, R + 1):
            dp[u] += solve(u - i)
    return dp[u]


solve(N)

print(dp[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
LR = [tuple(map(int,input().split())) for _ in range(K)]
d = [0]*N
ans = [0]*N
ans[0] = 1
for i in range(N):
    x = ans[i]
    for k in range(K):
        L, R = LR[k]
        if i+L < len(d):
            d[i+L] += x
        if i+R+1 < len(d):
            d[i+R+1] -= x
    for j in range(i+2, len(d)):
        d[j] += d[j-1]
    for j in range(len(d)):
        ans[j] += d[j]
        d[j] = 0
print(ans[-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())
    temp=list(range(l,r+1))
    s+=temp
s=sorted(s)
ans=[0]*(10**6)
ans[0]=1
for i in range(n-1):
    ans[i]=ans[i]%998244353
    for j in s:
        ans[i+j]+=ans[i]
print(ans[n-1]%998244353)

Submission status: Time Limit Exceeded

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


class DFS():
    def __init__(self,N,S):
        self.N = N
        self.S = S
        self.seen = [False] * self.N
        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 = set(S)

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split(" "))
a=[]
for k in range(K):
    l,r=map(int,input().split(" "))
    a+=list(range(l,r+1))
a.sort()
b=[0 for i in range(a[-1]-1)]
b.append(1)
for i in range(N-1):
    b.append(0)
    for j in a:
        b[-1]+=b[-j-1]
print(b[-1]%998244353)

Submission status: Time Limit Exceeded

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

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

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        dp[i] += sum(dp[LL:RR+1])
    dp[i]

print(dp[N] % MOD)

Submission status: Time Limit Exceeded

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

def main():
    n, k = map(int, input().split())
    mod = 998244353
    s = []
    for i in range(k):
        l, r = map(int, input().split())
        s += range(l, r + 1)
    s.sort()
    dp = [0] * n
    dp[0] = 1
    for i in range(n):
        if dp[i] == 0:
            continue
        for d in s:
            if i + d < n:
                dp[i + d] += max(dp[i], 1)
                dp[i + d] %= mod
    print(dp[n - 1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

S=[tuple(f()) for i in [0]*K]
p=998244353

dp=[0]*(N+1)
dp[1]=1
def To(n):
    for l,r in S:
        for i in range(r-l+1):
            if n+l+i<=N:
                dp[n+l+i]=(dp[n+l+i]+dp[n])%p
            else:
                break
                
for n in range(1,N+1):
    To(n)
print(dp[N]%p)

Submission status: Time Limit Exceeded

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)
mod = 998244353

n, k = map(int, input().split())
s = []

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

# s = list(set(s))

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)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    M = []
    mod = 998244353
    for i in range(K):
        a, b = map(int, input().split())
        for j in range(a, b+1):
            M.append(j)
    M = set(M)
    dp = [0]*(N+1)
    dp[1] = 1
    for i in range(2,N+1):
        for s in M:
            if i-s >= 1:
                dp[i] += dp[i-s]
    print(dp[N]%mod)

if __name__ == '__main__':
    main()