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:
# -*- 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 = []
    for k in range(K):
        for s in range(L[k], R[k] + 1):
            S.append(s)
    S = sorted(S)

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

    ans = m[N] % 998244353

    # 結果出力
    print(ans)


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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import math  # gcdもあるよ
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
import bisect #二部探索
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化
INF = 10**9 + 7
mod = 998244353

def main():
    n, k = list(map(int,input().split()))
    #data = [input().split() for _ in range(n)]
    #差集合Sをつくる
    S = []
    for _ in range(k):
        s = list(map(int,input().split()))
        #print(s)
        s_ = [i for i in range(s[0], s[1]+1)]
        #print(s_)
        S = list(set(S) | set(s_)) #和集合
    #print(S)

    square = [0 for _ in range(n+10)]
    square[0] = 1
    #print(square)
    for i in range(n):
        for j in S:
            if not i + j > n:
                square[i+j] += square[i]
                square[i+j] %= mod
            #print(square)
    print(square[n-1])
    return 0

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split(" ")))
S = []
for _ in range(K):
    a, b = list(map(int, input().split(" ")))
    S.extend(range(a, b+1))


combinations = [0] * (N + 1)
combinations[1] = 1
S.sort()
for i in range(1, (N + 1 - S[0])):
    if combinations[i] == 0:
        continue
    for j in S:
        idx = i + j
        if idx < N + 1:
            combinations[idx] += combinations[i]
            if combinations[idx] >= 998244353:
                combinations[idx] = combinations[idx] % 998244353
        else:
            break
print(combinations[-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):
    for l, r in s_list:
        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())
table=[i for i in range(N+1)]
arr=[]
for i in range(K):
    a,b=map(int,input().split())
    arr+=table[a:b+1]
arr=set(arr)

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

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

Submission status: Time Limit Exceeded

Solution code:
n = list(map(int, input().split()))
masu = [0]*n[0]
masu[0] = 1
l = [0]*n[1]
r = [0]*n[1]
for i in range(n[1]):
    kukan = list(map(int, input().split()))
    l[i] = kukan[0]
    r[i] = kukan[1]
l.sort()
r.sort()
for i in range(n[0]):
    for j in range(n[1]):
        for k in range(l[j],r[j]+1):
            if i+k < n[0]:
                masu[i+k]+=masu[i]
            else:
                break
print(masu[n[0]-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

MOD = 998244353

D = deque([1], N)
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      count += sum(D[i-k] for k in range(l, min(i, r) + 1))
  D.append(count % MOD)
print(D[-1])

Submission status: Time Limit Exceeded

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

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

S.sort()

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

print(dp[-1] % 998244353)

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 += self.tree[i]
            i -= i & -i
        return s % self.MOD

    def add(self, i, x):
        mod = self.MOD
        while i <= self.size:
            self.tree[i] = (self.tree[i] + x) % 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 = 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]


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:
m = 998244353
N, K = map(int, input().split())

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

a = [0] * (N + 1)

a[1] = 1
for i in range(2, N + 1):
    for j in jumps:
        if i > j:
            a[i] = (a[i] + a[i - j]) % m
print(a[N])

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,k=map(int,input().split())
can=[]
for i in range(k):
    l,r=map(int,input().split())
    for j in range(l,r+1):
        can.append(j)
table=[0]*n
table[0]=1
ka=[0]*(n+1)
ka[0]=1
que=[0]
heapq.heapify(que)
can.sort()
while que:
    now=heapq.heappop(que)
    ka[now]=0
    for j in can:
        if now+j>=n:
            break
        table[now+j]=(table[now+j]+table[now])%998244353
        if ka[now+j]==0:
            heapq.heappush(que,now+j)
            ka[now+j]=1
print(table[-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)
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        data[k] += x
        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]
        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)

print(query(n, n+1) % 998244353)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

print(dp[n]%998244353)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
N, K = map(int, input().split())
L = []
R = []
for k in range(K):
    l, r = map(int, input().split())
    L += [l]
    R += [r]
# memo = [[0 for i in range(N+2)] for k in range(K)]
memo = [0 for i in range(N+2)]
memo[1] = 1
memo[2] = -1
cusum = 0
for i in range(1, N+1):
    cusum += memo[i]
    # print(cusum)
    for k in range(K):
        l, r = L[k], R[k]
        # for j in range(i+l, min(i+r+1, N+1)):
        #     memo[j] += memo[i]
        memo[min(i+l, N+1)] += cusum
        memo[min(i+r+1, N+1)] -= cusum
    # print(memo)
# for i in range(1, N+1):
#     for k in range(K):
#         memo[k][i+1] += memo[k][i]
print(cusum % MOD)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

S = []
r = 998244353
for i in range(K):
    L,R = list(map(int,input().split()))
    for k in range(L,R+1):
        S.append(k)
        
        
dp = [0]*(N+1)
dp[1] = 1

for i in range(2,N+1):
    # print("i=",i)
    for k in S:
        if k<i:
            dp[i] += dp[i-k]
    dp[i] %= r
# print(S)
# print(dp)
print(dp[-1])

Submission status: Time Limit Exceeded

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

