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())
L = [list(map(int, input().split())) for i in range(K)]

S = []

for i in range(K):
    for j in range(L[i][0], L[i][1] + 1):
        S.append(j)

S.sort()

dp = [0] * N

for x in range(N):
    for y in S:
        if x > y:
            dp[x] = (dp[x] + dp[x - y]) % 998244353

    if x in S:
        dp[x] += 1

print(dp[N - 1])

Submission status: Time Limit Exceeded

Solution code:
from numba import njit, i8
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(reverse=True)
lr = np.array(lr)

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


@njit(cache=True)
def solve(n, lr, dp):
    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
    return dp[-1]


print(solve(n, lr, dp))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
L = []
for _ in range(K):
  a, b = map(int, input().split())
  L.append((a,b))
L.sort()
DP = [0]*N
DP[0]=1
for i in range(1, N):
  for l in L:
    for j in range(l[0], l[1]+1):
      if i>=j: 
        DP[i] += DP[i-j]
        DP[i] %= 998244353
      else:
        break
    else:
      continue
    break
print(DP[-1])

Submission status: Time Limit Exceeded

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

tiles = []
for i in range(K):
    L, R = map(int, input().split())
    tiles = tiles + list(range(L, R + 1))
tiles = sorted(tiles)

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

for i in range(2, N + 1):
    for tile in tiles:
        if i - tile < 0: break
        dp[i] = (dp[i] + dp[i - tile]) % mod

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
s = set()
# lr = []
for _ in range(k):
    l, r = map(int, input().split())
    # lr.append(tuple(map(int, input().split())))
    for tmp in range(l, r+1):
        s.add(tmp)
mod = 998244353

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

for i in range(1, n):
    # for l, r in lr:
    for ss in s:
        if i-ss >= 0:
            dp[i] += dp[i-ss]
    dp[i] %= mod

print(dp[-1]%mod)

Submission status: Time Limit Exceeded

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

import sys


