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())
MOD = 998244353

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

lr.sort()

dp = [0] * n

dp[0] = 1

for i in range(n - 1):
    for k in lr:
        if i + 1 - k >= 0:
            dp[i + 1] += dp[i + 1 - k]
            dp[i + 1] %= MOD

print(dp[-1])

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 j in range(l, r+1):
        S.append(j)

S = sorted(S)
dp = [0] * (N+1)
dp[1] = 1
for i in range(1, N):
    for j in S:
        if i + j > N:
            break
        dp[i+j] = (dp[i+j] + dp[i]) % mod

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
p = 998244353
N,K = [int(i) for i in input().split()]
L = [0]*(N+1)
L[1] = 1
nums = []
for _ in range(K):
    a,b = [int(i) for i in input().split()]
    for i in range(a,b+1):
        nums.append(i)
for i in range(2,N+1):
    for j in range(1,i):
        if i-j in nums:
            L[i] = (L[i] + L[j])%p
print(L[-1])

Submission status: Time Limit Exceeded

Solution code:

def solve():
    MOD = 998244353
    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)))
        S |= _s

    # dp[i] : iに到達する経路数
    dp = [0] * (N+1)
    dp[1] = 1
    for i in range(2, N+1):
        for d in S:
            if i-d > 0:
                dp[i] = (dp[i] + dp[i-d]) % MOD
    print(dp[N])


solve()

Submission status: Time Limit Exceeded