MOD = 998244353
n, k = map(int, input().split())
s = set()
for i in range(k):
    a, b = map(int, input().split())
    s.update(range(a, b + 1))
s = sorted(list(s))

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

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
xy = [map(int, input().split()) for _ in range(k)]
x, y = [list(i) for i in zip(*xy)]

slist=[]
for j in range(k):
    jlist=list(range(x[j],y[j]+1))
    slist.extend(jlist)

alist=[1]
blist=[0]*(n-1)
alist.extend(blist)
for r in range(n):
    for sa in slist:
        if r+sa<=n-1:
            alist[r+sa]+=alist[r]

ans=alist[n-1]
answer=ans%998244353
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n,k = map(int,input().split())
l = []
for num in range(k):
	l += [list(map(int,input().split()))]
    
s = []
for num in range(k):
  ch = 0
  if l[num][0] == l[num][1]:
    s += [l[num][0]]
  else:
    s += [l[num][0],l[num][1]]
    
count = 0

for num in range(n):
  test = list(itertools.product(s, repeat=num+1))
  for i in range(len(test)):
    
    if n-1 == sum(test[i]):
      count += 1
      #print(test[i],sum(test[i]))
    #elif n < sum(test[i]):
      #break   
print(count%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())
    S += [ j for j in range(L,R+1)]
S = set(S)

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

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

Submission status: Time Limit Exceeded

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

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))
def cum_sum(lst):
    cums = [0] * (len(lst)+1)
    cums[1] = lst[0]
    for i in range(2,len(lst)+1):
        cums[i] = cums[i-1] + lst[i-1]
    return cums
import bisect
n,k = mp()
mod = 998244353
s = [0]*(n+3)
for i in range(k):
    a,b = mp()
    s[a] += 1
    s[b+1] -= 1
s = cum_sum(s)[1:]
se = set()
for i in range(n+1):
    if s[i] > 0:
        se.add(i)
se = list(se)
dp = [0]*(n+1)
dp[1] = 1
for i in range(2, n+1):
    m = bisect.bisect_right(se, i)
    for j in range(m):
        if i - se[j] > 0:
            dp[i] += dp[i-se[j]]
            dp[i] %= mod
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

mod = 998244353

N, K = map(int, input().split())
LR = []
for _ in range(K):
    l, r = map(int, input().split())
    LR.append((l, r))

dp = np.array([0] * (N+1))

stop = False
while not stop:
    cnt = 0
    for i, (l, r) in enumerate(LR):
        l += cnt
        r += cnt
        if l > N:
            if i == 0:
                stop = True
            break
        else:
            dp[l:min(N+1, r+1)] += 1
    cnt += 1

