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 = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for _ in range(K)]
mod = 998244353


class LazySegmentTree():
    def __init__(self, array, f, g, h, ti, ei):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
            T x T -> T
            T is dat
        g : func
            binary operation of the monoid
            T x E -> T
            T is dat, E is laz
        h : func
            binary operation of the monoid
            E x E -> T
            E is laz
        ti : T
            identity element of T
        ei : E
            identity element of E
        """
        self.f = f
        self.g = g
        self.h = h
        self.ti = ti
        self.ei = ei
        self.height = height = len(array).bit_length()
        self.n = n = 2**height
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        self.laz = [ei] * (2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def reflect(self, k):
        dat = self.dat
        ei = self.ei
        laz = self.laz
        g = self.g
        return self.dat[k] if laz[k] is ei else g(dat[k], laz[k])

    def evaluate(self, k):
        laz = self.laz
        ei = self.ei
        reflect = self.reflect
        dat = self.dat
        h = self.h
        if laz[k] is ei:
            return
        laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k])
        laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k])
        dat[k] = reflect(k)
        laz[k] = ei

    def thrust(self, k):
        height = self.height
        evaluate = self.evaluate
        for i in range(height, 0, -1):
            evaluate(k >> i)

    def recalc(self, k):
        dat = self.dat
        reflect = self.reflect
        f = self.f
        while k:
            k >>= 1
            dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1))

    def update(self, a, b, x):  # set value at position [a, b) (0-indexed)
        thrust = self.thrust
        n = self.n
        h = self.h
        laz = self.laz
        recalc = self.recalc
        a += n
        b += n - 1
        l = a
        r = b + 1
        thrust(a)
        thrust(b)
        while l < r:
            if l & 1:
                laz[l] = h(laz[l], x)
                l += 1
            if r & 1:
                r -= 1
                laz[r] = h(laz[r], x)
            l >>= 1
            r >>= 1
        recalc(a)
        recalc(b)

    def set_val(self, a, x):
        n = self.n
        thrust = self.thrust
        dat = self.dat
        laz = self.laz
        recalc = self.recalc
        ei = self.ei
        a += n
        thrust(a)
        dat[a] = x
        laz[a] = ei
        recalc(a)

    def query(self, a, b):  # result on interval [a, b) (0-indexed)
        f = self.f
        ti = self.ti
        n = self.n
        thrust = self.thrust
        reflect = self.reflect
        a += n
        b += n - 1
        thrust(a)
        thrust(b)
        l = a
        r = b + 1
        vl = vr = ti
        while l < r:
            if l & 1:
                vl = f(vl, reflect(l))
                l += 1
            if r & 1:
                r -= 1
                vr = f(reflect(r), vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


#RSQ and RAQ
array = [(0, 1)] + [(1, 1)] + [(0, 1)] * 2 * N
f = lambda a, b: (a[0] + b[0], a[1] + b[1])
g = lambda a, b: ((a[0] + a[1] * b) % mod, a[1])
h = lambda a, b: (a + b) % mod
ti = (0, 0)
ei = 0

LST = LazySegmentTree(array=array, ti=ti, ei=ei, f=f, g=g, h=h)
for x in range(1, N):
    v = LST.query(x, x + 1)[0]
    for l, r in LR:
        LST.update(x + l, x + r + 1, v)
ans = LST.query(N, N + 1)
print(ans[0])

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(2, N + 1):
        for s in S:
            if n - s >= 1:
                dp[n] += dp[n - s] % MOD
            else:
                break
    print(dp[N] % MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	N, K = [int(a) for a in input().split(" ")]
	p = 998244353
	interval = []
	for i in range(K):
		L, R = [int(b) for b in input().split(" ")]
		interval.append({
			"left": L,
			"right": R
		})
	interval.sort(key=lambda itv: itv["left"])

	w = [0, 1]
	for i in range(2, N + 1):
		c = 0
		for j in range(len(interval)):
			if i - interval[j]["left"] <= 0:
				break
			if i - interval[j]["left"] > 0 and i - interval[j]["right"] <= 0:
				for k in range(interval[j]["left"], i):
					c = (c + w[i - k]) % p
			else:
				for k in range(interval[j]["left"], interval[j]["right"] + 1):
					c = (c + w[i - k]) % p
		w.append(c)
	print(w[-1])

main()

Submission status: Time Limit Exceeded

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

D = 998244353

Number = []
for lr in LR:
    Number.extend(range(lr[0],lr[1]+1))

position = 1
queue = []
for num in Number:
    temp = num + position
    if temp <= N:
        queue.append(num+position)

count = 0

while(True):
    if len(queue) == 0:
        break
    if queue[0] == N:
        count += 1
        del queue[0]
    else:
        for num in Number:
            temp = queue[0] + num
            if temp <= N:
                queue.append(num+queue[0])
        del queue[0]

print(count%D)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import numpy as np
import sys
sys.setrecursionlimit(10**6)
mod = 998244353

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

lr = []
# sets = set([])
for i in range(k):
    l, r = list(map(int, input().split()))
    # sets.update(set(range(l, r+1)))
    lr.append((l, r))
# print(sets)

lr.sort()

np_lists = np.zeros(n, dtype=int)
np_lists[0] = 1

# lists = [0]*n
# lists[0] = 1

for i in range(n):
    # now = lists[i]
    # for j in sets:
    #     if (i+j) < n:
    #         lists[i+j] += now
    now = np_lists[i] % mod
    for j in range(k):
        l, r = lr[j]
        if i+l >= n:
            k = j
            break
        np_lists[i+l:i+r+1] += now % mod


# print(lists[-1] % mod)
print(np_lists[-1] % mod)

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):
  if result[ni] is not None: return result[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:
import sys
sys.setrecursionlimit(200000000)

MOD = 998244353 
N, K = [int(i) for i in input().split()]
k = []
vals = []
for i in range(K):
  v = [int(i) for i in input().split()]
  vals.extend([*range(v[0], v[1] + 1)])
vals.sort()

d  = {}

def helper(n):
  if n in d:
    return d[n]
  if n == 0:
    return 1
  if n < vals[0]:
    return -1
  count = 0
  for v in vals:
    if n < v:
      break
    r = helper(n - v)
    if r != -1:
      count += r
      count %= MOD
  d[n] = count
  return count
 
print(max(helper(N - 1), 0))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
s=[]
for i in range(k):
    l,r=map(int,input().split())
    for j in range(l,r+1):
        s.append(j)

dp=[0]*n
dp[0]=1

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

print(dp[n-1]%998244353)

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
            else:
                break
    print(dp[n - 1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

li = [0]*(n+2)
lis = []
lis2 =[0]*(3*n)
lis2[1]=1

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

for i in range(1,n+1):
    li[i]+=li[i-1]
    if li[i]==1:
        lis.append(i)

for i in range(1,n+1):
    for j in lis:
        lis2[i]%=998244353
        lis2[i+j]+=lis2[i]

print(lis2[n])

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 998244353
    n, k = map(int, input().split())
    s = []
    
    for kk in range(k):
        if kk>10:
            break
        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())
d = [0]*2*K
for i in range(K):
    d[2*i], d[2*i+1] = map(int, input().split())
a=[0]*(N+1)
b=[0]*(N+1)
a[1]=1
b[1]=1
for i in range(2,N+1):
    t=0
    for j in range(K):
        if i-d[2*j]>0:
            t+=b[i-d[2*j]]
        if i-d[2*j+1]-1>0:
            t-=b[i-d[2*j+1]-1]
    a[i]=t
    b[i]=b[i-1]+a[i]
print(a[N]%998244353)

Submission status: Time Limit Exceeded

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

dp = [0] * N
dp[0] = 1

#S.sort()

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

print(dp[-1] % 998244353)

Submission status: Time Limit Exceeded

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

MOD = 998244353  # type: int


def solve(N: int, K: int, L: "List[int]", R: "List[int]"):
    routes = [0 for _ in range(N)]
    # routes[0] = Decimal(1)
    routes[0] = 1
    moves = []
    for k in range(K):
        moves += list(range(L[k], R[k]+1))
        # moves.append((L[k]))
        # if L[k] != R[k]: moves.append((R[k]))

    moves = sorted(moves)
    for i in range(1, N):
        tmp = 0
        for m in moves:
            if i < m: break
            # tmp += Decimal(routes[i - m])
            tmp += (routes[i - m])
            # print(i, m, tmp)
        routes[i] = tmp % MOD
    # print(routes)
    return routes[N-1] % MOD


# 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))
    print(solve(N, K, L, R))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n, k = i_map()
    l = []
    for i in range(k):
        a,b = i_map()
        for k in range(a,b+1):
            l.append(k)

    ans = [0]*n*2
    for i in l:
        ans[i] += 1

    for i in range(n):
        if ans[i] > 0:
            for k in l:
                ans[i+k] += ans[i]
    print(ans[n-1] % 998244353)


if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
S = []
for i in range(K):
    L,R = map(int,input().split())
    for j in range(L,R+1):
        S.append(j)
S.sort()
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]]

                # required number of ways
    return count[N]

print(countWays(S,len(S),N-1)%998244353)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
w = [0]*1000000
s = []
for _ in range(k):
  l,r = map(int,input().split())
  if l==r:
    s.append(l)
  else:
    for i in range(l,r+1):
      s.append(i)
s.sort()

w[1] = 1
for i in range(2,n+1):
  for num in s:
    if i-num < 1:
      break
    w[i] += w[i-num]
print(w[n]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

s = sorted(s)
MOD = 998244353  
  
dp = [-1] * n
dp[0] = 1

def ans(i):
  if dp[i] == -1:
    dp[i] = sum( 
      ans(i - si)
      for si 
      in s
      if i >= si
    ) % MOD
  return dp[i]

print(ans(n-1))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import numpy as np
import sys
sys.setrecursionlimit(10**6)
mod = 998244353

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

lr = []
# sets = set([])
for i in range(k):
    l, r = list(map(int, input().split()))
    # sets.update(set(range(l, r+1)))
    lr.append((l, r))
# print(sets)

lr.sort()

np_lists = np.zeros(n, dtype=int)
np_lists[0] = 1

# lists = [0]*n
# lists[0] = 1

for i in range(n):
    # now = lists[i]
    # for j in sets:
    #     if (i+j) < n:
    #         lists[i+j] += now
    now = np_lists[i]
    for j in range(k):
        l, r = lr[j]
        if i+l >= n:
            k = j
            break
        np_lists[i+l:i+r+1] += now


# print(lists[-1] % mod)
print(np_lists[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
from numba import jit
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

@jit
def F():
    for j in range(1,N):
        for s in S:
            if j + s > N or step[j] == 0:
                continue
            step[j+s] += (step[j]%998244353)
            step[j+s] %= 998244353
    return step[N]

print(F())

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
n, k = map(int, input().split())
s = []
for _ in range(k):
    l, r = map(int, input().split())
    s.extend([x for x in range(l, r+1)])

score = [0 for _ in range(n)]
score[0] = 1
for i in range(n):
    for x in s:
        if i+x >= n:
            continue
        score[i+x] = (score[i]+score[i+x])%mod

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

Submission status: Time Limit Exceeded

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

T = []
oklis = [0]*(N+1)

for i in lis:
    for j in range(i[0],i[1]+1):
        oklis[j]=1

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

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

print(dp[N]%MOD)

Submission status: Time Limit Exceeded

Solution code:
# range update
# point query

M = 998244353

class SegmentTreeNode:
	def __init__(self, start, end):
#		print("s", start, end)
		self.value = 0
		self.start = start
		self.end = end
		self.width = end - start
		if self.width > 1:
			w2 = self.width // 2
			self.left = SegmentTreeNode(start, start + w2)
			self.right = SegmentTreeNode(start + w2, end)
	
	def add(self, start, end, value):
		if self.start >= start and self.end <= end:
			self.value = (self.value + value) % M
		elif self.width > 1 and (self.start < end and start < self.end):
			self.left.add(start, end, value)
			self.right.add(start, end, value)
	
	def sum(self, index):
		s = 0
		if self.start <= index and index < self.end:
			s = (s + self.value) % M
			if self.width > 1:
				s = (s + self.left.sum(index) + self.right.sum(index)) % M
		return s
	
class SegmentTree:
	def __init__(self, n):
		width = 1
		while width < n:
			width *= 2
		self.root = SegmentTreeNode(0, width)
		self.root.value = 0
	
	def add(self, start, end, value):
		self.root.add(start, end, value)
	
	def sum(self, index):
		return self.root.sum(index)
	
	def to_list(self):
		values = []
		for i in range(N):
			values.append(self.sum(i))
		return values

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

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

st = SegmentTree(N + 1)
st.add(1, 2, 1)

for i in range(N):
#	print(st.to_list())
	count = st.sum(i)
	for R, L in sects:
		st.add(i + R, i + L + 1, count)

#print(st.to_list())

print(st.sum(N))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from functools import lru_cache

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

INF = 1 << 60


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap

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


N, K = read_int_n()
LR = [read_int_n() for _ in range(K)]
print(f(1))

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

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



# if __name__ == '__main__':
#     main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
ans=[0]*(n+1)
ans[1]=1
cnt=[]
for i in range(k):
    l,r=map(int,input().split())
    for j in range(l,r+1):
        cnt.append(j)
cnt.sort()
cnt2=1
cnt3=0
mod=998244353
if len(cnt)==n:
    print(pow(2,n-2,mod))
else:
    for i in range(1,n):
        if len(cnt)==0:
            break
        for j in range(len(cnt)):
            if i+cnt[j]>n:
                cnt=cnt[:j]
                break
            ans[i+cnt[j]]+=ans[i]
            ans[i+cnt[j]]%=mod
    print(ans[n])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
mod = 998244353
R = []
num = [0 for i in range(N)]
num[0] = 1
for i in range(K):
  R.append(list(map(int, input().split())))
for j in range(0, N):
  for k in range(len(R)):
    if j + R[k][0] < N:
      num[j + R[k][0]] += sum(num[:j+1])
    if j + R[k][1] + 1 < N:
      num[j + R[k][1] + 1] -= sum(num[:j+1])
  if j == 0:
    num[0] = 0
ans = sum(num) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-


def main():
    n, m = map(int, input().split())
    p = [list(map(int, input().split())) for _ in range(m)]
    s = set()
    for pp in p:
        s |= set(range(pp[0], pp[1]+1))
    s = list(s)
    s.sort()
    d = dict()
    d[1] = 1
    for i in range(2, n+1):
        ans = 0
        for ss in s:
            if i-ss > 0:
                ans += d[i - ss]
        d[i] = ans
    print(d[n] % 998244353)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = []
for _ in range(K):
    x, y = map(int, input().split())
    for i in range(x, y+1):
        S.append(i)
ALL = [0] * (N)
ALL[0] = 1
for i in range(N):
    for k in S:
        if k > i:
            next
        else:
            ALL[i] += ALL[i-k]
            ALL[i] = ALL[i] % 998244353
print(ALL[N-1])

Submission status: Time Limit Exceeded

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

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

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

print(dp[N - 1])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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


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

INF = 1 << 60


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap

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


N, K = read_int_n()
LR = [read_int_n() for _ in range(K)]
print(f(1))

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

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



# if __name__ == '__main__':
#     main()

Submission status: Time Limit Exceeded

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(k)]
mod = 998244353

s.sort()

dp = np.zeros(n * 2)
dp[1] = 1

for i in range(1, n):
    for l, r in s:
        dp[i + l:i + r + 1] += dp[i]
        dp[i + l:i + r + 1] %= mod

ans=int(dp[n] % mod)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
 
def main():
 
    input = sys.stdin.readline
 
    N,K = map(int,input().split())
 
    S = set()
 
    mod = 998244353
 
    for i in range(K):
        l,r = map(int,input().split())
 
        for i in range(l,r+1):
            S.add(i)
 
    masu = [0] * N
 
    masu[0] = 1
 
    for i in range(N):
        for j in S:
            if i+j < N:
                masu[i+j] += masu[i]
                masu[i+j] %= mod
 
    print(masu[N-1] % mod)
    
 
if __name__ == "__main__":
    main()

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(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:
n, k = list(map(int, input().split()))
s = [0] * k
for i in range(k):
    s[i] = list(map(int, input().split()))

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

print(dp[n] % mod)