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())
INF = 998244353
X = [list(map(int,input().split())) for _ in range(k)]
d = []
for i in range(k):
  for j in range(X[i][0],X[i][1]+1):
    d.append(j)
p = [0]*n
p[0] = 1
for i in range(1,n):
  for x in d:
    if i-x>= 0:
      p[i] += p[i-x]
print(p[-1]%INF)

Submission status: Time Limit Exceeded

Solution code:
# ####################################################################
# import io
# import sys
# _INPUT = """\
# 7 1
# 1 3
# """
# sys.stdin = io.StringIO(_INPUT)
####################################################################
import sys
def _p(*_a):
  #return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
####################################################################
def _pa(_aa):
  #return
  for _a in _aa: _p(_a)
####################################################################
N, K = map(int, input().split())

MOD = 998244353
ans = 0

M = [0] * (N + 1)

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

A.sort()

# _p(N,K,A)

for n in range(2, N+1):
  # print(n)
  if M[n] > 0: continue

  for a in A:
    p = n - a
    if p == 1: M[n] += 1
    if p <= 1: break
    M[n] += M[p] % MOD
    M[n] = M[n] % MOD

# _p(M)
print(M[N] % MOD)

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


n, k = LI()
s = set()
for i in range(k):
    l, r = LI()
    s |= set(range(l, r + 1))

# a = len(s)
dp = [0] * (n + 1)
dp[1] = 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(250000)

dp = []
syugo = set()


def rec(i):
    global syugo
    global dp

    if i < 0 :
        return 0

    if i == 0 :
        return 1

    for j in syugo:
        dp[i] = dp[i] + rec(i-j)

    return dp[i]
def main():
    global syugo
    global dp
    n, k = map(int, input().split())

    for i in range(k):
        s, e = map(int, input().split())
        for j in range(s, e+1):
            syugo.add(j)

    dp = [0]*n

    for i in range(n):
        for j in syugo:
            if i - j ==0 :
                dp[i] = dp[i] + 1
            elif i - j  > 0:
                dp[i] = dp[i] + dp[i-j]
    ##    rec(n-1)

    print(dp[n-1]%998244353)
main()



#
# while True:
#     pair_str = input().split()
#     pair_int = [int(s) for s in pair_str]
#     if pair_int[0] == 0 and pair_int[1] == 0 :
#         break
#     else:
#         input_list.append(pair_int)


# if b > c * 2 :
    #     b_price = c
    #
    # input_array_list = []
    #
    # while True:
    #     input_array = input().split()
    #     if input_array[0] == "0" and input_array[1] == "0":
    #         break
    #     else:
    #         input_array_list.append(input_array)
    #
    # for item in input_array_list:
    #     n = int(item[0])
    #     k_sum = int(item[1])
    #
    #     count = 0
    #     for i in range(1,n + 1- 2):
    #         for j in range(i+1, n + 1 - 1):
    #             for k in range (j+1, n+ 1):
    #                 if i + j + k == k_sum :
    #                     count = count + 1
    #     print(count)

    #
    # for item in input_array_list:
    #     if item[1] == "+":
    #         print(str(int(item[0])+int(item[2])))
    #     elif item[1] =="-":
    #         print(str(int(item[0])-int(item[2])))
    #     elif item[1] == "/":
    #         print(str(int(item[0])//int(item[2])))
    #     elif item[1] == "*":
    #         print(str(int(item[0])*int(item[2])))
    #

# import sympy as sp

# input_list = []
# a,b,c = map(int, input().split())
# divisors = sp.divisors(c)
#
# count = 0
#
# for divisor in divisors:
#     if a <= divisor and divisor <= b:
#         count = count + 1
# print(count)
#
# while True:
#     pair_str = input().split()
#     pair_int = [int(s) for s in pair_str]
#     if pair_int[0] == 0 and pair_int[1] == 0 :
#         break
#     else:
#         input_list.append(pair_int)
#
# for pair_int in input_list:
#     if pair_int[0] <= pair_int[1]:
#         print("{} {}".format(pair_int[0], pair_int[1]))
#     else:
#         print("{} {}".format(pair_int[1], pair_int[0]))

#for i in range(10000):
#    print("Hello World")
#a = input().split()
#a_int = [int(s) for s in a]
#a_sorted = sorted(a_int)
#print(' '.join(map(str, a_sorted)))

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
        for s in S:
            if i + s <= N:
                m[i + s] += m[i] % mod
            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
input = sys.stdin.readline

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

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

S = []

for left, right in L:
    S.extend(range(left, right+1))

S = sorted(list(set(S)))

n_list = [0] * N
n_list[0] = 1

