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:
''' ===============================
    -- @uthor : Kaleab Asfaw
    -- Handle : kaleabasfaw2010
    -- Bio    : High-School Student
    ==============================='''

# Fast IO
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file): self._fd = file.fileno(); self.buffer = BytesIO(); self.writable = "x" in file.mode or "r" not in file.mode; self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b: break
            ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0; return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)); self.newlines = b.count(b"\n") + (not b); ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1; return self.buffer.readline()
    def flush(self):
        if self.writable: os.write(self._fd, self.buffer.getvalue()); self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file): self.buffer = FastIO(file); self.flush = self.buffer.flush; self.writable = self.buffer.writable; self.write = lambda s: self.buffer.write(s.encode("ascii")); self.read = lambda: self.buffer.read().decode("ascii"); self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout); input = lambda: sys.stdin.readline().rstrip("\r\n")
# Others
# from math import floor, ceil, gcd
# from decimal import Decimal as d
mod = 10**9+7
def lcm(x, y): return (x * y) / (gcd(x, y))
def fact(x, mod=mod):
    ans = 1
    for i in range(1, x+1): ans = (ans * i) % mod
    return ans
def arr2D(n, m, default=0):
    lst = []
    for i in range(n): temp = [default] * m; lst.append(temp)
    return lst
def sortDictV(x): return {k: v for k, v in sorted(x.items(), key = lambda item : item[1])}

def solve(n, k, num):
    n -= 1
    dp = [0] * (n+1)
    dp[0] = 1
    for i in range(1, n+1):
        for x in num:
            if i - x >= 0:
                dp[i] = (dp[i] + dp[i-x]) % 998244353
    return dp[-1]

n, k = list(map(int, input().split()))
num = set()
for i in range(k):
    x, y = list(map(int, input().split()))
    for i in range(x, y+1):
        num.add(i)
print(solve(n, k, num))

Submission status: Time Limit Exceeded

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

MOD = 998244353

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

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

for i in range(N-1):
    for j in interval:
        if j <= N-1 - i:
            dp[i+j] += dp[i]
            dp[i+j] %= MOD

print(dp[N-1])

Submission status: Time Limit Exceeded

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

for i in range(K):
  s = list(map(int, input().split()))
  S.append(s)
  
DP = [0]*N
DP[0] = 1

#print(DP)

for i in range(1,N):
  T = 0
  for s in S:
    l = max(0,i-s[1])
    r = max(0,i-s[0]+1)
    T += sum(DP[l:r])
  DP[i] = T
  #print(DP)
  