print(dp[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8

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

T = [0] * (N+1)

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

S = []

for i in range(N+1):
    if T[i] == 1:
        S.append(i)

dp = [0] * N

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

print("{}".format(dp[N-1]))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
S=[]
NUM=998244353
for _ in range(K):
    l,r=map(int,input().split())
    for i in range(l,r+1):
        S.append(i)
S.sort()
dp=[0]*(N+1)
dp[1]=1
for i in range(2,N+1):
    for s in S:
        if i-s<=0: break
        dp[i]+=dp[i-s]
        dp[i]%=NUM

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
table=[i for i in range(N+1)]
arr=[]
for i in range(K):
    a,b=map(int,input().split())
    arr+=table[a:b+1]
arr=set(arr)

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


for i in range(N):
    for j in range(N):
        for k in arr:
            if dp[i][j]!=0 and j+k<=N-1:
                dp[i+1][j+k]+=dp[i][j]

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

print(ans%998244353)

Submission status: Time Limit Exceeded

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

nums = []

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


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

print(dp[-1]%MOD)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
mod=998244353
S=set()
for _ in range(k):
  l,r=map(int,input().split())
  for i in range(l,r+1):
    S.add(i)
dp=[0 for _ in range(n+1)]
for i in S:
  dp[i]=1

for i in range(1,n+1):
  for j in S:
    if i-j<1:
        continue
    dp[i]+=dp[i-j]
print(dp[n-1]%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

n,k = map(int, input().split())
LR = [list(map(int, input().split())) for i in range(k)]
LR.sort()
S = []
for i in range(k):
  a = LR[i][1] - LR[i][0]
  b = LR[i][0]
  for j in range(a+1):
    S.append(b)
    b += 1
    
DP = [0] * n
DP[0] = 1  # 0が1番目
for i in range(n):
  for j in S:
    if i+j > n-1:
      continue #list外となる
    else:
      DP[i+j] = (DP[i+j] + DP[i]) % 998244353

ans = DP[n-1] % 998244353

#print(LR)
#print(S)
#print(DP)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():

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

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

    kukan = []
    for w in lr:
        for i in range(w[0], w[1] + 1):
            kukan.append(i)

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

    dp[1] = 1
    for i in range(2, n + 1):
        for j in kukan:
            if i - j >= 0:
                dp[i] += dp[i - j] % mod

    print(dp[n] % mod)


main()

Submission status: Time Limit Exceeded

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

MOD = 998244353

PAT = []
for _ in range(K):
  l,r = map(int, input().split())
  PAT.append((l,r))
  
IMOS = [0] * (2*N+10)
IMOS[1] = 1
for i in range(0,N):
  for l,r in PAT:
    IMOS[i+l] += IMOS[i]
    IMOS[i+r+1] -= IMOS[i]
  #print(i, IMOS)
  IMOS[i+1] += IMOS[i]
  IMOS[i+1] % MOD
  
print((IMOS[N] - IMOS[N-1]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
lr = []
for _ in range(k):
    l, r = map(int, input().split())
    for i in range(l, r + 1):
        lr.append(i)
lr = set(lr)
lr = sorted(lr)
dp = [0] * (n + 1)
dp[n] = 1
for i in range(n, 1, -1):
    for step in lr:
        if step <= i:
            dp[i - step] += dp[i] % 998244353
            dp[i - step] %= 998244353
        else:
            break
print(dp[1])

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():

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

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

    kukan = []
    for w in lr:
        for i in range(w[0], w[1] + 1):
            kukan.append(i)

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

    dp[1] = 1
    for i in range(2, n + 1):
        for j in kukan:
            if i - j >= 0:
                dp[i] += dp[i - j] % mod

    print(dp[n] % mod)


main()

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

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

for i in range(2,N+1):
    for j in S:
        if i<j:
            break
        else:
            dp[i]+=dp[i-j]
            dp[i]%998244353

#print(S)
#print(dp)
print(dp[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, combinations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from operator import itemgetter
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'

def main():
    M = 998244353
    N, K = mis()
    A = []
    for _ in range(K):
        l, r = mis()
        A.extend(range(l, r+1))
    A.sort()
    s = [0]*(N+1)
    s[1] = 1
    for i in range(1, N+1):
        for a in A:
            if i+a <= N:
                s[i+a] = (s[i+a]+s[i])%M
            else:
                break
    print(s[-1])











main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
s = set()
for LR in range(k):
    l, r = map(int, input().split())
    for lr in range(l, r+1):
        s.add(lr)
dp = [0]*n
dp[0] = 1
for i in range(n):
    for d in s:
        if i-d >= 0:
            dp[i] = (dp[i-d] + dp[i]) % 998244353
print(dp[n-1])

Submission status: Time Limit Exceeded

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

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

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

for i in range(N - 1, -1, -1):
    if ans_list[i] == 0:
        continue
    for j in range(len(move_list)):
        step = move_list[j]
        idx = i - step
        if idx < 0:
            continue
        ans_list[idx] += ans_list[i]
ans_num = ans_list[0]
ans_num = ans_num % 998244353
print(ans_num)

Submission status: Time Limit Exceeded

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

s = list()
for li,ri in lr:
    s.extend(list(range(li,ri+1)))
s.sort()
mod = 998244353
ans = [0]*(n)
ans[0] = 1
for i in range(n):
    now = ans[i]
    if now:
        for si in s:
            if i+si < n:
                ans[i+si] += now%mod
                ans[i+si] %= mod
            else:
                break
#print(ans)
print(ans[-1]%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
print(dp[n] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
l_r = [ list(map(int, input().split())) for _ in range(k)  ]
s_s_l = [  list(range(l,r+1)) for l,r in l_r ]
d = [0] * n
d[0] = 1
for i in range(1, n):
    c = 0
    for s_l in s_s_l:
        for s in s_l:
            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:
n, k = map(int,input().split())
dp = [0]*(n+1)
dp[1] = 1
li = []
c = 998244353
for _ in range(k):
    x, y = map(int, input().split())
    li.append([x, y])
for i in range(n+1):
    for j, m in li:
        for l in range(j, m+1):
            if i > l:
                dp[i] += dp[i-l]
print(dp[-1]%c)

Submission status: Time Limit Exceeded

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

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

S.sort()

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

print(dp[-1] % 998244353)

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

    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:
N, K = list(map(int, input().split(" ")))
S = []
for _ in range(K):
    a, b = list(map(int, input().split(" ")))
    S.extend(range(a, b+1))


combinations = [0] * (N + 1)
combinations[1] = 1
S.sort()
for i in range(1, (N + 1 - S[0])):
    for j in S:
        idx = i + j
        if idx < N + 1:
            combinations[idx] += combinations[i]
            if combinations[idx] >= 998244353:
                combinations[idx] = combinations[idx] % 998244353
        else:
            break
print(combinations[-1])

Submission status: Time Limit Exceeded

Solution code:
k =  100000000
while(k):
    k -=1

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools


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

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

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


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline().rstrip("\r\n")
def List(): return list(map(int, input().split()))
def Num(): return int(input())


MOD = 998244353


def countWays(arr, m, N):
    count = [0 for i in range(N + 1)]
    count[0] = 1
    for i in range(1, N + 1):
        for j in range(m):
            if i >= arr[j]:
                count[i] += count[i - arr[j]]
    return count[N]


n, k = List()
s = set()
for i in range(k):
    a, b = List()
    for ele in range(a, b + 1):
        s.add(ele)
s = list(s)
# print(s)
print(countWays(s, len(s), n - 1) % MOD)