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())
A=[0]*K
B=[0]*K
p=998244353
for i in range(K):
  A[i],B[i]=map(int,input().split())

dp=[0]*N
dp[0]=1
for i in range(1,N):
  for j in range(K):
    if i>=B[j]:
      dp[i]+=sum(dp[i-B[j]:i-A[j]+1])%p
    elif i>=A[j]:
      dp[i]+=sum(dp[:i-A[j]+1])%p
print(dp[-1]%p)

Submission status: Time Limit Exceeded

Solution code:

from bisect import bisect_left,bisect

icase=0
if icase==0:
    n,k=map(int,input().split())

    s=[]
    for i in range(k):
        li,ri=list(map(int,input().split()))
        for i in range(li,ri+1):
            s.append(i)
elif icase==1:
    n,k=5,2
    s=[1, 3, 4]
elif icase==2:
    n,k=60,3    
    s=[5, 6, 7, 8, 1, 2, 3, 10, 11, 12, 13, 14, 15]

s.sort()

mod=998244353

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

for i in range(1,n):
    ir=min(bisect(s,n-i)+1,n)
    for si in s[:ir]:
        j=i+si
        if j<=n:
            dp[j]=(dp[j]+dp[i])%mod
#    print(i,ir,dp)

print(dp[n])

Submission status: Time Limit Exceeded

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

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

MOD = 998244353

lst = np.zeros((K, 2), np.int64)
for _ in range(K):
  l, r = map(int, input().split())
  lst[_][0]  = l
  lst[_][1] = r
    

'''dp = np.zeros((N*2), int)
dp[0] = 1

for i in range(N):
  a = dp[i] % MOD
  for l, r in lst:
    dp[i+l:i+r+1] += a
  #print(dp)
'''
  
@jit((i8, i8[:]), cache=True)
def main(N_, lst_):
  dp = np.zeros((N_*2), int)
  dp[0] = 1
  for i in range(N_):
    a = dp[i] % MOD
    for l, r in lst_:
      dp[i+l:i+r+1] += a
  return dp[N_ - 1] % MOD


print(main(N, lst))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
T=[0]*(N+1)
p=998244353
for i in range(K):
  a,b=map(int,input().split())
  for j in range(a,b+1):
    T[j]+=1

dp=[0]*N
dp[0]=1
for i in range(1,N):
  dp[i]=sum([x for j,x in enumerate(dp) if i>=j and T[i-j]==1])%p
print(dp[-1]%p)

Submission status: Time Limit Exceeded

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

    s=[]
    for i in range(k):
        li,ri=list(map(int,input().split()))
        for i in range(li,ri+1):
            s.append(i)
elif icase==1:
    n,k=5,2
    s=[1, 3, 4]
elif icase==2:
    n,k=60,3    
    s=[5, 6, 7, 8, 1, 2, 3, 10, 11, 12, 13, 14, 15]

mod=998244353

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

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

print(dp[n])

Submission status: Time Limit Exceeded

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

dp = [0]*(n+1)
dp[0],dp[1] = 0,1
cumsum = [0]*(n+1)
cumsum[1] = 1
for i in range(2,n+1):
  for l,r in sec:
    if i>l:
      dp[i] += cumsum[i-l]-cumsum[max(0,i-r-1)]
  cumsum[i] = dp[i]+cumsum[i-1]
