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:
from itertools import accumulate
n, k = map(int, input().split())
l = [0]*(n+10)
imos = [0]*(n+10)
mod = 998244353

for i in range(k):
    a, b = map(int, input().split())
    l[a] += 1
    l[b+1] -= 1
imos = list(accumulate(l))

s = []
for i in range(len(imos)):
    if i <= n and imos[i] == 1:
        s.append(i)
s.sort()
dp = [0]*(n+2)
dp[1] = 1
imos[1] = 1

for i in range(1,n+1):
    for ss in s:
        if i+ss>n:continue
        if imos[i] == 1:
            dp[i+ss] += dp[i]
            imos[i+ss] = 1
            dp[i+ss] %= mod

print(dp[n]%mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np 

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

path = np.zeros(n).astype('int')
path[0] = 1

for i in range(n-1):
    if path[i] == 0:
        continue
    for j in s:
        if i+j > n-1:
            break
        path[i+j] += path[i]
print(path[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
L = list()
R = list()
for _ in range(K):
    a,b = map(int, input().split())
    for _1 in range(_):
        x,y = L[_1],R[_1]
        if x <= a <= y or x <= b <= y :
            L[_1] = min(a,x)
            R[_1] = max(b,y)
            break
    else:
        L.append(a)
        R.append(b)
sep = len(L)


MOD = 998244353
dp = [0]*(N+2)
for l, r in zip(L, R):
    dp[min(N + 1, 1 + l)] += 1
    dp[min(N + 1, 1 + r + 1)] -= 1
for i in range(2,N+1):
    number = dp[i-1] + dp[i]
    if number > MOD:
        number -= MOD
    dp[i] = number
    for l, r in zip(L,R):
        dp[min(N + 1, i + l)] += dp[i]
        dp[min(N + 1, i + r +1)] -= dp[i]
print(dp[N]%MOD)

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):
        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 = np.array(steps)

print(main(N, steps))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

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

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

lr.sort()
lr = np.array(lr)

dp = np.zeros(n + n, dtype=np.int64)
dp[0] = 1
dp2 = dp.copy()


@njit(cache=True)
def solve(n, lr, dp, dp2):
    for i in range(n):
        idx = i + lr
        dp2[idx] += dp[i]
        dp2 %= MOD
        dp = dp2
    return dp[n - 1]


print(solve(n, lr, dp, dp2))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

lr.sort()
lr = np.array(lr)

dp = np.zeros(n + n, dtype=np.int64)
dp[0] = 1
dp2 = dp.copy()

for i in range(n):
    idx = i + lr
    dp2[idx] += dp[i]
    dp2 %= MOD
    dp = dp2

print(dp[n - 1])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
LR = [list(map(int,input().split())) for i in range(K)]
LR.sort()
mod = 998244353
ma = [0] * N
ma[0] = 1
for i in range(N):
    if i >1:
        ma[i] += ma[i-1]
    p = ma[i]
    if p != 0:
        for l,r in LR:
            if i+l <N:
                ma[i+l] += p
            else:
                break
            if i+r+1<N:
                ma[i+r+1] -= p
print(ma[N-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
from itertools import *
n, k = map(int, input().split())
mod = 998244353
strides = []
for i in range(k):
  l, r = map(int, input().split())
  for t in range(l, r + 1):
    strides.append(t)
strides.sort()

d = [0] * (n + 1)  # マスに対応
d[0] = 1
for i in range(1, n):
  for stride in strides:
    if i >= stride:
      d[i] += d[i - stride]
  d[i] %= mod
print(d[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)]
mod = 998244353

s = []
for l, r in lr:
    s += [i for i in range(l, r + 1)]

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

Submission status: Time Limit Exceeded

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

def main():
    n, k = map(int, input().split())
    lrs = []
    for i in range(k):
        l, r = input().split()
        lrs.append([int(l), int(r)])
    stdOut = solve(n, k, lrs)
    print(stdOut)


"""
方針
和集合の要素の和がn-1と等しくなる組み合わせを考える
和集合の要素の個数の最大はn-1なので、単純に総当たりで行うとO(n^n)

"""

mod = 998244353


def solve(n, k, lrs):
    # 和集合Sの作成
    S = []
    for i in range(k):
        lr = lrs[i]
        l = lr[0]
        r = lr[1]
        for j in range(r - l + 1):
            S.append(l + j)
    S.sort()

    # 例(998244353, [1, 3, 4], 4, 3) => 4 (1111,13,31,4)
    # この世に出ている部分和数え上げ問題は重複組み合わせになるため、
    # 部分和数え上げ問題はそのまま使うことはできない
    N = len(S)
    dp = [0 for i in range(n * 2)]
    dp[0] = 1
    # 配るDP
    for i in range(n):
        for si in S:
            dp[i + si] += dp[i]
        dp[i] = dp[i] % mod
    return dp[n - 1]
    # ただしこれではTLEになるので残念ならACにはなりませんでした


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
li = []
for i in range(K):
  l, r = map(int, input().split())
  for j in range(l, r+1):
    li.append(j)
li.sort()
    
ans = [0] * (N+1)
ans[1] = 1
for i in range(1, N):
  if ans[i] > 0:
    for n in li:
      if i+n <= N:
        ans[i+n] += ans[i]
        ans[i+n] %= 998244353
      else:
        break
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import numpy as np
n, k = map(int, input().split())
s_list = []
a_list = np.zeros((n + 1), dtype=int)
a_list[1] = 1
for i in range(k):
    l, r = map(int, input().split())
    s_list.append([l, r + 1])

for i in range(1, n):
    if a_list[i] > 998244353:
        a_list[i] %= 998244353
    if a_list[i] == 0:
        continue
    for l, r in s_list:
        if i + l > n:
            continue
        if i + r > n + 1:
            a_list[(i+l):(n+1)] += a_list[i]
        else:
            a_list[(i+l):(i+r)] += a_list[i]
print(a_list[n] % 998244353)

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):
        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 = np.array(steps)

print(main(N, steps))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K = map(int, input().split())

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

step = np.zeros(N+1)
step[1] = 1

for j in range(1,N):
    for l,r in S:
        if j + l > N:
            continue
        r_ = min(j+r+1,N+1)
        step[j+l: r_] += step[j]
        step[j+l:r_] %= 998244353
    
print(int(step[N]))

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')

m = 998244353
n, k = (int(x) for x in input().split())
d = set()
for _ in xrange(k):
    l,r = (int(x) for x in input().split())
    d = d.union(range(l, r+1))
d = sorted(d)
dp = [0 for _ in xrange(n)]
dp[0] = 1
for i in xrange(n):
    for di in d:
        try:
            dp[i+di] += dp[i]
        except:
            break
        if (dp[i+di] >= m):
            dp[i+di] = dp[i+di] %m  
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
LR = [list(map(int,input().split())) for i in range(K)]
mod = 998244353
ma = [0] * N
ma[0] = 1
for i in range(N):
    if i >1:
        ma[i] += ma[i-1]
    p = ma[i]
    if p != 0:
        for l,r in LR:
            if i+l <N:
                ma[i+l] += p
            if i+r+1<N:
                ma[i+r+1] -= p
print(ma[N-1]%mod)

Submission status: Time Limit Exceeded

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

dp = [0]*(N+1)
dp_sum = [0]*(N+1)
dp[1] = dp_sum[1] = 1
for i in range(2,N+1):
    for l,r in move:
        if 0<i-l:
            dp[i] += dp_sum[i-l]
            if 0<i-r-1:
                dp[i] -= dp_sum[i-r-1]
    dp_sum[i] = dp_sum[i-1] + dp[i]
            
print(dp[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K = map(int, input().split())
L = list()
R = list()
for _ in range(K):
    a,b = map(int, input().split())
    for _1 in range(_):
        x,y = L[_1],R[_1]
        if x <= a <= y or x <= b <= y :
            L[_1] = min(a,x)
            R[_1] = max(b,y)
            break
    else:
        L.append(a)
        R.append(b)
sep = len(L)


MOD = 998244353
dp = np.zeros(N+10,dtype=np.int64)
for l, r in zip(L, R):
    dp[min(N + 1, 1 + l)] += 1
    dp[min(N + 1, 1 + r + 1)] -= 1
for i in range(2,N+1):
    dp[i] = dp[i-1] + dp[i]
    kubaru = dp[i] % MOD
    for l, r in zip(L,R):
        dp[min(N + 1, i + l)] += kubaru
        dp[min(N + 1, i + r +1)] -= kubaru
print(dp[N]%MOD)

Submission status: Time Limit Exceeded

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

def solve():
    MOD = 998244353

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def setInit(As):
        for iB, A in enumerate(As, 1):
            data[iB] = A
        for iB in range(1, numPow2):
            i = iB + (iB & -iB)
            data[i] += data[iB]
    def addValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans
    def getRangeSum(iFr, iTo):
        return getSum(iTo) - getSum(iFr-1)


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

    data, numPow2 = makeBIT(N)

    addValue(0, 1)

    for i in range(1, N):
        v = 0
        for L, R in LRs:
            x, y = i-R, i-L
            if y < 0:
                continue
            if x < 0:
                x = 0
            v += getRangeSum(x, y) % MOD
            v %= MOD
        addValue(i, v)

    ans = getRangeSum(N-1, N-1) % MOD
    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
LR = [list(map(int,input().split())) for i in range(K)]
LR.sort()
mod = 998244353
ma = [0] * N
ma[0] = 1
for i in range(N):
    if i >1:
        ma[i] += ma[i-1]
    p = ma[i]
    if p != 0:
        for l,r in LR:
            if i+l <N:
                ma[i+l] += p
            if i+r+1<N:
                ma[i+r+1] -= p
print(ma[N-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

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

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


for i in range(K):
    a, b = map(int, input().split())
    for j in range(a-1, b):
        dp[j+1] = 1
        q.append(j+1)

q = sorted(q)

for i in range(1, N):
    for j in q:
        if i - j < 1:
            break
        dp[i] = (dp[i] + dp[i-j]) % 998244353
    # if i > 6:
    #     exit()

print(dp[N-1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
n,k = map(int,input().split())
K = [list(map(int,input().split())) for i in range(k)]

dp = [0]*(n+1)
dp[0] = 1
dp2 = [0]*(n+1)
for i in range(n):
    dp2[i] = (dp2[i]+dp2[i-1])%mod
    dp[i] = (dp[i]+dp2[i])%mod
    for l,r in K:
        dp2[min(i+l,n)] = (dp2[min(i+l,n)]+dp[i])%mod
        dp2[min(i+r+1,n)] = (dp2[min(i+r+1,n)]-dp[i])%mod
print(dp[n-1]%mod)

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)))
S= set(s)

mod = 998244353

step = [0] * (n+1)

step[0]=1
for i in range(n):
    for s in S:
        if i+s<=n:
            step[i+s]=(step[i]+step[i+s])%mod
        else:
            break
            # print(step)
# print(step)
print(step[n-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

def main():
    n, k = map(int, input().split())
    s = []
    for _ in range(k):
        l, r = map(int, input().split())
        s.extend(list(range(l, r+1)))
    
    dp = [0] * (2*n+1)
    dp[0] = 1
    
    for i in range(0, n):
        for j in s:
            dp[i+j] += dp[i]
    
    print(dp[n-1] % 998244353)
    
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K = map(int, input().split())

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

step = np.zeros(2*N+1)
step[1] = 1

for j in range(1,N):
    for l,r in S:
        step[j+l:j+r+1] += step[j]
        step[j+l:j+r+1] %= 998244353
    
print(int(step[N]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict
 
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()
 
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()
 
def main():
    N, K = NMI()
    A = list(sorted([NLI() for _ in range(K)]))
    
    ls = [0 for _ in range(N+A[-1][1]+10)]
    ls[0] = 1
 
    for n in range(N):
        for k in range(K):
            for x in range(A[k][0],A[k][1]+1):
                ls[n+x] += ls[n]%MOD2
    print(ls[N-1]%MOD2)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

D = [1]
M = 5000
memo = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      ll = i - min(i, r)
      rr = i - l + 1
      LL = (ll + M - 1) // M
      RR = rr // M
      if RR > LL:
        count += sum(D[ll:LL*M]) + sum(memo[LL:RR]) + sum(D[RR*M:rr])
      else:
        count += sum(D[ll:rr])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
print(D[-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N,K = map(int,input().split())
N-=1
mvs = set()
mods = 998244353
dps = defaultdict(int)
 
for _ in range(K):
  a,b = map(int,input().split())
  for k in range(a,b+1):
    mvs.add(k)
 
for k in mvs:
  if k <= N:
    dps[k]+=1
 
for i in range(2,N+1):
  for k in mvs:
    if i-k >0:
      dps[i] += dps[i-k] % mods 
print(dps[N]%mods)

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)))
S= set(s)

mod = 998244353
step = [0] * (n+1)

step[0]=1
for i in range(0,n+1):
    for s in S:
        if i+s<=n:
            step[i+s]=(step[i]+step[i+s])%mod

print(step[n-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 = [1]
M = 1000
memo = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      ll = i - min(i, r)
      rr = i - l + 1
      LL = (ll + M - 1) // M
      RR = rr // M
      if RR > LL:
        count += sum(D[ll:LL*M]) + sum(memo[LL:RR]) + sum(D[RR*M:rr])
      else:
        count += sum(D[ll:rr])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
print(D[-1])

Submission status: Time Limit Exceeded

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

D = [1]
M = 10
memo = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      ll = i - min(i, r)
      rr = i - l + 1
      LL = (ll + M - 1) // M
      RR = rr // M
      if RR > LL:
        count += sum(D[ll:LL*M]) + sum(memo[LL:RR]) + sum(D[RR*M:rr])
      else:
        count += sum(D[ll:rr])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
print(D[-1])

Submission status: Time Limit Exceeded

Solution code:
def getsum(BITTree, i):
    s = 0
    i = i + 1
    while i > 0:
        s += BITTree[i]
        i -= i & (-i)
    return s
def updatebit(BITTree, n, i, v):
    i += 1
    while i <= n:
        BITTree[i] += v
        i += i & (-i)
def construct(arr, n):
    BITTree = [0] * (n + 1)
    for i in range(n):
        updatebit(BITTree, n, i, arr[i])
    return BITTree
n,k=map(int,input().split())
c=[]
a=[0]*(n+1)
a[1]=1
BITTree = construct(a,len(a))
mod=998244353
for i in range(k):
    x,y=map(int,input().split())
    c.append([x,y])
for i in range(2,n+1):
    for j in range(len(c)):
        p,q=c[j][0],c[j][1]
        if i-q>0:
            l,r=i-p,i-q
            z=(getsum(BITTree,l)-getsum(BITTree,r-1))%mod
            a[i]+=z
            updatebit(BITTree, len(a), i,z)
        else:
            q=i-1
            if i-q>0 and i-p>0:
                l, r = i - p, i - q
                z = (getsum(BITTree, l) - getsum(BITTree, r - 1))%mod
                a[i]+=z
                updatebit(BITTree, len(a), i, z)
print(a[n]%mod)

Submission status: Time Limit Exceeded

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

for i in range(k):
    l,r = list(map(int,input().split()))
    for i in range(l,r+1):
        s.add(i)
lis = list(s)
lis = sorted(lis)
dic = dict()
dic[1] = 1

for i in range(1,n+1):
    if i in dic.keys():
        #for j in s:
        for j in range(0,len(lis)):#
            #if i + j in dic.keys():
            if i + lis[j] in dic.keys():
                #dic[i+j] += dic[i]
                dic[i+lis[j]] += dic[i]
            else:
                #dic[i+j] = dic[i]
                dic[i+lis[j]] = dic[i]
            if i + lis[j] > n:#
                break#

if n in dic.keys():
    print(dic[n] % 998244353)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    L = [[] for _ in range(K)]
    for t in range(K):
        l, r = map(int, input().split())
        for j in range(l, r + 1):
            L[t].append(j)

    lc = [0] * K
    mod = 998244353

    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(1,N+1):

        for k in range(K):
            CL =L[k]
            if len(CL)==1:
                lc[k]=dp[i-CL[0]]
            else:
                if CL[-1] > i:
                    lc[k] = lc[k] +dp[i-L[k][0]]
                else:
                    lc[k] =( lc[k] + dp[i - L[k][0]] - dp[i - L[k][-1]-1] )%mod
            dp[i] += lc[k]



    print(dp[N - 1]%mod)


if __name__ == "__main__":
    main()

# \n

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit
     
MOD = 998244353
N, K = list(map(int, input().split()))
     
dp = np.zeros(N+1, dtype=np.int64)
mv = np.zeros(N+1, dtype=np.int64)
for i in range(K):
    l, r = list(map(int, input().split()))
    for j in range(l, r+1):
        mv[j] = 1

@jit(nopython=True)
def shift_and_add(dp, mv, i):
    for i in range(1, N+1):
        dp += np.concatenate((np.zeros(i+1, dtype=np.int64), mv[1:N-i+1]*dp[i]))
        dp %= MOD
            
dp[1] = 1
shift_and_add(dp, mv, i)
     
print(dp[N])

Submission status: Time Limit Exceeded

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

for i in range(k):
    l,r = list(map(int,input().split()))
    for i in range(l,r+1):
        s.add(i)
lis = list(s)
lis = sorted(lis)
dic = dict()
dic[1] = 1

for i in range(1,n+1):
    if i in dic.keys():
        #for j in s:
        for j in range(0,len(lis)):#
            #if i + j in dic.keys():
            if i + lis[j] in dic.keys():
                #dic[i+j] += dic[i]
                dic[i+lis[j]] += dic[i]
            else:
                #dic[i+j] = dic[i]
                dic[i+lis[j]] = dic[i]
            if i + j > n:#
                break#

if n in dic.keys():
    print(dic[n] % 998244353)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    L = [[] for _ in range(K)]
    for t in range(K):
        l, r = map(int, input().split())
        for j in range(l, r + 1):
            L[t].append(j)

    lc = [0] * K
    mod = 998244353

    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(1,N+1):

        for k in range(K):
            CL =L[k]
            if len(CL)==1:
                lc[k]=dp[i-CL[0]]
            else:
                if CL[-1] > i:
                    lc[k] = sum(dp[:max(0,1+ i-CL[0])]) %mod
                else:
                    lc[k] =( lc[k] + dp[i - L[k][0]] - dp[i - L[k][-1]-1] )%mod
            dp[i] += lc[k]



    print(dp[N - 1]%mod)


if __name__ == "__main__":
    main()

# \n

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit
     
MOD = 998244353
N, K = list(map(int, input().split()))
     
dp = np.zeros(N+1, dtype=np.int64)
mv = np.zeros(N+1, dtype=np.int64)
for i in range(K):
    l, r = list(map(int, input().split()))
    for j in range(l, r+1):
        mv[j] = 1

@jit
def shift_and_add(dp, mv, i):
    for i in range(1, N+1):
        dp += np.concatenate((np.zeros(i+1, dtype=np.int64), mv[1:N-i+1]*dp[i]))
        dp %= MOD
            
dp[1] = 1
shift_and_add(dp, mv, i)
     
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)


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

kukan = []
for i in range(K):
    a,b=input().split()
    kukan.append((int(a), int(b)))

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

# 計N-1回の移動
# 集合Sから重複有りで数を選び，その和がN-1となればよい

i = 1
ans = 0

while True:
    h = itertools.product(S, repeat=i)
    flag = 0
    length = 0
    for v in h:
        length += 1
        s = sum(v)
        if s == N-1:
            ans += 1
        elif s > N-1:
            flag += 1
    if flag == length:
        break

    i += 1

print(ans%998244353)

Submission status: Time Limit Exceeded

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

s = []
for i in range(k):
    l,r = map(int,input().split())
    for i in range(l,r+1):
        s.append(i)
s.sort()
# print(s)
dp = [0 for i in range(n+1)]
dp[1] = 1
for i in range(2,n+1):
    for j in s:
        if i-j >= 1:
            dp[i] += dp[i-j]
    # print(dp)
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)]
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]
      dp[i] %= m
 
print(dp[n-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    move_set = set([])

    for i in range(k):
        a, b = map(int, input().split())
        for j in range(a, b + 1):
            move_set.add(j)
    sorted_set = sorted(move_set)
    # print(sorted_set)
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n+1):
        for num in sorted_set:
            if num + 1 > i:
                break
            else:
                dp[i] += dp[i - num]
    print(dp[-1] % 998244353)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
mod = 998244353
ansList = [0] * (n + 1)
numList = []
for x in range(k):
    l, r = map(int, input().split())
    for id in range(l, r+1):
        numList.append(id)
numList.sort()

ansList[1] += 1
for id in range(1,n+1):
    for x in numList:
        if id + x > n: break 
        ansList[id + x] += ansList[id]
print(ansList[n] % mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    move_set = set([])

    for i in range(k):
        a, b = map(int, input().split())
        for j in range(a, b + 1):
            move_set.add(j)
    sorted_set = sorted(move_set)
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n+1):
        for num in sorted_set:
            if num + 1 > i:
                pass
                # break
            else:
                dp[i] += dp[i - num]
    print(dp[-1] % 998244353)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k = input().split()
goal = int(n)
loup = int(k)
total = set()
dp = [0] * (goal + 1)
dp[0] = 1



#集合の作成
for k in range(loup):
	a,b = map(int, input().split())
	l = set(range(a,b+1))
	total = total | l

#main
for i in range(1,goal+ 1):
	for n in range(1,max(total) + 1):
		if n not in total:
			continue
        
		if i-n >= 0:
			dp[i] = dp[i] + dp[i-n]

print(dp[goal - 1] % 998244353)

Submission status: Time Limit Exceeded

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

arr={0}
for i in range(K):
    a,b=map(int,input().split())
    arr|=set([j for j in range(a,b+1)])

arr.discard(0)


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

ans=0
for i in range(N):
    if dp[i]!=0:
        for j in arr:
            if i+j<=N-1:
                dp[i+j]+=dp[i]
        
    
print(dp[-1]%998244353)

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:
#!/usr/bin/env python3
import sys
import numpy as np

input = sys.stdin.readline
mod = 998244353


def ST():
    return input().rstrip()


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


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


def LI():
    return list(MI())


N, K = MI()

steps = set()
for _ in range(K):
    l, r = MI()
    steps |= set(range(l, r + 1))

dp = np.zeros(N)
dp[0] = 1

for i in range(N):
    for s in steps:
        tmp = i - s
        if tmp >= 0:
            dp[i] += dp[tmp]
            dp[i] %= mod

print(int(dp[N - 1]))

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    N, K = map(int, sys.stdin.readline().rstrip().split())
    L = [0] * 10
    R = [0] * 10
    for i in range(K):
        l, r = map(int, sys.stdin.readline().rstrip().split())
        L[i], R[i] = l, r

    dp = [0] * (N+1)
    dp[1] = 1
    for i in range(2,N+1):
        for j in range(K):
            l = min(L[j], i)
            r = min(R[j], i)
            dp[i] += sum(dp[i-r:(i-l)+1])
            dp[i] %= 998244353
        # print(dp[i])
    
    print(dp[N])


main()

Submission status: Time Limit Exceeded

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

n,k = map(int,input().split())
s = []
for i in range(k):
  l,r = map(int,input().split())
  s.append((l,r))
s.sort(key=lambda x:x[1], reverse=True)
MOD = 998244353

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

def f(x):
  if x < 1:
    return 0
  if x == 1:
    return 1
  if memo[x] != -1:
    return memo[x]
  res = 0
  for l,r in s:
    for i in range(r,l-1,-1):
      res += f(x-i)
      res %= MOD
  memo[x] = res
  return res

print(f(n))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
li = []
for i in range(K):
  l, r = map(int, input().split())
  for j in range(l, r+1):
    li.append(j)
li.sort()
    
ans = [0] * (N+1)
ans[1] = 1
for i in range(1, N+1):
  if ans[i] > 0:
    for n in li:
      if i+n <= N:
        ans[i+n] += ans[i]
        ans[i+n] %= 998244353
      else:
        break
print(ans[-1])

Submission status: Time Limit Exceeded

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

arr={0}
for i in range(K):
    a,b=map(int,input().split())
    arr|=set([j for j in range(a,b+1)])

arr.discard(0)


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

ans=0
for i in range(N):
    for j in arr:
        if i+j<=N-1:
            dp[i+j]+=dp[i]
    
    
print(dp[-1]%998244353)