def main():
    mod = 998244353
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def mi():     return map(int, input().split())    

    n, k = mi()
    intervals = [tuple(mi()) for _ in range(k)]
    N = n
    
    # N: 処理する区間の長さ
    LV = (N-1).bit_length()
    N0 = 2**LV
    data = [0]*(2*N0)
    lazy = [0]*(2*N0)

    def gindex(l, r):
        L = (l + N0) >> 1; R = (r + N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1

    # 遅延伝搬処理
    def propagates(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if not v:
                continue
            if lazy[2*i-1] + v >= mod:
                lazy[2*i-1] = (lazy[2*i-1] + v) % mod
            else:
                lazy[2*i-1] += v
            # lazy[2*i-1] = (lazy[2*i-1] + v) % mod
            if lazy[2*i] + v >= mod:
                lazy[2*i] = (lazy[2*i] + v) % mod
            else:
                lazy[2*i] += v
            # lazy[2*i] = (lazy[2*i] + v) % mod 
            if data[2*i-1] + v >= mod:
                data[2*i-1] = (data[2*i-1] + v) % mod
            else:
                data[2*i-1] += v           
            # data[2*i-1] = (data[2*i-1] + v) % mod
            if data[2*i] + v >= mod:
                data[2*i] = (data[2*i] + v) % mod
            else:
                data[2*i] += v                  
            # data[2*i] = (data[2*i] + v) % mod
            lazy[i-1] = 0

    # 区間[l, r)にxを加算
    def update(l, r, x):
        *ids, = gindex(l, r)
        propagates(*ids)
        L = N0 + l; R = N0 + r
        while L < R:
            if R & 1:
                R -= 1
                lazy[R-1] = (lazy[R-1] + x) % mod
                data[R-1] = (data[R-1] + x) % mod
            if L & 1:
                lazy[L-1] = (lazy[L-1] + x) % mod
                data[L-1] = (data[L-1] + x) % mod
                L += 1
            L >>= 1; R >>= 1
    
    # [l] を求める
    def get(l):
        propagates(*gindex(l, l+1))
        return data[N0+l-1]



    update(0, 1, 1)
    for i in range(n):
        p = get(i)
        # print(p)
        for l, r in intervals:
            if i + l < n:
                update(i + l, min(i + r + 1, n), p)
    
    # print(query(n-1, n))
    print(get(n-1))


if __name__ == "__main__":
    main()

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

def f(L, R):
    for k in range(L, R+1):
        if i+k < N:
            dp[i+k] = (dp[i+k] + dp[i]) % mod
        else:
            return False

    return True

for i in range(N):
    for j in range(K):
        L, R = T[j]
        if f(L, R) == False:
            break

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(LR[::2], LR[1::2]):
    for i in range(l, r+1):
        S.add(i)
dp = [0] * (n+1)
dp[1] = 1
for i in range(2, n+1):
    for s in S:
        if i-s >= 0:
            dp[i] += dp[i-s]
            dp[i] %= mod
print(dp[n])

Submission status: Time Limit Exceeded

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


def add(a, b, BIGMOD):
    return (a + b) % BIGMOD


MOD = 998244353
S = []
for i in range(K):
    L, R = map(int, input().split())
    for i in range(R - L + 1):
        S.append(L + i)

S = list(set(S))
S = sorted(S)
#print(S)

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

for i in range(N):
    for s in S:
        if i + s < N:
            DP[i + s] = (DP[i + s] + DP[i]) % MOD
            # print(DP)

print(DP[N - 1] % MOD)

Submission status: Time Limit Exceeded

Solution code:
import collections
def get():
    return [int(x) for x in input().split()]

n, k = get()
s = set()
for _ in range(k):
    start, end = get()
    [s.add(x) for x in range(start, end+1)]
# memo = {}
# def rec(N):
#     if N < 1:
#         return 0
#     elif N == 1:
#         return 1
#     ans = 0
#     for i in s:
#         if i > N:
#             break
#         if N-i not in memo:
#             memo[N-i] = rec(N-i)
#         ans += memo[N-i]
#         ans %= 998244353
#     return ans
# print(rec(n))

table = collections.defaultdict(int)
table[1] = 1
for num in range(1, n+1):
    for i in s:
        if num + i > n:
            break
        table[num+i] += table[num]
        table[num+i] %= 998244353

print(table[n])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np  # noqa

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

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

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

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


print(int(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]
    n,k=map(int,input().split())
    a=set()
    MOD=998244353
    for i in range(k):
      l,r=map(int,input().split())
      for j in range(l-1,r):
        a.add(j)
    dp=[0]*n*2
    dp[0]=1
    for i in range(1,n):
      x=dp[i-1]
      if x==0:
        continue
      else:
        for j in a:
          dp[i+j]+=x
          dp[i+j]%=MOD
    print(dp[n-1])
    
if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
inf=998244353


N,K=map(int,input().split())
SS=[]

for i in range(K):
    s1,s2=map(int,input().split())
    for j in range(s1,s2+1):
        SS.append(j)

SS.sort()

table = [0 for k in range(N-1)] 

for s in SS:
    if s<=N-1:
        table[s-1]+=1
for i in range(N-1):
    if table[i]!=0:
        table[i]%=inf
        for s in SS:
            if i+s<N-1:
                table[i+s]+=table[i]
                #print(table,i,s)
            else:
                break
print(table[-1]%inf)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int, input().split())
alist=[]
for i in range(k):
  a,b=map(int, input().split())
  for i in range(a,b+1):
    alist.append(i)
blist=[0]*(2*n+2)
blist[0]=1
for i in range(n):
  for j in alist:
    blist[i+j]=(blist[i]+blist[i+j])%998244353
print(blist[n-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) * 2, 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] == 0:
        continue
    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:
n, k = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(k)]
MOD = 998244353
cand = []
for l, r in lr:
    for i in range(l, r+1):
        cand.append(i)
cand.sort()
cand = tuple(cand)
# print(cand)
dp = [0] * (n+1)
dp[0] = 1
for i in range(1, n+1):
    tmp = 0
    for num in cand:
        if i - num >= 0:
            tmp += dp[i-num]
            tmp %= MOD
        else:
            dp[i] = (tmp % MOD)
            break
    dp[i] = (tmp % MOD)
print(dp[-2])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
import numpy as np
setrecursionlimit(10 ** 8)

mod = 998244353

def main():
    from builtins import int, map
    N, K = map(int, input().split())
    LR = [tuple(map(int, input().split())) for _ in range(K)]
    # LR = sorted(LR, key = lambda x: x[1], reverse=True)
    # print(N, K, LR)
    
    possible = np.zeros(N + 1, dtype=np.int)
    possible[1] = 1
    for k in range(1, N + 1):
        if possible[k] > 0:
            for (l, r) in LR:
                if k + l > N:
                    continue
                possible[k+l:k+r+1] += possible[k]
                possible[k+l:k+r+1] %= mod
    ans = possible[N] % mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split(" "))
