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:
import sys
input = sys.stdin.readline

N,K = (int(x) for x in input().rstrip('\n').split())
As = []
n = [x for x in range(1,N+1)]
for _ in range(K):
  L,R = (int(x) for x in input().rstrip('\n').split())
  As.extend(n[L-1:R])
res_d = {0:1}
for i in range(1,N):
  res = 0
  for k,v in res_d.items():
    if any(k+x==i for x in As):
      res += v
  res_d[i] = res%998244353
print(res_d[N-1])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
N-=1
mvs = set()
mods = 998244353
dps = [0]+[0 for i in range(N)]

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:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)

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(reverse=True)


@lru_cache(maxsize=None)
def rec(n):
    if n == 1:
        return 1
    else:
        ans = 0
        for k in lr:
            if n - k >= 1:
                ans += rec(n - k)
                ans %= MOD
    return ans


print(rec(n))

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(s) for s in input().split()]
rans = []
for _ in range(K):
    l, r= [int(s) for s in input().split()]
    rans.append((l, r))
rans.sort()

prev = -1
newrans = []
for ran in rans:
    l, r = ran
    if l <= prev:
        newrans[-1] = max(r, newrans[-1])
    else:
        newrans.append([l,r])
    prev = max(prev, r)

rans = newrans
sums = [0, 1]
s = 1
# print(rans)
for i in range(2, N+1):
    # print(sums, i)
    for ran in rans:
        l = i - ran[0]
        r = max(i - ran[1] - 1, 0)
        # print(l, r, s)
        if l >= 0:
            s += sums[l] - sums[r]
    sums.append(s)
# print(sums)
if N == 1:
    print(1)