print(DP[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
  base = 998244353
  N, K = map(int, input().split(" "))

  step_lengthes = []
  for _ in range(K):
    L, R = map(int, input().split(" "))
    step_lengthes.extend(range(L, R+1))
  step_lengthes.sort()
  dp = [0] * (N+1)
  dp[1] = 1

  for i in range(1, N+1):
    for d in step_lengthes:
      if i+d <= N:
        dp[i+d] += dp[i]
      else:
        break
  print(dp[-1]%998244353)

if __name__ == "__main__":
  resolve()

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    mod = 998244353
    N, K = iim()
    it = map(int, sys.stdin.read().split())
    A = [0] * N
    A[0] = 1

    B = []
    for l, r in zip(it, it):
        for x in range(l, r+1):
            B.append(x)

    B.sort()
    for i in range(N-1):
        if A[i] == 0:
            continue
        for j in B:
            k = i + j
            if k >= N:
                break
            A[k] = (A[k] + A[i]) % mod

    print(A[-1])


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    mod = 998244353

    dp = [0 for i in range(N)]
    dp[0] = 1
    dp = np.array(dp)

    left = N
    for i in range(K):
        left = min(left,LR[i][0])

    for i in range(N):
        for k in range(K):
            l = LR[k][0]
            r = LR[k][1]
            if i + l >= N:
                continue
            else:
                L = i + l
            if i + r >= N:
                R = N - 1
            else:
                R = i + r
            dp[L:R+1] += dp[i]
            dp[L:R+1] %= mod

    # print(dp)
    print(dp[-1])



main()

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
a = [list(map(int, input().split())) for i in range(Q)]
cnt = [0]*N
cnt[0]=1
for i in range(0,N-1):
  for j in range(Q):
    for k in range(a[j][0],a[j][1]+1):
      if i+1+k<=N:
        cnt[i+k]=(cnt[i+k]+cnt[i])%998244353
print(cnt[N-1])

Submission status: Time Limit Exceeded

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

MOD = 998244353


def main():
    N, K = map(int, input().split())
    LR = [tuple(map(int, input().split())) for _ in range(K)]
    S = set()
    for start, end in LR:
        for i in range(start, end + 1):
            S.add(i)
    M = dict()
    M[1] = 1
    for i in range(2, N + 1):
        M[i] = sum([M[i - s] for s in S if (i - s > 0)]) % MOD
    print(M[N])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


def main():
    N, K = map(int, input().split())
    LR = [tuple(map(int, input().split())) for _ in range(K)]
    S = set()
    MOD = 998244353
    for start, end in LR:
        for i in range(start, end + 1):
            S.add(i)
    M = dict()
    M[1] = 1
    for i in range(1, N + 1):
        calc(i, S, M)
    print(M[N] % MOD)


def calc(n: int, S: set, M: dict):
    if n <= 1:
        return
    if n in M:
        return
    M[n] = sum([M[n - s] for s in S if (n - s > 0)])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


def main():
    N, K = map(int, input().split())
    LR = [tuple(map(int, input().split())) for _ in range(K)]
    S = set()
    MOD = 998244353
    for start, end in LR:
        for i in range(start, end + 1):
            S.add(i)
    M = dict()
    M[1] = 1
    for i in range(1, N + 1):
        calc(i, S, M)
    print(M[N] % MOD)


def calc(n: int, S: set, M: dict):
    if n <= 1:
        return
    if n in M:
        return
    for s in S:
        calc(n - s, S, M)
    M[n] = sum([M[n - s] for s in S if (n - s > 0)])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def input_int():
    return(int(input()))

def input_int_list():
    return(list(map(int,input().split())))

def input_int_map():
    return(map(int,input().split()))

def run():
    n, k = input_int_map()

    ranges = []
    for _ in range(k):
        l, r = input_int_map()
        ranges.append((l, r))

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

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

        for l, r in ranges:
            if i + l < n:
                dp[i + l] += dp[i]

            if i + r + 1 < n:
                dp[i + r + 1] -= dp[i]

    result = dp[-1] % 998244353
    print(result)

run()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 998244353

def fft_convolve(f, g):
  Lf, Lg = f.shape[-1], g.shape[-1]
  L = Lf + Lg - 1
  fft_len = 1 << L.bit_length()
  fh, fl = f >> 15, f & (1 << 15) - 1
  gh, gl = g >> 15, g & (1 << 15) - 1
  def conv(f, g):
    Ff = np.fft.rfft(f, fft_len)
    Fg = np.fft.rfft(g, fft_len)
    h = np.fft.irfft(Ff * Fg)
    return np.rint(h)[..., :L].astype(np.int64) % MOD
  x = conv(fl, gl)
  z = conv(fh, gh)
  y = conv(fl + fh, gl + gh) - x - z
  return (x + (y << 15) + (z << 30)) % MOD

def coef_of_generating_function(P, Q, N):
  assert Q[0] == 1 and len(Q) == len(P) + 1
  def convolve(f, g):
    return fft_convolve(f, g)
  while N:
    Q1 = np.empty_like(Q)
    Q1[::2] = Q[::2]
    Q1[1::2] = MOD - Q[1::2]
    P = convolve(P, Q1)[N & 1::2]
    Q = convolve(Q, Q1)[::2]
    N >>= 1
  return P[0]

N, K = map(int, input().split())
Q = np.array([0]*(N+2), np.int64)
Q[0] = 1
Q[1] = -1
for _ in range(K):
  L, R = map(int, input().split())
  Q[L] -= 1
  Q[R+1] += 1

P = np.zeros_like(Q)[:-1]
P[0] = 1
P[1] = -1

print(coef_of_generating_function(P, Q, N-1))

Submission status: Time Limit Exceeded

Solution code:
#dpで素直にやるとO(N^2)だから、累積和で高速化しO(KN)にする

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

s = []
for i in range(k):
  s.append(list(map(int,input().split())))

cnt = [0]*n
cnt[0] = 1
sum = [0]*n
sum[0] = 1
for i in range(1,n):
  for j in range(k):
    if i > s[j][1]:
      cnt[i] += sum[i-s[j][0]] - sum[i-s[j][1]-1]
    elif i >= s[j][0]:
      cnt[i] += sum[i-s[j][0]]
    sum[i] = sum[i-1] + cnt[i]

print(cnt[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
#dpで素直にやるとO(N^2)だから、累積和で高速化しO(KN)にする

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

s = []
for i in range(k):
  s.append(list(map(int,input().split())))

cnt = [0]*n
cnt[0] = 1
sum = [0]*n
sum[0] = 1
for i in range(1,n):
  for j in range(k):
    if s[j][0] == s[j][1] and i >= s[j][0]:
      cnt[i] += cnt[i-s[j][0]]
    elif i > s[j][1]:
      cnt[i] += sum[i-s[j][0]] - sum[i-s[j][1]-1]
    elif i >= s[j][0]:
      cnt[i] += sum[i-s[j][0]]
    sum[i] = sum[i-1] + cnt[i]

print(cnt[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
N,K = [int(i) for i in input().split()]
mod = 998244353
LR = []
S = []
dp = [0]*(N+1)
for i in range(K):
  LR.append([int(i) for i in input().split()])
for lr in LR:
  S.extend(range(lr[0],lr[1]+1))
S.sort()

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

print(dp[-2])

Submission status: Time Limit Exceeded

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

dp = [0]*(n+1)
dp[1] = 1
dpac = [0]*(n+1)
dpac[1] = 1
for i in range(2, n+1):
    for kl, kr in kkn:
        l = i-kr
        r = i-kl
        if r < 0: continue
        l = max(l, 0)
        dp[i] += dpac[r] - dpac[l-1]
    dpac[i] = dpac[i-1] + dp[i]
print(dp[n]%MOD)

Submission status: Time Limit Exceeded

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

LR = [map(int, input().split()) for _ in range(K)]
L, R = [list(i) for i in zip(*LR)]

a = []
for i in range(K):
  a.extend(list(range(L[i], R[i] + 1)))
LR = list(set(a))

DP = [0]*N
DP[0] = 1
for i in range(N):
  if i + LR[-1] >= N:
    LR.pop(-1)
  if len(LR) < 1:
    break
  
  for s in LR:
    local = i + s
    if local < N:
      DP[local] += DP[i]


print(DP[N-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
N,K = [int(i) for i in input().split()]
mod = 998244353
LR = []
S = []
dp = [0]*(N+1)
for i in range(K):
  LR.append([int(i) for i in input().split()])
for i in range(N):
  for lr in LR:
    if lr[0] <= i and i <= lr[1]:
      S.append(i)
S = list(set(S))
#print(S)

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

print(dp[-2])

Submission status: Time Limit Exceeded

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

LR = [map(int, input().split()) for _ in range(K)]
L, R = [list(i) for i in zip(*LR)]

a = []
for i in range(K):
  a.extend(list(range(L[i], R[i] + 1)))
LR = list(set(a))

DP = [0]*N
DP[0] = 1
for i in range(N):
  if i + LR[-1] > N:
    LR.pop(-1)
  if len(LR) < 1:
    break
  for s in LR:
    local = i + s
    if local < N:
      DP[local] += DP[i]


print(DP[N-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
N,K = [int(i) for i in input().split()]
mod = 998244353
LR = []
S = []
dp = [0]*(N+1)
for i in range(K):
  LR.append([int(i) for i in input().split()])
for i in range(N):
  for lr in LR:
    if lr[0] <= i and i <= lr[1]:
      S.append(i)
S = list(set(S))
#print(S)

for i in range(1,N):
  if i in S:
    dp[i] = 1
  T = [S[j] for j in range(len(S)) if S[j] <= i]
  #print(i, T)
  for j in range(len(T)):
    #print(i, T[j], i-T[j])
    dp[i] += 1*dp[i-T[j]]
    dp[i] %= mod

print(dp[-2])

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    ruiseki = [0]*(n+1)

    move_list = [list(map(int, input().split())) for i in range(k)]
    sorted_list = sorted(move_list)
    dp = [0] * (n + 1)
    dp[1] = 1
    ruiseki[1] = 1
    for i in range(2, n+1):
        for rng in sorted_list:
            left = max(0, i - rng[1]-1)
            right = min(i - rng[0], i - 1)
            if left < right:
                dp[i] += ruiseki[right] - ruiseki[left]
            else:
                break
        ruiseki[i] = ruiseki[i - 1] + dp[i]
    print(dp[-1] % 998244353)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    ruiseki = [0]*(n+1)

    move_list = [list(map(int, input().split())) for i in range(k)]
    sorted_list = sorted(move_list)
    dp = [0] * (n + 1)
    dp[1] = 1
    ruiseki[1] = 1
    for i in range(2, n+1):
        for rng in sorted_list:
            left = max(0, i - rng[1]-1)
            right = min(i - rng[0], i - 1)
            if left <= right:
                dp[i] += ruiseki[right] - ruiseki[left]
            else:
                break
        ruiseki[i] = ruiseki[i - 1] + dp[i]
    print(dp[-1] % 998244353)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(v) for v in input().split()]

links = []
for k in range(K):
    L, R = [int(v) for v in input().split()]
    links.append((L, R))

links = sorted(links, key=lambda x: x[1])

count = [1]
sub = [0, 1]
subtotal = 1

for i in range(1, N):
    v = 0
    for l, r in links:
        r2 = i - l + 1
        l2 = i - r
        if l2 < 0:
            l2 = 0
        if r2 >= 0:
            v += sub[r2] - sub[l2]

    count.append(v % 998244353)
    subtotal += v
    sub.append(subtotal)

print(count[-1])

Submission status: Time Limit Exceeded

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

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

moves = [0] * N
moves[0] = 1

rui_wa = [0] * N
rui_wa[0] = 1

for i in range(1, N):
    for j in range(0, K):
        l = max(i - L[j], 0)
        r = max(i - R[j], 0)
        if i - L[j] < 0:
            continue

        moves[i] += rui_wa[l] - rui_wa[r - 1]

    rui_wa[i] = moves[i] + rui_wa[i - 1]



print(moves[N - 1] % 998244353)

Submission status: Time Limit Exceeded

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

def input_int_array():
    return map(int, input().split())

MOD = 998244353

def answer():
    n, k = input_int_array()
    spans = [tuple(input_int_array()) for x in range(k)]

    count = [0 for x in range(n)]
    count[0] = 1

    for i in range(n):
        for j in range(k):
            l, r = spans[j]
            for lr in range(l, r + 1):
                if i + lr < n:
                    count[i + lr] = (count[i + lr] + count[i]) % MOD
                else:
                    break
    print(count[-1] % MOD)


answer()

Submission status: Time Limit Exceeded

Solution code:
(n,_),*s=[[*map(int,t.split())]for t in open(0)]
d=[1,-1]+[0]*2*n
for i in range(n):
  d[i]+=d[i-1]
  for l,r in s:
    d[i+l]+=d[i]
    d[i-~r]-=d[i]
print(d[n-1]%998244353)

Submission status: Time Limit Exceeded

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

LR = [map(int, input().split()) for _ in range(K)]
L, R = [list(i) for i in zip(*LR)]

a = []
for i in range(K):
  a.extend(list(range(L[i], R[i] + 1)))
LR = list(set(a))

DP = [0]*N
DP[0] = 1
for i in range(N):
  for s in LR:
    local = i + s
    if local < N:
      DP[local] += DP[i]


print(DP[N-1] % mod)

Submission status: Time Limit Exceeded

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

def skp(a):
    global ans
    if a == n:
        ans = ans+1
    elif a<n:
        for i in reach:
            skp(a+i)

reach = deque()

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

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

skp(1)
print(ans)

Submission status: Time Limit Exceeded

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

t = [False] * (n+5)

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

s = []

for i,v in enumerate(t):
    if v==True:
        s.append(i)

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

for i in range(2,n+1,1):
    for d in s:
        if i-d>=1:
            dp[i] += dp[i-d]
            dp[i] %= mod

print(dp[n] % mod)

Submission status: Time Limit Exceeded

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

def input_int_array():
    return map(int, input().split())


def answer():
    n, k = input_int_array()
    spans = [tuple(input_int_array()) for x in range(k)]

    count = [0 for x in range(n)]
    count[0] = 1

    for i in range(n):
        for j in range(k):
            l, r = spans[j]
            for lr in range(l, r + 1):
                if i + lr < n:
                    count[i + lr] += count[i]
                else:
                    break
    print(count[-1] % 998244353)


answer()

Submission status: Time Limit Exceeded

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

def input_int_array():
    return map(int, input().split())


def answer():
    n, k = input_int_array()
    spans = [tuple(input_int_array()) for x in range(k)]

    count = [0 for x in range(n)]
    count[0] = 1
    count[1] = -1

    for i in range(n):
        if i > 0:
            count[i] += count[i-1]
        for j in range(k):
            l, r = spans[j]
            r += 1
            if i + l < n:
                count[i + l] += count[i]
            if i + r < n:
                count[i + r] -= count[i]
    print(count[-1] % 998244353)


answer()

Submission status: Time Limit Exceeded

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

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

dp = [0] * (N + 1)
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = i - R[j]
        ri = i - L[j]
        if ri < 1:
            continue
        li = max(1, li)
        dp[i] += dp_sum[ri] - dp_sum[li - 1]
    dp_sum[i] = dp_sum[i - 1] + dp[i]

print(dp[-1] % MOD)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
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,1):
        s.append(j)

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

for i in range(2,n+1,1):
    for d in s:
        if i-d>=1:
            dp[i] += dp[i-d]
            dp[i] %= mod

print(dp[n] % mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K = map(int,input().split())
LR = []
for _ in range(K):
  L,R = map(int,input().split())
  LR += list(range(L,R+1))
LR = np.array(LR)
MOD = 998244353
dp = np.zeros(N,"i8")
dp[0] = 1
for i in range(N):
  lr = (i+LR)
  lr = lr[lr<N]
  dp[lr] = (dp[lr]+dp[i])%MOD
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
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,1):
        s.append(j)

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

for i in range(2,n+1,1):
    for d in s:
        if i-d>=1:
            dp[i] += dp[i-d]

print(dp[n] % mod)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
mod = 998244353
section = set()
dp = [0]*n
dp[0] = 1

for i in range(k):
  l, r = map(int, input().split())
  section = section.union(set(range(l, r+1)))
  

for i in range(n):
  for step in section:
    x = dp[i]
    if i + step < n:
      dp[i+step] = (dp[i+step] + x) % mod
      
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K = map(int,input().split())
LR = []
for _ in range(K):LR.append(list(map(int,input().split())))
MOD = 998244353
dp = np.zeros(N,"i8")
dp[0] = 1
for i in range(N):
  for L,R in LR:
    if i+L<N:
      dp[i+L:i+R+1] += dp[i]
      dp[i+L:i+R+1] %= MOD
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353


def main(N, LR):
    L, R = LR[::2], LR[1::2]
    K = len(L)
    F = np.zeros(N + 10, np.int64)
    F[0] = 1
    for n in range(1, N + 10):
        F[n] += F[n - 1]
        for k in range(K):
            l, r = L[k], R[k] + 1
            if n - l >= 0:
                F[n] += F[n - l]
            if n - r >= 0:
                F[n] -= F[n - r]
        F[n] %= MOD
    ans = F[N - 1] - F[N - 2]
    return ans % MOD


N, K = map(int, readline().split())
LR = np.array(read().split(), np.int64)

print(main(N, LR))

Submission status: Time Limit Exceeded

Solution code:
#
import sys
import math
import itertools

# 整数をいくつか入力
n,k = (int(i) for i in input().split())


lr = [[int(i) for i in input().split()] for i in range(k)] 

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

for i in range(2,n+1):
    for a in lr:
        if a[0] < i:
            dp[i] += ans[i-a[0]]
            if a[1] < i-1:
                dp[i] -= ans[i-a[1]-1]
    ans[i]=ans[i-1]+dp[i]

print(dp[n]%998244353)

Submission status: Time Limit Exceeded

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

t = [False] * 20

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

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

for i in range(2,n+1,1):
    for d in s:
        if i-d>=1:
            dp[i] += dp[i-d]

print(dp[n] % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

mod = 998244353

N, K = rl()
lr = []
for i in range(K):
	l, r = rl()
	lr.append((l,r))
lr.sort()

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

ans = 0
s = 0
flags = [1] * K
for i in range(1, N+1):
	s += dp[i]
	for k in range(K):
		if flags[k] == 0:
			break
		l, r = lr[k]
		if i+l <= N:
			dp[i+l] += s
			if i+r+1 <= N:
				dp[i+r+1] -= s
			else:
				ans += s
				ans %= mod
				break
		else:
			flags[k] = 0
			break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np  # noqa

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

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

jumps = np.array(jumps)
dp2 = np.zeros(N + 1)

dp = np.zeros(N + 1)
dp[1] = dp2[1] = 1
for i in range(2, N + 1):
    for j, jump in enumerate(jumps):
        mn = max(0, i - jump[1])
        mx = max(mn, i - jump[0])
        dp[i] = (dp[i] + dp2[mx] - dp2[mn - 1]) % m
    dp2[i] = (dp[i] + dp2[i - 1]) % m

print(int(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
mod = 998244353
section = set()
dp = [0]*n
dp[0] = 1

for i in range(k):
  l, r = map(int, input().split())
  section = section.union(set(range(l, r+1)))
  

for i in range(n):
  for step in section:
    x = dp[i] % mod
    if i + step < n:
      dp[i+step] += x
      
print(dp[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = map(int, input().split())
s = set()
for i in range(k):
    a, b = map(int, input().split())
    s.update(range(a, b + 1))
s = sorted(list(s))

dp = [0] + [0] * n
dp[1] = 1
for i in range(1, n + 1):
    for j in s:
        if i + j > n:
            break
        else:
            dp[i + j] = (dp[i + j] + dp[i]) % MOD
print(dp[n])

Submission status: Time Limit Exceeded

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

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

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


def func(pos):
    for l, r in area:
        if pos + l - 1 < N:
            a[pos + l-1] += d[pos]
        if pos + r < N:
            a[pos + r] -= d[pos]
    d[pos+1] = d[pos] + a[pos]


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

print(d[N-1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

mod = 998244353

N, K = rl()
lr = []
for i in range(K):
	l, r = rl()
	lr.append((l,r))
lr.sort()

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

ans = 0
s = 0
for i in range(1, N+1):
	s += dp[i]
	for l, r in lr:
		if i+l <= N:
			dp[i+l] += s
			if i+r+1 <= N:
				dp[i+r+1] -= s
			else:
				ans += s
				ans %= mod
				break
		else:
			break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

input = sys.stdin.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())


@njit((i8, i8[:]), cache=True)
def main(N, steps):
    dp = np.zeros(N, np.int64)
    dp[0] = 1
    for i in range(N):
        if steps.size == 0:
            break
        if steps[-1] >= N:
            steps = steps[:-1]
        dp[steps] += dp[i]
        dp[steps] %= mod
        steps += 1

    return dp[N - 1]


N, K = MI()

steps = []
for _ in range(K):
    l, r = MI()
    steps += list(range(l, r + 1))

steps.sort()
steps = np.array(steps, np.int64)

print(main(N, steps))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
# import numba
# from numba import njit, b1, i4, i8, f8

input = sys.stdin.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())


# @njit((i8, i8[:]), cache=True)
def main(N, steps):
    dp = np.zeros(N, np.int64)
    dp[0] = 1
    for i in range(N):
        if steps.size == 0:
            break
        if steps[-1] >= N:
            steps = steps[:-1]
        dp[steps] += dp[i]
        dp[steps] %= mod
        steps += 1

    return dp[N - 1]


N, K = MI()

steps = []
for _ in range(K):
    l, r = MI()
    steps += list(range(l, r + 1))

steps.sort()
steps = np.array(steps, np.int64)

print(main(N, steps))

Submission status: Time Limit Exceeded

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

input = sys.stdin.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())


def main(N, steps):
    dp = np.zeros(N, np.int64)
    dp[0] = 1
    for i in range(N):
        if steps.size == 0:
            break
        steps = steps[steps < N]
        dp[steps] += dp[i]
        dp[steps] %= mod
        steps += 1

    return dp[N - 1]


N, K = MI()

steps = []
for _ in range(K):
    l, r = MI()
    steps += list(range(l, r + 1))

steps.sort()
steps = np.array(steps, np.int64)

print(main(N, steps))

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

mod = 998244353

N, K = rl()
lr = []
for i in range(K):
	l, r = rl()
	lr.append((l,r))

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

ans = 0
s = 0
for i in range(1, N+1):
	s += dp[i]
	for k in range(K):
		l, r = lr[k]
		if i+l <= N:
			dp[i+l] += s
			if i+r+1 <= N:
				dp[i+r+1] -= s
			else:
				ans += s
				ans %= mod
print(ans)