a=[]
d=[]
e=[]
for k in range(K):
    l,r=map(int,input().split(" "))
    d.append(l)
    e.append(r)
d.sort()
e.sort()
for k in range(K):
    a+=list(range(d[k],e[k]+1))
b=[0 for i in range(a[-1]-1)]
b.append(1)
for i in range(N-1):
    x=0
    for j in a:
        x+=b[-j]
    b.append(x%998244353)
print(b[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    numbers = []
    for _ in range(K):
        L, R = map(int, input().split())
        for i in range(L, R + 1):
            numbers.append(i)
    numbers.sort()
    dp = [0] * N
    dp[0] = 1
    p = 998244353
    for i in range(N):
        if dp[i] > 0:
            for j in numbers:
                if i + j < N:
                    dp[i + j] = (dp[i+j] + dp[i]) % p
                else:
                    break
        else:
            continue
    print(dp[N-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, K = map(int, input().split())
d = [0]*(N+1)
l = []
for i in range(K):
    l.append(list(map(int, input().split())))
for i in range(K):
    a, b = l[i][0], l[i][1]
    for j in range(b-a+1):
        d[a+j] = 1
di = []
for i in range(len(d)):
    if d[i]==1:
        di.append(i)

adj = {}
for i in range(N-1):
    lis = [i+1+j for j in di if i+1+j<=N]
    adj[i+1] = lis

ans = [0]*(N+1)
ans[1] = 1
for i in range(N-1):
    #i+1番目
    li = adj[i+1]
    for x in li:
        ans[x] = ans[x] + ans[i+1]
        if(ans[x]>998244353):
            ans[x] = ans[x]%998244353
print (ans[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:

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

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

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

import sys
sys.setrecursionlimit(100000000)

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

    k_set = set()
    for _ in range(k):
        l, r = input_int_map()

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

    k_list = list(k_set)

    result = find_pettern(n - 1, k_list, {})
    result = result % 998244353
    print(result)

def find_pettern(n: int, k_list: [int], memo: {}) -> int:

    if n < 0:
        return 0

    if n == 0:
        return 1

    if n in memo:
        return memo[n]

    count_num = 0
    for k in k_list:
        count_num += find_pettern(n - k, k_list, memo)

    memo[n] = count_num

    return count_num

run()

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n, k = i_map()
    l = []
    ans = [0]*n*2
    for i in range(k):
        a,b = i_map()
        for k in range(a,b+1):
            l.append(k)
            ans[k] += 1
    l.sort()

    for i in range(n):
        if ans[i] > 0:
            for k in l:
                if i+k > n-1:
                    break
                else:
                    ans[i+k] += ans[i]
                    ans[i+k] = ans[i+k] % 998244353
    print(ans[n-1] % 998244353)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k=list(map(int, input("").split()))
s=[]
for i in range(k):
    l,r=list(map(int, input("").split()))
    for j in range(l,r+1):
        s.append(j)
s=list(set(s))
o=[0]*(n+1)
o[1]=1
for i in range(2,n+1):
    for j in s:
        if i-j > 0 :
            o[i]+=o[i-j] 
print(o[n]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
t = sys.stdin.readlines()
N,K = map(int, t[0].split())
S = []
for i in range(K):
    L,R = map(int, t[1+i].split())
    S += [ j for j in range(L,R+1)]

S = sorted(S)

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


for j in range(1,N):
    for s in S:
        if j + s > N or step[j] == 0:
            continue
        step[j+s] += (step[j]%998244353)
        step[j+s] %= 998244353
    
print(step[N])

Submission status: Time Limit Exceeded

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

L = [0 for _ in range(N)]
R = [0 for _ in range(N)]

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

S = []
for i in range(K):
    for s in range(L[i],R[i]+1):
        S.append(s)

A = [0 for _ in range(N)]

A[0] = 1

for i in range(1,N):
    for s in S:
        if s<=i:
            A[i] += A[i-s] % 998244353
    A[i] = A[i] % 998244353

print(A[N-1])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
MOD = 998244353


def solve():
    N,K = map(int,input().split())
    step = [tuple(map(int,inp.split())) for inp in stdin.read().splitlines()]
    # @lru_cache(None)
    # def dp(n):
    #     if n == 1:
    #         return 1
    #     res = 0
    #     for a,b in step:
    #         if n <= a:
    #             continue
    #         for i in range(a,b+1):
    #             if n > i:
    #                 res += dp(n-i)
    #     return res % MOD
    #
    # print(dp(N))

    dp = [0] * (N+1)
    dp[1] = 1
    for i in range(2,N+1):
        for a,b in step:
            if i <= a:
                continue
            for j in range(a,b+1):
                if i > j:
                    dp[i] += dp[i-j]
        dp[i] %= MOD
    print(dp[N])



if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)

N,K,*f = map(int, open(0).read().split())
LR = [f[i*2:i*2+2] for i in range(K)]
LR.sort()
S = []
for L,R in LR:
    for i in range(L,R+1):
        S.append(i)
mem = [False] * (N+1)
mem[1] = 1

def f(n):
    if mem[n]:
        return mem[n]
    else:
        res = 0
        for x in S:
            if n - x > 0:
                res = (res+f(n-x)) % 998244353
        mem[n] = res
        return res

print(f(N))

Submission status: Time Limit Exceeded

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

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

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

L.sort()

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

for i in range(2,N+1):
    count = 0
    for l,r in L:
        if l >= i:
            break
        elif l < i and i - r > 1:
            count += dp[i-l] - dp[i-r-1]
        else:
            count += dp[i-l]
    dp[i] = dp[i-1] + count

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

Submission status: Time Limit Exceeded

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
#import itertools
#import heapq
#from collections import deque
#d = deque()

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    mod=998244353
    dp=[0]*(2*(10**5)+10)
    dp[0]=1
    n,k=map(int, readline().rstrip().split())
    #s=set()
    #lr=[0]*(2*(10**5)+10)
    ll=[0]*(2*(10**5)+10)
    rr=[0]*(2*(10**5)+10)
    for i in range(k):
        ll[i],rr[i]=map(int, readline().rstrip().split())
    for i in range(n-1):
        if dp[i] == 0:
            continue
        for j in range(k):
            for x in range(ll[j],rr[j]+1):
                if (i+x) > n:
                    break
                dp[i+x] += dp[i]
                dp[i+x]%=mod
    print(dp[n-1])
    #for i in range(n):
    #    if i > 0:
    #        lr[i]+=lr[i-1]
    #    if lr[i] > 0:
    #        s.add(i)

    #arr=list(map(int, readline().rstrip().split()))
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Time Limit Exceeded

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

mod = 998244353
i = 1
dp = [0] * (n+1)
dp[i] = 1
for i in range(n+1):
    if dp[i] == 0:
        continue
    for lr in s:
        for d in lr:
            if i+d <= n:
                dp[i+d] = (dp[i+d] + dp[i]) % mod

print(dp[n] % mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, K = map(int, input().split())
MOD = 998244353
dp = [0 for _ in range(N)]
dp[0] = 1

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

for i in range(N):
    tmp = dp[i]
    for k in range(K):
        if i+L[k] < N:
            for d in range(L[k], min(R[k]+1, N-i)):
                dp[i+d] += tmp
                dp[i+d] %= MOD

ans = dp[N-1] % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
s=[]
ans=0
dp=[0,1]
for i in range(k):
  a,b=map(int,input().split())
  if b==n:
    s.extend(list(range(a,b)))
  else:
    s.extend(list(range(a,b+1)))
s.sort()
for i in range(2,n+1):
  tmp=0
  for j in s:
    if i-j>=1:
      tmp+=dp[i-j]
    else:
      break
  dp.append(tmp)
print(dp[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353

def eratosthenes(n, start, l, r, array):
    # print(array, n, l, r)
    for i in range(l, r+1):
        if i+start > n:
            break
        array[i+start] = (array[start] + array[i+start]) % mod


def resolve():

    n, k = map(int, input().split())
    array = [0] * (n+1)
    array[1] = 1

    lr = []
    for i in range(k):
        l,r = map(int, input().split())
        lr.append((l,r))
    lr.sort(reverse=True)
    for start in range(1, n):
        for l,r in lr:
            eratosthenes(n, start, l, r, array)


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

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


#for i in range(k):
#    a,b = map(int,input().split())
#    for i in range(a,b+1):
#        s += [i]

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

#print(s)
#s = list(set(s))
len_s = len(s)

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

for i in range(2,n+1):
    for j in range(k):
        ans[i] += sum(ans[max(0,i-s[j][1]):max(0,i-s[j][0]+1)])
        #print(i,sum(ans[max(0,i-s[j][0]):max(0,i-s[j][1]+1)]),max(0,i-s[j][0]),max(0,i-s[j][1]+1))

#print(ans)

print(ans[n]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
P=998244353
N,K=map(int,input().split())
LR=[]
for _ in range(K):
  l,r=map(int,input().split())
  LR+=range(l,r+1)
LR=list(set(LR))
LR=np.array(LR)
c=[0]*N
c[0]=1
for k in range(N):
  S=list(LR[LR<=k])
  while len(S):
    c[k]+=c[k-S[-1]]%P
    S.pop()
print(c[-1]%P)

Submission status: Time Limit Exceeded

Solution code:
#再帰の限度を拡張
import sys
sys.setrecursionlimit(1000000)
#再帰メモ化
from functools import lru_cache

MOD_BY = 998244353 

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

LR_list = list()

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

@lru_cache(maxsize=10000000000)
def dp_search(now):
    if now == 1:
        return 1
    elif now <= 0:
        return 0
    else:
        ans = 0
        for L,R in LR_list:
            for i in range(L,min(R+1,now+1)):
                ans += dp_search(now-i)%MOD_BY
        
        return ans%MOD_BY

print(dp_search(N)%MOD_BY)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
span = []
mod = 998244353
for i in range(k):
    span.append(list(map(int, input().split())))
dp = [0 for i in range(n+1)]
acc = [0 for i in range(n + 1)]
dp[0] = 1
for i in range(n+1):
    acc[i] += acc[i-1]
    dp[i] += acc[i]
    for j in range(k):
        l, r = span[j]
        if l + i < n + 1:
            acc[l + i] += dp[i]
        if r + 1 + i < n + 1:
            acc[r+1 + i] -= dp[i]
    dp[i] %= mod
print(dp[-2] % mod)

Submission status: Time Limit Exceeded

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

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    # 標準入力を取得
    N, K = list(map(int, input().split()))
    L, R = [], []
    for k in range(K):
        L_k, R_k = list(map(int, input().split()))
        L.append(L_k)
        R.append(R_k)

    return N, K, L, R


def main(N: int, K: int, L: list, R: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): マスの数(2 <= N <= 2 * 10**5)
        K (int): 区関数(1 <= K <= min(K, N))
        L (list): 区間の下限(1 <= L_i <= R_i <= N)
        R (list): 区間の上限(1 <= L_i <= R_i <= N)
    """
    # 求解処理
    S = set()
    for k in range(K):
        for s in range(L[k], R[k] + 1):
            S.add(s)
    S = sorted(S)

    mod = 998244353
    m = {i: 0 if i != 1 else 1 for i in range(1, N + 1)}
    for i in range(1, N):
        if m[i] == 0:
            continue
        m[i] %= mod
        for s in S:
            if i + s <= N:
                m[i + s] += m[i]
            else:
                break

    ans = m[N] % mod

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, K, L, R = get_input()

    # メイン処理
    main(N, K, L, R)

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
            else:
                break

print(dp[N-1])

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)
min_S = min(S)
memo = [-1 for _ in range(N)]

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

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