else:
    print((sums[-1] - sums[-2]) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():

    input = sys.stdin.readline

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

    S = set()

    mod = 998244353

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

        for i in range(l,r+1):
            S.add(i)

    masu = [0] * N

    masu[0] = 1

    for i in range(N):
        for j in S:
            if i+j < N:
                masu[i+j] += masu[i]
                masu[i+j] %= mod

    print(masu[N-1] % mod)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

S = []

for i in range(K):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        S.append(j)

dp = [0] * N * 10

dp[1] = 1

for i in range(2, N + 1):
    count = 0
    for s in S:
        if i > s:
            count = (count + dp[i - s]) % 998244353
    dp[i] += count % 998244353

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
N-=1
mvs = set()
mods = 998244353
dps = [0]+[0 for i in range(N)]

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:
    dps[i] += dps[i-k] % mods if i-k >0 else 0
print(dps[N]%mods)

Submission status: Time Limit Exceeded

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


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

for i in range(K):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        S.add(j)

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

def f(n):
    if flag[n]:
        return dp[n]
    flag[n] = 1
    ret = dp[n]
    for step in S:
        if n >= step:
            ret += f(n - step) % MOD
            ret %= MOD
    dp[n] = ret
    return ret

print(f(N))

Submission status: Time Limit Exceeded

Solution code:
def main():
  N, K = map(int, input().split())
  dis = []
  mod = 998244353
  for _ in range(K):
    L, R = map(int, input().split())
    if L == R:
      dis.extend([L])
    else:
      dis.extend(list(range(L, R+1)))
  
  lst = [0] * (N+1)
  lst[0] = 1
  for i in range(1, N):
    for j in dis:
      if i-j >= 0:
        lst[i] += lst[i-j]
    lst[i] = lst[i] % mod
  print(lst[i])
  
main()

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np

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


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

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

def move(x):
    res = -1
    if memo[x] != -1:
        res = memo[x]
    elif x < 0:
        res = 0
    elif x == 0:
        res = 1
    else:
        tmp = 0
        for s in S:
            tmp += move(x - s)
        res = tmp
    if x >= 0:
        memo[x] = res
    return res

for i in range(N):
    move(i)
res =  move(N - 1) % 998244353
print(res)
# print(memo)

Submission status: Time Limit Exceeded

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

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

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

for i in range(1,N):
  for j in S:
    if i >= j:
      DP[i] += DP[i-j]
      
print(DP[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

n,k=map(int,input().split())
s=set()
for i in range(k):
  l,r=map(int,input().split())
  s |= set(range(l,r+1))
  
memo=[0]*(2*n)
memo[1]=1

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

print(memo[n]%998244353)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
dp = [0]*(n+1)
dp[1] = 1
li = []
c = 998244353
for _ in range(k):
    x, y = map(int, input().split())
    for i in range(x, y+1):
        if i not in li:
            li.append(i)
for i in range(n+1):
    for j in li:
        if i > j:
            dp[i] = (dp[i]+dp[i-j])
print(dp[-1]%c)

Submission status: Time Limit Exceeded

Solution code:
nk=input("").split(" ")
n=int(nk[0])
k=int(nk[1])
listp=[]
for i in range(n):
    listp+=[-1]
listp[0]=1
listlr=[]
for i in range(k):
    lr=input("").split(" ")
    listlr+=[[int(lr[0]),int(lr[1])]]
    



def funcp(n):
    if(listp[n-1]==-1):
        s=0
        for ii in range(k):
            for i in range(n-listlr[ii][1],n-listlr[ii][0]+1):
                if(i>0):
                    s+=funcp(i)
        s%=998244353
        listp[n-1]=s
        
        return s
    else:
        return listp[n-1]
print(funcp(n))

Submission status: Time Limit Exceeded

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

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


@lru_cache(maxsize=None)
def rec(n):
    if n == 1:
        return 1
    else:
        ans = 0
        for k in lr:
            if n - k >= 1:
                ans += rec(n - k)
                ans %= MOD
    return ans


print(rec(n))

Submission status: Time Limit Exceeded

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

N,K = (int(x) for x in input().rstrip('\n').split())
As = []
n = [x for x in range(1,N+1)]
for _ in range(K):
  L,R = (int(x) for x in input().rstrip('\n').split())
  As.extend(n[L-1:R])
res_d = {0:1}
for i in range(1,N):
  res = 0
  for k,v in res_d.items():
    if any(k+x==i for x in As):
      res += v
  res_d[i] = res%998244353
print(res_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)]
s = []
mod = 998244353

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

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

for i in range(n):
    for j in s:
        if i+j > n:
            continue
        li[i+j] += li[i]
        li[i+j] %= mod

print(li[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)]
step = []
for l,r in LR:
    for i in range(l,r+1):
        step.append(i)
mod = 998244353
ma = [0] * N
ma[0] = 1
for i in range(N):
    if ma[i] != 0:
        for j in step:
            if i+j < N:
                ma[i+j] += ma[i]
print(ma[N-1]%mod)

Submission status: Time Limit Exceeded

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

Move = []

for i in range(K):
    value = L[i]
    while True:
        Move.append(value)
        value += 1
        if value > R[i]:
            break
#Move.sort()
# print(Move)

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

for i in range(1, N):
    for m in Move:
        if i - m >= 0:
            DP[i] += DP[i - m]
            DP[i] = DP[i] % mod
        # else:
        #     break
print(DP[N - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(2*10**5)
MOD = 998244353
LR = []
memo = {}

def solve(n):
    if n == 1:
        return 1
    if n in memo:
        return memo[n]
    answer = 0 
    for l, r in LR:
        for d in range(l, r+1):
            if n-d > 0:
                answer += solve(n-d)
                answer %= MOD
    memo[n] = answer
    return answer


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

Submission status: Time Limit Exceeded

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

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


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

for i in range(1,N):
  for j in S:
    if i >= j:
      DP[i] += DP[i-j]
      
print(DP[-1]%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())
    for j in range(l, r + 1):
        S.append(j)

dp = [0] * N * 10

dp[1] = 1

for i in range(2, N + 1):
    count = 0
    for s in S:
        if i > s:
            count += dp[i - s]
            count = count % 998244353
    dp[i] += count

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools


def resolve(in_):
    N, K = map(int, next(in_).split())
    LR = tuple(tuple(map(int, line.split()) for line in itertools.islice(in_, K)))

    r = tuple(itertools.chain.from_iterable(iter(range(l, r + 1)) for l, r in LR))
    dp = [0] * (N + 1)
    dp[1] = 1
    mod = 998244353

    for i in range(1, N + 1):
        for j in r:
            index = i - j
            if index > 0:
                dp[i] += dp[index]
                dp[i] %= mod
    
    return dp[N]



def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


dp = [0] * 2 * N
dp[N] = 1
for i in range(1, N):
    for ll, rr in lis:
        dp[N + i] += (sum(dp[(N + i - rr + 1): (N + i - ll + 1)]) % 998244353)
print(dp[2 * N - 1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
n,k  = map(int, input().split())
s = []
alist = [0] * 1_000_000
alist[1] = 1    # start point

for i in range(k):
    s_i = list(map(int, input().split()))
    s.extend([x for x in range(s_i[0], s_i[1] + 1)])
s.sort()

for i in range(n):
    if alist[i] == 0: continue
    for j in range(len(s)):
        alist[i+s[j]] += alist[i]
print(alist[n] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  field=[LI() for _ in range(k)]
  field.sort()

  rng=[]
  for x,y in field:
    for z in range(x,y+1):
      rng.append(z)

  # print(rng)

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

  rng_mx=len(rng)
  for i in range(1,n):
    for j,dx in enumerate(rng[:rng_mx]):
      if i+dx>n:
        rng_mx=j+1
        break
      dp[i+dx]+=dp[i]
      dp[i+dx]%=mod
    # print(dp)
  
  return dp[n]%mod

# main()
print(main())

Submission status: Time Limit Exceeded

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

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

D = [0] * N
D[0] = 1

for n in range(N):
  for i in range(n):
    if (n - i) in S:
      D[n] += D[i] % 998244353
      
print(D[N - 1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
s=[]
for _ in range(k):
    l,r=map(int,input().split())
    for i in range(l,r+1):
        s.append(i)
s=sorted(s)
ans=[0]*(10**6)
ans[0]=1
for i in range(n-1):
    for j in s:
        ans[i]=ans[i]%998244353
        ans[i+j]+=ans[i] 
print(ans[n-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

N, K = map(int, input().split())
S = set()
for _ in range(K):
    l, r = map(int, input().split())
    for i in range(l, r+1):
        S.add(i)

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

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
mod=998244353
N,K=map(int,input().split())
_S=[]
for _ in range(K):
    l,r=map(int,input().split())
    _S+=list(range(l,r+1))
S=sorted(_S)
dp=[0]*(N+1)
dp[1]=1
for i in range(1,N-S[0]+1):
    for s in S:
        if s+i>N:
            S.remove(s)
            break
        dp[i+s]+=dp[i]
        dp[i+s]%=mod
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

n, k = map(int, sys.stdin.buffer.readline().split())
leap = set()
cell = np.array([0]*n, np.int64)
cell[0] = 1 
for x in sys.stdin.buffer.readlines():
    l, r = map(int, x.split())
    leap |= set(range(l,r+1))

for i in range(n):
    if cell[i]:
        for j in leap:
            if i + j < n:
                cell[i+j] += cell[i]

print(cell[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
MOD = 998244353
S = set()
for i in range(K):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        S.add(j)

dp = [0] * N
dp[0] = 1
for i in range(1, N):
    for s in S:
        if s > i:
            continue
        dp[i] += dp[i - s]
print(dp[-1] % MOD)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
MOD=998244353
S=[]
for _ in range(K):
    L,R=map(int,input().split())
    S.append((L,R))
dp=[0]*(N+1)
dp[1]=1
for i in range(2,N+1):
    for j in range(K):
        L,R=S[j][0],S[j][1]
        if L>=i:
            continue
        l=max(0,i-R)
        r=min(i-1,i-L)
        dp[i]+=sum(dp[l:r+1])
        dp[i]%=MOD
print(dp[N]%MOD)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
mod=998244353
dp=[0]*n
dp[0]=1
l=[list(map(int,input().split(" "))) for i in range(k)]
for i in range(n):
    for j in range(k):
        for m in range(l[j][0],l[j][1]+1):
            if i-m>=0:
                dp[i]+=dp[i-m]%mod
print(dp[n-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

dd = defaultdict(int)
dd[N] = 1

for _i in range(N-1):
    i = N-1 - _i
    for l, r in LRs:
        for d in range(l, r+1):
            dd[i] = (dd[i] + dd[i+d]) % mod

print(dd[1])

Submission status: Time Limit Exceeded

Solution code:
N ,K = map(int,input().split())
S = []
mod = 998244353
for _ in range(K): 
    l,r = map(int,input().split())
    S += list(range(l,r+1))
dp = [0]*(N+10) 
dp[0]=1
for n in range(N):
    for i in S:
        if n >= i:
            dp[n] += dp[n-i]
print(dp[N-1]%mod)

Submission status: Time Limit Exceeded

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

def main():
    input = sys.stdin.readline
    n, k = map(int, input().split())
    tmp = []
    for _ in range(k):
        l, r = map(int, input().split())
        for i in range(l, r + 1):
            tmp.append(i)
    tmp.sort()
    dp = [0] * n
    dp[0] = 1
    tmp_len = len(tmp)

    for i in range(n):
        for j in range(tmp_len):
            if i + tmp[j] <= n - 1:
                dp[i + tmp[j]] += dp[i]
                dp[i + tmp[j]] %= 998244353
            else:
                tmp_len = j
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


m = 998244353

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

for i in range(n):
    for j in range(k):
        for a in range(l[j], r[j]+1):
            if i + a >= n:
                break
            dp[i+a] += dp[i]
            dp[i+a] %= m

print(dp[n-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

MOD = 998244353  # type: int


def solve(N: int, K: int, L: "List[int]", R: "List[int]"):
    dp = [0] * (N + 1)
    dp[1] = 1
    s = []
    for i in range(K):
        for j in range(L[i], R[i]+1):
            s.append(j)
    for i in range(1, N+1):
        for j in s:
            if i - j >= 1:
                dp[i] += dp[i-j]
                dp[i] %= MOD
    print(dp[N]%MOD)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    L = [int()] * (K)  # type: "List[int]"
    R = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    solve(N, K, L, R)

if __name__ == '__main__':
    main()

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 = S|set(range(l,r+1))
S=list(S)
ans = [0]*n
ans[0]=1
for i in range(n):
  for s in S:
    if i+s < n:
      ans[i+s] += ans[i]
print(ans[n-1]%998244353)

Submission status: Time Limit Exceeded

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

MOD = 998244353
for _ in range(K):
    L, R = map(int, input().split())
    S |= set(range(L, R + 1))
# print(f'{S=}')

DP = [0] * (N + 5) * 2
DP[0] = 0
DP[1] = 1

# 配るDP
for i in range(1, N + 1):
    for s in S:
        DP[i + s] += DP[i]
    DP[i] %= MOD
# print(f'{DP=}')
print(DP[N])

Submission status: Time Limit Exceeded

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

N,K = map(int,input().split())
S = []
MOD = 998244353
r_max = 0
for i in range(K):
    l,r = map(int,input().split())
    r_max = max(r,r_max)
    for x in range(l,r+1):
        S.append(x)

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

for i in range(0,N):
    for x in S:
        dp[i+x] += dp[i]

print(dp[N-1]%MOD)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
s=[]
dp=[0]*(n+5)
for i in range(k):
     l,r =map(int,input().split())
     for j in range(l,r+1):
         s.append(j)
          
s.sort()
dp[0]=1
dp[s[0]]=1
for i in range(s[0]+1,n+4):
    for j in s:
        if j>i:
            break
        else:
            dp[i]+= dp[i-j] % 998244353
        dp[i] %= 998244353
print(dp[n-1])

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

dp = [0] + [-1] * n
def dfs(goal, route):
    if dp[goal] != -1:
        return dp[goal]
    else:
        ans = 0
        for r in route:
            if goal - r < 1:
                continue
            else:
                ans = (ans + dfs(goal - r, route)) % MOD
        dp[goal] = ans
        return dp[goal]
dp[1] = 1
print(dfs(n, s))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
dp = [0]*(n+1)
dp[1] = 1
li = []
c = 998244353
for _ in range(k):
    x,y = map(int,input().split())
    for i in range(x,y+1):
        if i not in li:
            li.append(i)
for i in range(n+1):
    for j in li:
        if i>j:
            dp[i] = (dp[i]+dp[i-j])%c
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain
(N,K), *lr = [list(map(int, s.split())) for s in open(0)]
lr.sort()
MOD = 998244353
dp = [0] * (N+1)
dp[1] = 1

steps = list(chain(*[range(l, r+1) for l, r in lr]))

for i in range(1, N+1):
    if i+steps[0] > N:
        break
    for step in steps:
        if i+step <= N:
            dp[i+step] = (dp[i+step] + dp[i]) % MOD
print(dp[-1])

Submission status: Time Limit Exceeded

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

MOD = 998244353  # type: int


def solve(N: int, K: int, L: "List[int]", R: "List[int]"):
    dp = [0] * (N + 1)
    dp[1] = 1
    s = []
    for i in range(K):
        for j in range(L[i], R[i]+1):
            s.append(j)
    for i in range(1, N+1):
        for j in s:
            if i - j >= 1:
                dp[i] += dp[i-j]
    print(dp[N]%MOD)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    L = [int()] * (K)  # type: "List[int]"
    R = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    solve(N, K, L, R)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
mod = 998244353
ans = [0]*(n*2)
ans[0] = 1
c = []


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

c = sorted(c)

for i in range(n):
    for j in c:
        if i + j > n:
            break
        ans[i + j] += ans[i]%mod


print(ans[n - 1]%mod)

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split()))
move = []
for i in range(k):
    s, t = list(map(int, input().split()))
    m = list(range(s, t + 1))
    move += m

mod = 998244353

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

for i in range(n):
    p = i
    temp = 0
    for m in move:
        if m <= p:
            temp += dp[p - m]
    dp[p] += temp % mod

print(dp[n-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


dp = [0] * 2 * N
dp[N] = 1
for i in range(1, N):
    for ll, rr in lis:
        dp[N + i] += sum(dp[(N + i - rr + 1): (N + i - ll + 1)])
print(dp[2 * N - 1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

numset = set()
for i in range(K):
    l, r = map(int, input().split())
    numset |= set(range(l,r+1))

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

numlist = list(numset)
for i in range(2,N+1):
    for j in numlist:
        if j >= i:
            break
        dp[i] += dp[i-j]
    
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)]
s = []
mod = 998244353

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

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

for i in range(n):
    for j in s:
        li[i] += li[i-j]
        li[i] %= mod

print(li[n-1])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
s=[]
for _ in range(k):
    l,r=map(int,input().split())
    for i in range(l,r+1):
        s.append(i)
s=sorted(s)
ans=[0]*(10**6)
ans[0]=1
for i in range(n-1):
    for j in s:
        ans[i+j]+=ans[i] 
print(ans[n-1]%998244353)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n,k= list(map(int, input().split()))
INF=998244353
s=[]
for i in range(k):
    j,k=map(int,input().split())
    s+=[l for l in range(j,k+1)]
pattern=[0 for i in range(n)]
pattern[0]=1
ls=len(s)
s.sort()
for i in range(1,n):
    tmp=0
    for j in s:
        if i-j<0:
            break
        tmp+=pattern[i-j]
        tmp%=INF
    pattern[i]=tmp
print(pattern[-1])

Submission status: Time Limit Exceeded

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

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

import itertools
s = list(itertools.chain.from_iterable(s))

s.sort()

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

for l in range(1,n):
    for m in s:
        if l-m <0:
            break
        dp[l] = (dp[l] +dp[l-m]) % 998244353 

print(dp[n-1]%998244353 )

Submission status: Time Limit Exceeded

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

dp = [0] * (N+1)

mvlst = list()
for i in range(K):
    l, r = list(map(int, input().split()))
    for j in range(l, r+1):
        mvlst.append(j)

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

print(dp[N] % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

N, K = map(int, input().split())
S = set()
for _ in range(K):
    l, r = map(int, input().split())
    for i in range(l, r+1):
        S.add(i)

mod = 998244353
dp = [0 for _ in range(N+1)]
dp[1] = 1
for i in range(1, N):
    for s in S:
        if i + s <= N:
            dp[s+i] += dp[i]
            dp[s+i] %= mod

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys

n, k = map(int, sys.stdin.buffer.readline().split())
leap = set()
cell = [0]*n
cell[0] = 1 
for x in sys.stdin.buffer.readlines():
    l, r = map(int, x.split())
    leap |= set(range(l,r+1))

for i in range(n):
    if cell[i]:
        for j in leap:
            if i + j < n:
                cell[i+j] += cell[i]

print(cell[-1]%998244353)

Submission status: Time Limit Exceeded

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

mod = 998244353

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

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

s = set(s)

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

for i in range(n):
    if dp[i] == 0:
        continue
    for s_ele in s:
        dp[i+s_ele] += dp[i]

print(dp[n-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
N, K = map(int, input().split())
table = [False] * N
path = [0] * N

for i in range(K):
  l, r = map(int, input().split())
  for j in range(l-1, r):
    table[j] = True

path[0] = 1
for i in range(1, N):
  total = 0
  for j in range(i):
    if table[i-j-1]:
      total = (total + path[j]) % MOD
  path[i] = total

print(path[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)]

S = set()
for l,r in LR:
  S = S.union(set(range(l, r+1)))

path_num_dict = {1:1}
for i in range(2, N+1):
  path_num = 0
  for d in S:
    j = i - d
    if j >= 1:
      path_num += path_num_dict[j] % 998244353
  path_num_dict[i] = path_num % 998244353
print(path_num_dict[N])

Submission status: Time Limit Exceeded

Solution code:
N ,K = map(int,input().split())
S = []
mod = 998244353
for _ in range(K): 
    l,r = map(int,input().split())
    S += list(range(l,r+1))
S.sort()
dp = [0]*(N+10) 
dp[0]=1
for n in range(N):
    for i in S:
        if n >= i:
            dp[n] += dp[n-i]
print(dp[N-1]%mod)