for idx, value in enumerate(n_list):
    if value == 0:
        continue
    if S[0] + idx >= N:
        break
    for s in S:
        next_idx = s + idx
        if next_idx >= N:
            break
        n_list[next_idx] += value

print(n_list[-1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod = 998244353
    n,k = map(int,input().split())
    rngs = []
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(k):
        rngs.append(list(map(int,input().split())))
    for i in range(1,n+1):
        for rng in rngs:
            for j in range(rng[0],rng[1]+1):
                try:
                    dp[i+j] += dp[i]
                except IndexError:
                    continue
    print(dp[n]%mod)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
N,K = map(int,input().split())
move = []
for _ in range(K):
    x,y = map(int,input().split())
    for i in range(x,y+1):
        move.append(i)
move.sort()
move = set(move)
memo = [0]*(N+1)
memo[1] = 1
for i in range(2,N+1):
    for j in move:
        if 0<i-j:
            memo[i] += memo[i-j]
        else:
            break
    memo[i] = memo[i]%mod
print(memo[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
cc = [list(map(int,input().split())) for i in range(K)]
masu = [1]+[0]*(N-1)
ccc = []
for i,j in cc:
  for k in range(i,j+1):
    ccc.append(k)
ccc.sort()
for i in range(N):
  for j in ccc:
    if i-j>=0:
      masu[i]+=masu[i-j]
    else:
      break
print(masu[-1]%998244353)

Submission status: Time Limit Exceeded

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

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

d = [0] * N


def func(pos):
    for a in area:
        for i in range(a[0], a[1]+1):
            if pos - i > -1:
                d[pos-i] += d[pos] % 998244353
            else:
                break


d[N-1] = 1
for i in range(N-1, -1, -1):
    if d[i] > 0:
        func(i)

print(d[0] % 998244353)

Submission status: Time Limit Exceeded

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    # mod = 1000000007                # 10^9+7
    mod = 998244353
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
    

    n, k = mi()
    intervals = [lmi() for _ in range(k)]
    N = 2 * n + 1
    
    # N: 処理する区間の長さ
    INF = 2**31-1

    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
            lazy[2*i-1] += v
            lazy[2*i] += v
            #
            lazy[2*i-1] %= mod
            lazy[2*i] %= mod
            data[2*i-1] += v
            data[2*i] += v
            #
            data[2*i-1] %= mod
            data[2*i] %= 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] += x
                data[R-1] += x
                # 
                lazy[R-1] %= mod
                data[R-1] %= mod
            if L & 1:
                lazy[L-1] += x
                data[L-1] += x
                # 
                lazy[L-1] %= mod
                data[L-1] %= mod
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            data[i-1] = min(data[2*i-1], data[2*i])

    # 区間[l, r)内の最小値を求める
    def query(l, r):
        propagates(*gindex(l, r))
        L = N0 + l; R = N0 + r

        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, data[R-1])
            if L & 1:
                s = min(s, data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

S = []
for l,r in LR:
    for _ in range(l,r+1):
        S.append(_)
S = list(set(S))

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

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:
        for s in SS:
            if i+s<N-1:
                table[i+s]+=table[i]
                table[i+s]%=inf
                #print(table,i,s)
            else:
                break
print(table[-1]%inf)

Submission status: Time Limit Exceeded

Solution code:
root=[]
n,k = map(int,input().split())
for i in range(k):
    x,y = map(int,input().split())
    root.append([x,y])

toori=[0]*(2*10**5)+[0]*n+[0]*(2*10**5)
toori[2*10**5]=1
cum=[0]*k
for a,i in enumerate (root):
    s=0
    for j in range (i[0],i[1]+1):
        s+=toori[2*10**5+1-j]
    cum[a]=s
toori[2*10**5+1]+=sum(cum)


for now in range(2,n):#nowが今の場所
    for a,i in enumerate (root):
        cum[a]=cum[a]+toori[2*10**5+now-i[0]] - toori[2*10**5+now-1-i[1]]
    toori[2*10**5+now]+=sum(cum)
    


print(toori[2*10**5+n-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
figs = set()
for _ in range(K):
  a,b = map(int,input().split())
  for i in range(a,b+1):
    figs.add(i)
DP = [0]*N
DP[0] = 1
for i in range(N):
  for item in figs:
    if i - item >= 0:
      DP[i] = DP[i - item]+DP[i]
print(DP[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
lrl = []
for _ in range(k):
    lrl.append(list(map(int,input().split())))

N = 2 * n
# N: 処理する区間の長さ

data0 = [0]*(N+1)
data1 = [0]*(N+1)

mod = 998244353
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        x %= 998244353
        data[k] += x
        data[k] %= 998244353
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def _get(data, k):
    s = 0
    while k:
        s += data[k]
        s %= 998244353
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

add(1, 2, 1)
for i in range(n):
    now = query(i+1, i+2) 
    for l, r in lrl:
        add(l+i+1, r+i+2, now % 998244353)

print(query(n, n+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)
M = [0]*(N+1)
M[1]=1
for i in range(1,N+1):
    for LS in S:
        if LS <= i-1:
            M[i] += M[i-LS]
print(M[N] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


class Bit:

    def __init__(self, a):
        if hasattr(a, "__iter__"):
            le = len(a)
            self.n = 1 << le.bit_length()
            self.values = values = [0] * (self.n + 1)
            values[1:le + 1] = a[:]
            for i in range(1, self.n):
                values[i + (i & -i)] += values[i]
        elif isinstance(a, int):
            self.n = 1 << a.bit_length()
            self.values = [0] * (self.n + 1)
        else:
            raise TypeError

    # A[i] += val
    def add(self, i, val):
        n, values = self.n, self.values
        while i <= n:
            values[i] += val
            i += i & -i

    # A[1, i]の累積和
    def sum(self, i):
        values = self.values
        res = 0
        while i > 0:
            res += values[i]
            i -= i & -i
        return res

    # A[1, i]の累積和 が v 以上になる最小の i
    def bisect_left(self, v):
        n, values = self.n, self.values
        if v > values[n]:
            return None
        i, step = 0, n >> 1
        while step:
            if values[i + step] < v:
                i += step
                v -= values[i]
            step >>= 1
        return i + 1


def main():

    N, K = in_nn()
    LR = []
    for i in range(K):
        l, r = in_nn()
        LR.append((l, r))

    init_dp = [0] * N
    init_dp[0] = 1
    init_dp[1] = -1
    bit = Bit(init_dp)

    for i in range(1, N + 1):
        for k in range(K):
            l, r = LR[k]
            now = bit.sum(i)
            bit.add(i + l, now)
            bit.add(i + r + 1, -now)

    print(bit.sum(N) % 998244353)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# region header
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
import copy
# @lru_cache(maxsize=None)
# sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
# endregion
# region input function


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


# endregion


class RAQ():
    def __init__(self, N, identity):
        """
        Parameters
        ----------
        N: int
            the number of nodes

        identity: int
            queries' identity element
            query = max -> -inf
            query = min -> inf
        """
        self.N = N
        self.depth = (N - 1).bit_length()
        self.N0 = 2 ** self.depth
        self.identity = identity
        self.init_val = 0
        self.data = [self.init_val] * (2 * self.N0)
        self.lazy = [self.init_val] * (2 * self.N0)

    def init_list(self, list):
        """init list directly

        Args:
            list (list(int)): init list
        """
        for i in range(self.N):
            self.update(i, i + 1, list[i])

    def _segfunc(self, left, right):
        res = sum([left, right])
        return res

    def _generate_index(self, l, r):
        """
        Parameters
        ----------
        l,r: int
            target range [l,r) (0-index)

        Return
        ----------
        res: iter(int)
            actually update index
        """
        L = l + self.N0
        R = r + self.N0
        lm = (L // (L & -L)) >> 1  # update target
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1
            R >>= 1
        while L:
            yield L
            L >>= 1

    def _propagates(self, *ids):
        """
        Parameters
        ----------
        ids: iter(int)
            update target
        """
        for i in reversed(ids):
            v = self.lazy[i - 1]
            if not v:
                continue
            self.lazy[2 * i - 1] += v
            self.lazy[2 * i] += v
            self.data[2 * i - 1] += v
            self.data[2 * i] += v
            self.lazy[i - 1] = self.init_val

    def update(self, l, r, x):
        """
        Parameters
        ----------
        l,r: int
            target range [l,r) (0-index)
        x: int
            add value
        """
        L = self.N0 + l
        R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R - 1] += x
                self.data[R - 1] += x
            if L & 1:
                self.lazy[L - 1] += x
                self.data[L - 1] += x
                L += 1
            L >>= 1
            R >>= 1
        for i in self._generate_index(l, r):
            self.data[i - 1] = self._segfunc(self.data[2 * i - 1], self.data[2 * i]) + self.lazy[i - 1]

    def query(self, l, r):
        """
        Parameters
        ----------
        l,r: int
            target range [l,r) (0-index)

        Return
        ----------
        res: int
        """
        self._propagates(*self._generate_index(l, r))
        L = self.N0 + l
        R = self.N0 + r

        s = self.identity
        while L < R:
            if R & 1:
                R -= 1
                s = self._segfunc(s, self.data[R - 1])
            if L & 1:
                s = self._segfunc(s, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def get_list(self):
        """get all list

        Returns:
            list(int): origin list
        """
        for i in range(self.N):
            self._propagates(*self._generate_index(i, i + 1))
        return self.data[self.N0 - 1:self.N0 + self.N - 1]


n, k = inpl()
query = []
for _ in range(k):
    l, r = inpl()
    query.append([l, r])
query.sort()
st = RAQ(n, 0)
st.update(n - 1, n, 1)
for i in range(n, 0, -1):
    for l, r in query:
        if i-l<=0:
            break
        st.update(max(0, i - r - 1), i - l, st.query(i - 1, i))
print(st.query(0, 1) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)
n, k = map(int,input().split())
num = [-1]*(n+1)
num[0] = 0
num[1] = 1
lis = []
MOD = 998244353
for i in range(k):
    l, r = map(int,input().split())
    lis += list(range(l,r+1))
def numpat(n):
    if n<0:
        return 0
    elif num[n]!=-1:
        return num[n]
    tmp = 0
    for i in lis:
        tmp += numpat(n-i)
    num[n]=tmp%MOD
    return num[n]
print(numpat(n))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
l_r = [ list(map(int, input().split())) for _ in range(k)  ]
d = [0] *n
d[0] = 1
for i in range(1, n):
    c = 0
    for l,r in l_r:
        for s in range(l, r+1):
            if s <= i:
                if d[i-s] > 0:
                    c += d[i-s]
            else:
                break
    d[i] = c%998244353
print(d[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
mmm=998244353
def countWays(arr, m, N): 

	count = [0 for i in range(N + 1)] 
	
	# base case 
	count[0] = 1
	
	for i in range(1, N + 1): 
		for j in range(m): 

			if (i >= arr[j]): 
				count[i] =(count[i]+ count[i - arr[j]] )%mmm
	
	return count[N] 
	
a,b=map(int,input().split())
s=set()
arr=[]
for i in range(b):
    x,y=map(int,input().split())
    for j in range(x,y+1):
        arr.append(j)
            
    # arr = [1, 5, 6] 
# print(arr)
m = len(arr) 
N = a-1
print(countWays(arr, m, N)) 
			
# This code is contributed by Anant Agarwal.

Submission status: Time Limit Exceeded

Solution code:
#D
N,K=map(int,input().split())
p=998244353
L=[0]*K
R=[0]*K
C=[0]*K
allnum=set(i for i in range(1,N+1))
mov=set()
for i in range(K):
    L[i],R[i] = map(int,input().split())
    for i in range(L[i],R[i]+1):
        mov.add(i)
    #C[i] = [L[i],R[i]]
#C.sort()
mov2=allnum-mov

if len(mov)<len(mov2):
    dp = [0]*(N+1)
    dp[1]=1
    for i in range(2,N+1):
        for m in mov:
            if i-m>=1:
                dp[i] += dp[i-m]
                dp[i] %= p
else:
    dp = [0]*(N+1)
    dp[1]=1
    summ=0
    for i in range(2,N+1):
        summ += dp[i-1]
        summ %=p
        cant=0
        for m in mov2:
            if i-m>=1:
                cant += dp[i-m]
                cant %= p
        dp[i]=summ-cant
        #print(dp[i],summ)
    
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

Z = 998244353


def input():
    return sys.stdin.readline().rstrip('\n')


def calc(N, K, LR):
    c = []
    for (l, r) in LR:
        for i in range(l, r + 1):
            c += [i]
    d = [0] * N
    d[0] = 1
    for i in range(N):
        if d[i] == 0:
            continue
        for e in c:
            if i + e < N:
                d[i + e] = (d[i + e] + d[i]) % Z
    return d[N - 1]


(N, K) = tuple([int(s) for s in input().split()])
LR = [tuple([int(s) for s in input().split()]) for _ in range(K)]
print(calc(N, K, LR))

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


LR = [list(map(int,input().split())) for _ in range(K)]
L = [0]*N
for i in range(N):
    if i == 0:
        L[0] = 1
    else:#i>=1のとき
        for j in range(K):#それぞれの区間に対して
            if i - LR[j][0] >= 0:
                L[i] +=sum(L[max(i - LR[j][1],0) : i - LR[j][0] + 1])
               
print(L[N-1]%998244353)

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

dp=[0]*(n+1)
dp[1]=1
for i in range(2,n+1):
  for ss in s:
    dp[i]+=dp[i-ss]
  dp[i] %= 998244353

print(dp[n])