Solution code:
N, K  = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(K)]
S = set()
for l in L:
  S = S|set([i for i in range(l[0], l[1]+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]
      DP[i] %= 998244353
    else:
      break
  continue
print(DP[-1])

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

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

S = set()
for l, r in lr:
    for j in range(l, r+1):
        S.add(j)

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

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:

import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

mod = 998244353

N, K = nn()
T = nm(K)

dp = array1(N)
dp[0] = 1

T = sorted(T, key=lambda x: x[0])

for i in range(N):
    for j in range(K):
        L, R = T[j]
        for k in range(L, R+1):
            if i+k < N:
                dp[i+k] = (dp[i+k] + dp[i]) % mod

print(dp[N-1])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
l, r = map(int, input().split())
s = set(range(l, r+1))
for i in range(1, k):
    l, r = map(int, input().split())
    s = s | set(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]
    dp[i] = dp[i]%998244353
print(dp[-1])

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 = set()
    for _ in range(k):
        l, r = map(int, input().split())
        for i in range(l, r + 1):
            tmp.add(i)
    dp = [0] * n
    dp[0] = 1
    for i in range(n):
        for j in tmp:
            if i + j <= n - 1:
                dp[i + j] += dp[i]
                dp[i + j] %= 998244353
    
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
from decimal import Decimal
# from fractions import Fraction
# sys.setrecursionlimit(100000)
mod = 998244353
INF=float('inf')

n,k=mdata()
lis=[]
dp=[0]*(n)
dp[0]=1
for i in range(k):
    l,r=mdata()
    for j in range(l,r+1):
        lis.append(j)
lis.sort()
for i in range(1,n):
    for j in lis:
        if j>i:
            break
        dp[i]=(dp[i]+dp[i-j])%mod
out(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
q = 998244353

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

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

S.sort()

result = [0] * N
result[0] = 1

for i in range(N):
    for s in S:
        if i + s < N:
            result[i + s] = (result[i + s] + result[i]) % q
        else:
            break

print(result[-1])

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:
n, k= map(int, input().split())
r = [
    tuple(map(int, input().split()))
    for _ in range(k)
]
r = sorted(r)

x = [None] * n
x[0] = 1
for i in range(n):
    if x[i] is None:
        continue
    for j in range(k):
        f = False
        for p in range(r[j][0], r[j][1] + 1):
            if i + p >= n:
                f = True
                break
            if x[i + p] is None:
                x[i + p] = x[i]
            else:
                x[i + p] += x[i]
            x[i + p] %= 998244353
        if f:
            break
if x[n - 1] is None:
    print(0)
else:
    print(x[n - 1])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
MOD = 998244353
P = []
for _ in range(K):
    l, r = map(int, input().split())
    for i in range(l, r+1):
        P.append(i)
dp = [0]*(N+1)
dp[0]=1
for i in range(N):
    for p in P:
        dp[min(i+p,N)] += dp[i]
        dp[min(i + p, N)]%=MOD
print(dp[N-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split()))
s = []
for i in range(k):
    a, b = list(map(int, input().split()))
    for j in range(a, b+1):
        s.append(j)
s = set(s)
dp = [0]*(n+1)
dp[1] = 1
mod = 998244353
for i in range(1, n+1):
    for ss in s:
        if i+ss <= n:
            dp[i+ss] += dp[i]
            dp[i+ss] %= mod
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
(n,k),*e=[[*map(int,i.split())]for i in open(0)]
mod=998244353
a=[0]*n
a[0]=1
b=[]
e.sort()
for i,j in e:
    b+=range(i,j+1)
for i in range(n):
    for j in b:
        if i+j<n:
            a[i+j]+=a[i]
            a[i+j]%=mod
        else:break
print(a[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
N,K = map(int,input().split())
LR = [tuple(map(int,input().split())) for i in range(K)]
LR.sort()
MOD = 998244353

arr = []
for l,r in LR:
    for i in range(l,r+1):
        arr.append(i)

from functools import lru_cache
@lru_cache(maxsize=10**8)
def rec(n):
    if n==0: return 1
    ret = 0
    for a in arr:
        if n-a < 0: break
        ret += rec(n-a)
        ret %= MOD
    return ret

print(rec(N-1))

Submission status: Time Limit Exceeded

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

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

    for j in range(l, r+1):
        s.append(j)

dp = [0] * n
dp[0] = 1
for i in range(n):
    for j in s:
        ind = i-j
        if ind >= 0:
            dp[i] += dp[ind]
            dp[i] %= 998244353

print(dp[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())
    for j in range(L, R + 1):
        lis.append(j)


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

print(dp[2 * N - 1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
#import math
#import itertools
import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
MOD = 998244353
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,k=INTM()
    lrs=[]
    for i in range(k):
        lrs.append(LIST())
    pt=np.array([0]*((2*n)+1))
    pt[0]=1
    for i in range(n):
        for l,r in lrs:
            pt[i+l:i+r+1]+=pt[i]
            pt[i+l:i+r+1]=pt[i+l:i+r+1]%MOD
    
    print(pt[n-1]%MOD)


if __name__=='__main__':
    do()

Submission status: Time Limit Exceeded

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

lr = []
for _ in range(K):
    l, r = map(int, input().split())
    for x in range(l, r+1):
        lr.append(x)
lr.sort()
for i in range(N-1):
    for x in lr:
        if x + i < N:
           dp[x+i] += dp[i]
           dp[x+i] %= mod
        else:
            break
print(dp[N-1])

Submission status: Time Limit Exceeded

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

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

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


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

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

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


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

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
# MOD = 10 ** 9 + 7
MOD = 998244353


def main():
    N, K = map(int, readline().split())
    S = set()
    for k in range(K):
        L, R = map(int, readline().split())
        S |= set(range(L, R + 1))

    dp = [0] * (N + 20)
    dp[1] = 1
    S = list(S)
    S.sort()

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def count(n, x, y):
    ans = 0
    for i in range(len(x)):
        if (n - x[i] <= 0):
            pass
        else:
            ans = ans + y[n - x[i]]
    y.append(ans%998244353)

for i in range(n + 1):
    if (i != 0 and i != 1):
        count(i, lst, lst2)

print(lst2[n])

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353

N, K = list(map(int, input().split()))
move = []
for _ in range(K):
    L, R = list(map(int, input().split()))
    for i in range(L, R+1):
        move.append(i)
dp = [0]*(2*N+10)
dp[0] = 1
for i in range(N):
    tmp = dp[i]
    for m in move:
        dp[i+m] += tmp
        dp[i+m] %= mod
print(dp[N-1])

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353

N, K, *LR = map(int, open(0).read().split())

S = set()
for l, r in zip(*[iter(LR)] * 2):
    for i in range(l, r + 1):
        S.add(i)

S = sorted(S)

dp = [0] * N
dp[0] = 1
for i in range(N):
    for s in S:
        if i + s >= N:
            break
        dp[i + s] += dp[i]
        dp[i + s] %= mod

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
mod = 998244353
dp = [0]*N
dp[0] = 1

ok = [0]*(N+1)
for _ in range(K):
    l, r = mapint()
    ok[l-1] += 1
    ok[r] -= 1
from itertools import accumulate
ok = list(accumulate(ok))
lis = [i for i in range(1, N+1) if ok[i-1]]
for i in range(N):
    for d in lis:
        if i-d>=0:
            dp[i] += dp[i-d]
            dp[i] %= mod

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
n,k=[int(c) for c in input().split()]
MOD = 998244353
segs = set()
for _ in range(k):
    a,b=[int(c) for c in input().split()]
    for i in range(a,b+1):
        segs.add(i)

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

for i in range(n-1):
    if dp[i] != 0:
        for j in segs:
            if i + j < n:
                dp[i+j] = dp[i+j] + dp[i]
                dp[i+j]%=MOD

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

Submission status: Time Limit Exceeded

Solution code:
N, K  = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(K)]
S = set()
for l in L:
  S = S|set([i for i in range(l[0], l[1]+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]
      DP[i] %= 998244353
print(DP[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
# MOD = 10 ** 9 + 7
MOD = 998244353


def main():
    N, K = map(int, readline().split())
    S = set()
    for k in range(K):
        L, R = map(int, readline().split())
        S |= set(range(L, R + 1))

    dp = [0] * (N + 20)
    dp[1] = 1
    S = list(S)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

D = sorted(D)
dp[0] = 1
for i in range(N):
    for d in D:
        if i + d > N:
            continue
        dp[i + d] += dp[i]
        dp[i + d] %= mod

print(dp[N-1])

Submission status: Time Limit Exceeded

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

x = [None] * n
x[0] = 1
for i in range(n):
    if x[i] is None:
        continue
    for j in range(k):
        for p in range(l[j], r[j] + 1):
            if i + p >= n:
                break
            if x[i + p] is None:
                x[i + p] = x[i]
            else:
                x[i + p] += x[i]
            x[i + p] %= 998244353
if x[n - 1] is None:
    print(0)
else:
    print(x[n - 1])

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=list()
    for i in range(K):
        l,r=map(int,input().split())
        for j in range(l,r+1):
            L.append(j)
    mod=998244353
    L.sort()

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

        for l in L:
            if i+l>N:
                break
            dp[i+l] +=dp[i]
            dp[i+l] %=mod

    print(dp[N-1])













if __name__ == "__main__":
    main()

# \n

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
N,K = map(int,input().split())
ran = []
DP = [0]*(N+1)
DP[1] = 1
for i in range(K):
  a,b = map(int,input().split())
  ran.extend([x for x in range(a,b+1)])
ran.sort()
for i in range(N+1):
  for j in ran:
    if j >= i:
      break
    DP[i] = (DP[i] + DP[i-j]) % MOD
print(DP[N])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env Python3

#import
#import math
#import numpy as np
#= int(input())
#= input()
modnum = 998244353

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

def mod(num):
    return num % modnum

S = []

for l, r in LR:
    for i in range(l, r + 1):
        if not i in S:
            S.append(i)

dp = [0] * N

dp[0] = 1

for i in range(1, N):
    for s in S:
        if not s > i:
            dp[i] = mod(dp[i] + dp[i - s])

print(dp[N-1])

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N, K = MI()
    s = set()
    mod = 998244353
    for i in range(K):
        l, r = MI()
        for j in range(l, r+1):
            s.add(j)
    dp = [0] * (N+1)
    dp[1] = 1
    for i in range(1, N):
        for ss in s:
            idx = i + ss
            if idx < N+1:
                dp[i+ss] += dp[i]
        # print(dp)
    print(dp[N] % mod)
            
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
# # Make IO faster
# import sys
# input = sys.stdin.readline

# # get single (or) multiple str
# X = input()

# # get single int
# N = int(input())
# # get multiple int (e.g., 2)
# X, Y = map(int, input().split())
# # get multiple int (e.g., 2) for N lines
# XY = [list(map(int, input().split())) for _ in range(N)]

# from IPython import embed; embed(); exit();

# 全部入り
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = list(MAP())
x = set()
for i in range(K):
    l, r = list(MAP())
    for j in range(l, r + 1):
        x.add(j)

ans = [0 for _ in range(N)]
ans[0] = 1
for i in range(1, N):
    for j in x:
        if 0 <= (i - j):
            ans[i] = (ans[i] + ans[i - j]) % 998244353
print(ans[-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())
    S += [i for i in range(l, r+1)]
S.sort()
mod = 998244353

dp = [0] * (N+1)
dp[1] = 1
for i in range(1, N+1):
    for d in S:
        if i+d > N:
            break
        dp[i+d] += dp[i] % mod
print(dp[N]%mod)

Submission status: Time Limit Exceeded

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

#import
#import math
#import numpy as np
#= int(input())
#= input()
modnum = 998244353

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

def mod(num):
    return num % modnum

S = []

for l, r in LR:
    for i in range(l, r + 1):
        if not i in S:
            S.append(i)

dp = [0] * N

dp[0] = 1

for i in range(1, N):
    for s in S:
        if not s > i:
            dp[i] = mod(dp[i] + dp[i - s])

print(dp[N-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    MOD = 998244353
    cand = set()
    for _ in range(K):
        L, R = map(int, input().split())
        A = set(range(L,R+1))
        cand |= A

    dp = [0] * (N + 5)
    dp[0] = 1
    for i in range(N):
        for j in cand:
            if i + j <= N:
                dp[i+j] += dp[i]
                dp[i+j] %= MOD

    print(dp[N-1])
    




if __name__ == "__main__":
    main()

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,readline().split())
vec = [0]*(n+1)
for i in range(k):
    l,r = map(int,readline().split())
    for j in range(l,r+1):
        vec[j] = 1

to = []

for i in range(1,n+1):
    if vec[i] == 1:
        to.append(i)

dp = [0]*(n+1)
dp[1] = 1
for i in range(1,n+1):
    for j in to:
        if (i+j > n):
            break
        dp[i+j] = (dp[i]+dp[i+j])%mod

print(dp[n])

Submission status: Time Limit Exceeded

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

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

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

for index in range(N):
    for A in area:
        for i in range(A[0], A[1] + 1):
            DP[index + i] += DP[index]
            DP[index + i] %= MOD

print(DP[N - 1])

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())
    for i in range(L,R+1):
        if i not in S:
            S.append(i)

# dp[i]: マスiに移動する方法
dp = [0] * 200010
dp[0] = 1

for i in range(N):
    for d in S:
        if i+d < N:
            dp[i+d] += dp[i]
            dp[i+d] %= MOD

print(dp[N-1])

Submission status: Time Limit Exceeded

Solution code:
q = 998244353

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

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

result = [0] * N
result[0] = 1

for i in range(N):
    for s in S:
        if i + s < N:
            result[i + s] = (result[i + s] + result[i]) % q

print(result[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,k = na()
mod = 998244353
dp = [1] + [0]*(n-1)
hw = []

for i in range(k):
    l,r = na()
    for j in range(l,r+1):
        hw.append(j)

for i in range(n):
    for p in hw:
        if i+p < n:
            dp[i+p] = (dp[i]+dp[i+p])%mod

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N, K, *LR = [int(_) for _ in open(0).read().split()]
L = LR[::2]
R = LR[1::2]
mod = 998244353
dp = [0] * 3 * N
dp[1] = 1
for s in range(1, N):
    for l, r in zip(L, R):
        for d in range(l, r + 1):
            dp[s + d] += dp[s]
            dp[s + d] %= mod
print(dp[N])

Submission status: Time Limit Exceeded

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

MOD = 998244353

lst = []
for _ in range(K):
  l, r = map(int, input().split())
  for i in range(l, r+1):
    lst.append(i)
    
#print(lst)

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

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

Submission status: Time Limit Exceeded

Solution code:
p = 998244353

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

hop = []

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

dp = [0]*N

dp[0] = 1

for i in range(N - 1):
    for j in range(len(hop)):
        if i + hop[j] < N:
            dp[i + hop[j]] += dp[i]
            dp[i + hop[j]] %= p

print(dp[N - 1] % p)

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))
C = 998244353
S = set()
for _ in range(K):
    l, r = list(map(int, input().split()))
    S |= set(range(l, r+1))
# print(S)

dp = [0]*N
dp[0] = 1
for i in range(N-1):
    if dp[i] == 0:
        continue
    for j in S:
        if i+j < N:
            dp[i+j] = (dp[i+j]+dp[i]) % C
# print(dp)
print(dp[-1] % C)

Submission status: Time Limit Exceeded

Solution code:
import sys


class BinaryIndexedTree:
    def __init__(self, n, MOD):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
        self.MOD = MOD

    def sum(self, i):
        s = 0
        while i > 0:
            s = (s + self.tree[i]) % self.MOD
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] = (self.tree[i] + x) % self.MOD
            i += i & -i

    def lower_bound(self, x):
        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_


n, k, *lr = map(int, sys.stdin.buffer.read().split())
lr = list(zip(lr[0::2], lr[1::2]))
MOD = 998244353

bit = BinaryIndexedTree(n + 2, MOD)
bit.add(1, 1)
for i in range(1, n):
    v = bit.sum(i)
    for l, r in lr:
        bit.add(i + l, v)
        bit.add(min(i + r + 1, n + 1), -v)

print((bit.sum(n) - bit.sum(n - 1)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(x) for x in input().split()]
S = set()
for _ in range(k):
    l, r = [int(x) for x in input().split()]
    for i in range(l, r + 1):
        S.add(i)
S = list(sorted(S))
memo = {0: 1}
for i in range(1, n):
    memo[i] = sum(memo[i - s] for s in S if i - s >= 0) % 998244353
print(memo[n - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,k = na()
mod = 998244353
dp = [1] + [0]*(n-1)
hw = []

for i in range(k):
    l,r = na()
    for j in range(l,r+1):
        hw.append(j)

hw.sort()
for i in range(n):
    for p in hw:
        if i-p >= 0:
            dp[i] = (dp[i]+dp[i-p])%mod

print(dp[-1])

Submission status: Time Limit Exceeded

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

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def main():
    INF = 999999999999999999999999
    MOD = 998244353

    n,k = get_nums_l()

    steps = []
    for _ in range(k):
        l,r = get_nums_l()
        for i in range(l, r+1):
            steps.append(i)

    # dp[i] = iマスまで行く方法のパターン数
    dp = [0] * (n+1)

    dp[1] = 1

    for i in range(1, n):
        for step in steps:
            if i+step <= n:
                dp[i+step] = (dp[i+step] + dp[i]) % MOD

    print(dp[n] % MOD)

main()