print(dp[n]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

MOD = 998244353

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

dp = np.zeros((N*2), int)
dp[0] = 1

for i in range(N):
  a = dp[i] % MOD
  for l, r in lst:
    dp[i+l:i+r+1] += a
  #print(dp)
   
print(dp[N-1]% MOD)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
mod = 998244353
list_s = []
for _ in range(k):
    l, r = map(int, input().split())
    list_s.append((l, r))
dp = [0] * (n + 1)
sdp = [0] * (n + 1)
dp[1] = 1
sdp[0] = 0
sdp[1] = 1

for i in range(2, n + 1):
    for l, r in list_s:
        dl = max(0, i - r - 1)
        dr = max(0, i - l)
        dp[i] += sdp[dr] - sdp[dl]
        sdp[i] = sdp[i - 1] + dp[i]
print(dp[n] % mod)

Submission status: Time Limit Exceeded

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

LR = [map(int, input().split()) for _ in range(K)]
MOD = 998244353
dic = []
for l, r in LR:
    tmp = [x for x in range(l, r+1)]
    dic += tmp
dic.sort()
dp = [0]*(N+1)
dp[1] = 1
n = len(dic)
cnt = 0
t = []
for i in range(2, N+1):
    tmp = i-1
    while cnt < n:
        if dic[cnt] <= tmp:
            t.append(dic[cnt])
            cnt += 1
        else:
            break
    for s in t:
        dp[i] += dp[i-s]
        dp[i] %= MOD
print(dp[-1])

Submission status: Time Limit Exceeded

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

LR = [map(int, input().split()) for _ in range(K)]
MOD = 998244353
dic = set()
for l, r in LR:
    for i in range(l, r+1):
        dic.add(i)
dic = list(dic)
dic.sort()
dp = [0]*(N+1)
dp[1] = 1

n = len(dic)
cnt = 0
t = []
for i in range(2, N+1):
    tmp = i-1
    while cnt < n:
        if dic[cnt] <= tmp:
            t.append(dic[cnt])
            cnt += 1
        else:
            break
    for s in t:
        dp[i] += dp[i-s]
        dp[i] %= MOD
print(dp[-1])

Submission status: Time Limit Exceeded

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

LR = [map(int, input().split()) for _ in range(K)]
MOD = 998244353
dic = set()
for l, r in LR:
    for i in range(l, r+1):
        dic.add(i)
dic = list(dic)
dp = [0]*(N+1)
dp[1] = 1

for i in range(2, N+1):
    tmp = i-1
    t = [x for x in dic if x <= tmp]
    for s in t:
        dp[i] += dp[i-s]
        dp[i] %= MOD
print(dp[-1])

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 += [i for i in range(L, R+1)]
A = [1]
for n in range(1,N):
    s = sum(A[n - i] for i in S if n - i >= 0) % 998244353
    A.append(s)
print(A[N-1])

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.append([L,R])
A = [1]
for n in range(1,N):
    s = sum(A[n - i] for u in S for i in range(u[0], u[1] + 1) if n - i >= 0) % 998244353
    A.append(s)
print(A[N-1])

Submission status: Time Limit Exceeded

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

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

for i in range(2,N+1):
    for l, r in S: 
        if i >= r + 1:
            dp[i] += dp_sums[i - l] - dp_sums[i - r - 1] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i > l and i < r + 1:
            dp[i] += dp_sums[i - l] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i <= l:
            dp_sums[i] = dp_sums[i-1] + dp[i]
    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.append([L,R])
A = [1]
n = 1
while n <= N - 1:
    for i in S:
        s = sum(A[n - i] for s in S for i in range(s[0], s[1] + 1) if n - i >= 0) % 998244353
        A.append(s)
        s = 0
        n += 1
print(A[N-1])

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.append([L,R])
A = [1]
n = 1
while n <= N - 1:
    for i in S:
        s = sum(A[n - i] for s in S for i in range(s[0], s[1] + 1) if n - i >= 0) % 998244353
        A += [s]
        s = 0
        n += 1
print(A[N-1])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
L = [0] * K
R = [0] * K
S = set()
for k in range(K):
    L[k],R[k] = map(int,input().split())
for k in range(K):
    for n in range(L[k], R[k] + 1):
        S.add(n)
dp = [0] * (N+1)
dp[1] = 1
S = sorted(S)
for i in range(1,N+1):
    for s in S:
        if i-s <= 0:
            break
        dp[i] += dp[i-s]
    dp[i] %= 998244353
print(dp[N])

Submission status: Time Limit Exceeded

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

dp = [0] * (n+1)
sdp = [0] * (n+1)
dp[1] = 1
for i in range(2,n+1):
    for s in list_s:
        if s < i:
            dp[i] += dp[i-s]
print(dp[n] % mod)

Submission status: Time Limit Exceeded

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

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

for i in range(2,N+1):
    for l, r in S: 
        if i >= r + 1:
            dp[i] += dp_sums[i - l] - dp_sums[i - r - 1] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i > l and i < r + 1:
            dp[i] += dp_sums[i - l] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i <= l:
            dp_sums[i] = dp_sums[i-1] + dp[i]
        dp[i] %= 998244353
print(dp[N])

Submission status: Time Limit Exceeded

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

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

for i in range(2,N+1):
    for l, r in S: 
        if i >= r + 1:
            dp[i] += dp_sums[i - l] - dp_sums[i - r - 1] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i > l and i < r + 1:
            dp[i] += dp_sums[i - l] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i <= l:
            dp_sums[i] = dp_sums[i-1] + dp[i]
        while dp[i] >= 998244353:
            dp[i] -= 998244353
while dp[N] >= 998244353:
    dp[N] -= 998244353 
print(dp[N])

Submission status: Time Limit Exceeded

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

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

for i in range(2,N+1):
    for s in S: 
        if i >= s[1] + 1:
            dp[i] += dp_sums[i - s[0]] - dp_sums[i - s[1] - 1] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i > s[0] and i < s[1] + 1:
            dp[i] += dp_sums[i - s[0]] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i <= s[0]:
            dp_sums[i] = dp_sums[i-1] + dp[i]
        while dp[i] >= 998244353:
            dp[i] -= 998244353
while dp[N] >= 998244353:
    dp[N] -= 998244353 
print(dp[N])

Submission status: Time Limit Exceeded

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

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

for i in range(1,N+1):
    for s in S: 
        if i >= s[1] + 1:
            dp[i] += dp_sums[i - s[0]] - dp_sums[i - s[1] - 1] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i > s[0] and i < s[1] + 1:
            dp[i] += dp_sums[i - s[0]] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i <= s[0]:
            dp_sums[i] = dp_sums[i-1] + dp[i]
        while dp[i] >= 998244353:
            dp[i] -= 998244353
while dp[N] >= 998244353:
    dp[N] -= 998244353 
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
#bitでタコ殴りにする
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_

m=998244353    
N,K=map(int,input().split())
bit = Bit(N)
bit.add(1,1)#初期値　はじめは１
period = []
for _ in range(K):#動ける区間の記憶
    l,r=map(int,input().split())
    period.append((l,r))
for i in range(2,N+1):#2からNまで見ていく。もらうDP
    for l,r in period:
        rx = max(0,i-l)
        lx = max(0,i-r-1)
        if rx==0:
            tmp_r = 0
        else:
            tmp_r = bit.sum(rx)
        if lx == 0:
            tmp_l = 0
        else:
            tmp_l = bit.sum(lx)
        bit.add(i,(tmp_r-tmp_l)%m)
ans = (bit.sum(N)-bit.sum(N-1))%m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#bitでタコ殴りにする
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_

m=998244353    
N,K=map(int,input().split())
bit = Bit(N)
bit.add(1,1)#初期値　はじめは１
period = []
for _ in range(K):#動ける区間の記憶
    l,r=map(int,input().split())
    period.append((l,r))
for i in range(2,N+1):#2からNまで見ていく。もらうDP
    for l,r in period:
        rx = max(0,i-l)
        lx = max(0,i-r-1)
        if rx==0:
            tmp_r = 0
        else:
            tmp_r = bit.sum(rx)
        if lx == 0:
            tmp_l = 0
        else:
            tmp_l = bit.sum(lx)
        bit.add(i,tmp_r)
        bit.add(i,-tmp_l)
ans = (bit.sum(N)-bit.sum(N-1))%m
print(ans)

Submission status: Time Limit Exceeded

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

a = [0 for i in range(N+1)]
a[1] = 1
b = [0 for i in range(N+1)]
b[1] = 1
for i in range(2,N+1):
    for j in range(K):
        if l[j][0] < i:
            a[i] += b[i-l[j][0]]-b[max(0,i-l[j][1]-1)]
        else:
            break
    b[i] = b[i-1]+a[i]
mod = 998244353
print(a[N]%mod)

Submission status: Time Limit Exceeded

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


a = [0 for i in range(N+1)]
a[1] = 1
b = [0 for i in range(N+1)]
b[1] = 1
for i in range(2,N+1):
    for j in range(K):
        if l[j][0] < i:
            a[i] += b[i-l[j][0]]-b[max(0,i-l[j][1]-1)]
    b[i] = b[i-1]+a[i]
mod = 998244353
print(a[N]%mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

mod = 998244353
n, k = map(int, input().split())
left = []
right = []
for _ in range(k):
  l, r = map(int, input().split())
  left.append(l)
  right.append(r)
dp = np.zeros(n+1, dtype=np.int)
dp[1] = 1
for i in range(2, n+1):
  for j in range(k):
    dp[i] += dp[max(0, i - left[j])] - dp[max(0, i - right[j] - 1)]
    dp[i] %= mod
  dp[i] = (dp[i-1] + dp[i]) % mod
print((dp[n] - dp[n-1]) % mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

mod = 998244353
n, k = map(int, input().split())
left = []
right = []
for _ in range(k):
  l, r = map(int, input().split())
  left.append(l)
  right.append(r)
dp = np.zeros(n, dtype=np.int)
dp[0] = 1
for i in range(n-1):
  for j in range(k):
    dp[i + left[j] : i + right[j] + 1] += dp[i]
    dp[i + left[j] : i + right[j] + 1] %= mod
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os
    import re
    with open(__file__) as f:
        source = f.read().split('###''nbacl')
    for s in source[1:]:
        s = re.sub("'''.*", '', s)
        sp = s.split(maxsplit=1)
        if os.path.dirname(sp[0]):
            os.makedirs(os.path.dirname(sp[0]), exist_ok=True)
        with open(sp[0], 'w') as f:
            f.write(sp[1])

    import nbmodule
    nbmodule.cc.compile()
    exit(0)

from nbmodule import solve
import numpy as np
i8 = np.int64
i4 = np.int32


def main():
    f = open(0)
    N, K = [int(x) for x in f.readline().split()]
    LR = np.fromstring(f.read(), i8, sep=' ').reshape((-1, 2)).T.copy()
    L = LR[0]
    R = LR[1]
    arg = np.argsort(L)
    left = L[arg]
    right = R[arg]
    w = right - left + 1
    ans = solve(N, left, w)
    print(ans)


if __name__ == '__main__':
    main()

'''
###nbacl nbmodule.py
import numpy as np
from numba import njit
from numba.types import i8, i4
from numba.pycc import CC
ni4 = np.int32
ni8 = np.int64
cc = CC('nbmodule')

MOD = 998244353


@cc.export('solve', (i8, i8[:], i8[:]))
def solve(N, left, w):
    l0 = w.max()
    dp_len = N + l0
    dp_prev = np.zeros(dp_len, ni8)
    dp_prev[l0] = 1
    dp = np.zeros(dp_len, ni8)
    left_min = left[0]
    ret = 0
    while l0 + left_min < dp_len:
        for k in range(left.shape[0]):
            pre = 0
            for i in range(l0 + left[k], dp_len):
                cur = pre + dp_prev[i - left[k]] - dp_prev[i - left[k] - w[k]]
                dp[i] += cur
                pre = cur
        ret += dp[-1]
        dp_prev, dp = dp, dp_prev
        dp_prev %= MOD
        dp.fill(0)
        l0 += left_min

    return ret % MOD

if __name__ == '__main__':
    cc.compile()
'''

Submission status: Time Limit Exceeded

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

F = [0]*(n+2) # [l,r+1): 1<=[l]<[r+1]<=n+1
for _ in range(k):
    l, r = map(int, input().split())
    F[l] += 1
    F[r+1] += -1

# print(F)
S = []
for i in range(n+1): # i:[0, n]
    if F[i] > 0: S.append(i)
    F[i+1] += F[i]

# print(F)
# print(n,k)
# print(S)

MOD = 998244353
dp = [0]*(n+1)  # [0,n]
dp[1] = 1

for i in range(1, n+1): # i:[1,n]
    for s in S:
        if i + s <= n:
            # print('s {} i {} n {}'.format(s,i,n))
            dp[i + s] += dp[i]
            dp[i + s] %= MOD

# print(dp)

print((dp[n] + MOD) % MOD)

Submission status: Time Limit Exceeded

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

F = [0]*(n+2) # [l,r+1): 1<=[l]<[r+1]<=n+1
for _ in range(k):
    l, r = map(int, input().split())
    F[l] += 1
    F[r+1] += -1

# print(F)
S = []
for i in range(n+1): # i:[0, n]
    if F[i] > 0: S.append(i)
    F[i+1] += F[i]

# print(F)
# print(n,k)
# print(S)

MOD = 998244353
dp = [0]*(n+1)  # [0,n]
dp[1] = 1

for i in range(1, n+1): # i:[1,n]
    for s in S:
        if i + s <= n:
            # print('s {} i {} n {}'.format(s,i,n))
            dp[i + s] += dp[i]

# print(dp)

print((dp[n] + MOD) % MOD)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
DP = [0]*(N+1)
DPsum=[0]*(N+1)
DP[1]=1
DPsum[1]=1
lr = []
m=998244353
for _ in range(K):
    l,r = map(int,input().split())
    lr.append([l,r])

for i in range(2,N+1):
    for l,r in lr:
        lx = i - r - 1
        rx = i - l
        lx = max(0,lx)
        rx = max(0,rx)
        DP[i]+= DPsum[rx]-DPsum[lx]
    DPsum[i]=DPsum[i-1]+DP[i]
print(DP[N]%m)

Submission status: Time Limit Exceeded

Solution code:
# 179 D

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

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

memo = [0 for _ in range(n+max(s))]
  
for i in range(1, n):
  if i in s:
    memo[i] += 1
  for e in s:
    memo[i+e] += memo[i]

    

print(memo[n-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,k = map(int,input().split())
lr = []
for _ in range(k):
    a,b = map(int,input().split())
    lr.append(list(range(a,b+1)))
lr = set(itertools.chain.from_iterable(lr))
count = [0] * (n + 1)
for a in lr:
    count[a] = 1
for i in range(n):
    for j in lr:
        if count[i-j] > 0 and i-j > 0:
            count[i] += count[i-j]
print(count[-2]%998244353)

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:
import itertools
n,k = map(int,input().split())
lr = []
for _ in range(k):
    a,b = map(int,input().split())
    lr.append(list(range(a,b+1)))
lr = list(itertools.chain.from_iterable(lr))
count = [0] * (n + 1)
for a in lr:
    count[a] = 1
for i in range(n):
    for j in lr:
        if count[i-j] > 0 and i-j > 0:
            count[i] += count[i-j]
print(count[-2] % 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))

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

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 |= set(list(range(l, r+1)))

mod = 998244353
dp = [0] * (n+1)
dp[1] = 1
s = sorted(list(s))
for i in range(1, n):
    dp[i] %= mod
    for add in s:
        if i+add <= n:
            dp[i+add] += dp[i]
print(dp[n] % mod)

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 |= set(list(range(l, r+1)))

mod = 998244353
dp = [0] * (n+1)
dp[1] = 1
s = sorted(list(s))
for i in range(1, n):
    for add in s:
        if i+add <= n:
            dp[i+add] += dp[i]
            dp[i+add] %= mod
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
# 179 D

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

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

memo = {}

for i in range(1, n+max(s)+1):
  memo[i] = 0
  
for i in range(1, n):
  if i in s:
    memo[i] += 1
  for e in s:
    memo[i+e] += memo[i]

    

print(memo[n-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
K, N = map(int, input().split())
num_list = []
for i in range(N):
    L, R = map(int, input().split())
    num_list += list(range(L, R+1))
    
num_set = set(sorted(num_list))
counting = [0 for i in range(K+1)]
counting[1]=1
for i in range(2, K+1):
    for n in num_set:
        if i-n > 0:
            counting[i] += counting[i-n]
print(counting[K]%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):
  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] % mod


print(DP[N-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
# 179 D

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

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

memo = {}

def dest(n):
  return sum([memo[n-i] for i in s if n-i in memo])

for i in range(1, n):
  memo[i] = dest(i) 
  if i in s:
    memo[i] += 1
    

print(memo[n-1]% 998244353)

Submission status: Time Limit Exceeded

Solution code:
# 179 D

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

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

memo = {}

def dest(n):
  return sum([memo[n-i] for i in s if n-i in memo])

for i in range(1, n):
  memo[i] = dest(i) % 998244353
  if i in s:
    memo[i] += 1
    

print(memo[n-1])

Submission status: Time Limit Exceeded

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

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

print(dp[N] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
dp=[0 for i in range(n+1)]
dp[1]=1
accum=[0 for i in range(n+1)]
accum[1]=1
s=[]
for i in range(k):
    x,y=map(int,input().split())
    s.append([x,y])
for i in range(2,n+1):
    for j in s:
        l,r=j
        tmpl=i-r
        tmpr=i-l
        if(tmpl<1):
            tmpl=1
        if(tmpr>=i):
            tmpr=i-1
        if(tmpr<0):
            continue
        dp[i]+=accum[tmpr]-accum[tmpl-1]
    accum[i]=dp[i]+accum[i-1]
print(dp[n]%998244353)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
dp=[0 for i in range(n+1)]
dp[1]=1
accum=[0 for i in range(n+1)]
accum[1]=1
s=[]
for i in range(k):
    x,y=map(int,input().split())
    s.append([x,y])
for i in range(2,n+1):
    for j in s:
        l,r=j
        tmpl=i-r
        tmpr=i-l
        if(tmpl<1):
            tmpl=1
        if(tmpr>=i):
            tmpr=i-1
        dp[i]+=accum[tmpr]-accum[tmpl-1]
    accum[i]=dp[i]+accum[i-1]
print(dp[n]%998244353)

Submission status: Time Limit Exceeded

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

l = []
for i in range(K):
    for j in range(LR[i][1] - LR[i][0] + 1):
        l.append(LR[i][0] + j)

dp = [0] * N
dp[0] = 1
for i in range(N):
    for j in range(len(l)):
        if i + l[j] < N:
            dp[i + l[j]] += dp[i]

print(dp[N - 1] % 998244353)

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)
from numba import njit,i8


@njit(i8(i8,i8,i8[:,:],i8,i8[:],i8,i8,i8,i8))
def give_cnt(N,K,LR,mod,dp,L,R,l,r):
    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
    return dp[-1]


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

    mod = 998244353

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

    res = give_cnt(N,K,LR,mod,dp,0,0,0,0)

    # print(dp)
    print(res)



main()

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]
        if i+d == N and dp[i+d] >= base:
          dp[i+d] %= base
      else:
        break
  print(dp[-1]%base)

if __name__ == "__main__":
  resolve()

Submission status: Time Limit Exceeded

Solution code:
N,K = [int(i) for i in input().split()]
mod = 998244353
LR = []
S = []
dp = [0]*(N+1)
dps = [0]*(N+1)
dps[1] = 1
for i in range(K):
  LR.append([int(i) for i in input().split()])
rM = 0
for i in range(N):
  for lr in LR:
    if lr[0] <= i and i <= lr[1]:
      S.append(i)
  rM = max(rM, lr[1])
for i in range(1,N):
  if i in S:
    dp[i] = 1
  for l,r in LR:
    l,r = i - r,i - l
    if r < 1:
      continue
    l = max(0,l)
    dp[i] += dps[r] - dps [l-1]
    dp[i] %= mod
    dps[i] += dps[r] - dps[l]
    
  dps[i] = dps[i-1] + dp[i]
print(dp[-2])