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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-09-19 20:49:34 +0900
# LastModified: 2020-09-19 21:53:27 +0900
#


import os
import sys
import numpy as np
# import pandas as pd


def main():
    unko = 998244353
    N, K = map(int, input().split())
    box = np.array([0])
    for _ in range(K):
        L, R = map(int, input().split())
        box = np.append(box, np.arange(L, R+1))
    box = sorted(box[1:])
    dp = [0]*(N+1)
    dp[1] = 1
    for i in range(1, N+1):
        if i + box[0] > N:
            break
        if dp[i] != 0:
            for b in box:
                if i + b > N:
                    break
                dp[i+b] += dp[i]
#        print(dp)
    print(dp[N]%unko)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def readinput():
    n,k=map(int,input().split())
    lr=[]
    for _ in range(k):
        l,r=map(int,input().split())
        lr.append((l,r))
    return n,k,lr

def main(n,k,lr):
    lrs=sorted(lr,key=lambda x:x[0])
    MOD=998244353
    dp=[0]*(n+1)
    dp[1]=1
    for i in range(1,n):
        #print(i)
        if dp[i]==0:
            continue
        skip=False
        for l,r in lrs:
            for j in range(l,r+1):
                #print('i+j: {}'.format(i+j))
                if i+j>n:
                    skip=True
                    break
                dp[i+j]=(dp[i+j]+dp[i])%MOD
                #print(dp)
            if skip:
                break
    return dp[n]

if __name__=='__main__':
    n,k,lr=readinput()
    ans=main(n,k,lr)
    print(ans)

Submission status: Time Limit Exceeded

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

N,K = (int(x) for x in input().rstrip('\n').split())
As = []
n = [x for x in range(1,N+1)]
for _ in range(K):
  L,R = (int(x) for x in input().rstrip('\n').split())
  As.extend(n[L-1:R])
res = [1]
for i in range(1,N):
  d = sum(res[v] for v in range(len(res)) if any(v+x==i for x in As))
  res.append(d%998244353)
print(res[-1])

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:
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
que=[0]
heapq.heapify(que)
can.sort()
while que:
    now=heapq.heappop(que)
    for j in can:
        if now+j>=n:
            break
        table[now+j]=(table[now+j]+table[now])%998244353
        if not now+j in set(que):
            heapq.heappush(que,now+j)
print(table[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
L=[]
for i in range(K):
    l,r=map(int,input().split())
    L.append([l,r+1])
L.sort()
mod=998244353
A=[0 for i in range(N+1)]
A[1]=1
for i in range(N+1):
    if A[i]>0:
        A[i]%=mod
        for l,r in L:
            for n in range(l+i,r+i):
                if n<=N:
                    A[n]+=A[i]
                else:
                    break
print(A[N]%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

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

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


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

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

print(dp[n - 1] % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

mod = 998244353

class BIT:
	def __init__(self, n):
		self.n = n
		self.nums = [0] * (n+1)
		
	def add(self, i, x):
		n, nums = self.n, self.nums
		i += 1
		while i <= n:
			nums[i] += x
			i += i & -i
	
	def sum(self, i):
		nums = self.nums
		s = 0
		i += 1
		while i:
			s += nums[i]
			i -= i & -i
		return s

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

bit = BIT(N+1)
bit.add(1, 1)
bit.add(2, -1)

ans = 0
for i in range(1, N+1):
	s = bit.sum(i)
	#print('s', s)
	for k in range(K):
		l, r = lr[k]
		if i+l <= N:
			#print('l', i+l, s)
			bit.add(i+l, s)
			if i+r+1 <= N:
				#print('r', i+r+1, -s)
				bit.add(i+r+1, -s)
			else:
				ans += s
				ans %= mod
print(ans)
#print(bit.sum(N) % mod)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
L=list()
R=list()
dice=list()
dp=[0]*N
dp[0]=1
for i in range(K):
    l,r=map(int,input().split())
    for i in range(l,r+1):
        if i<=N-1:
            dice.append(i)
dice.sort()
for i in range(1,N):
    for j in range(len(dice)):
        if i-dice[j]<0:
            break
        else:
            dp[i]+=dp[i-dice[j]]
print(dp[N-1]%998244353)

Submission status: Time Limit Exceeded

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

steps = list(chain.from_iterable(range(l, r+1) for l, r in lr))

for i in range(1, N+1):
    if i+mstep > N:
        break
    for step in steps:
#         print(f'{i=}, {step=}')
        if i+step > N:
            break
        dp[i+step] = (dp[i+step] + dp[i]) % MOD
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 標準入力を取得
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)

# 求解処理
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):
    for s in S:
        if i + s <= N:
            m[i + s] += m[i]
        else:
            break

ans = m[N] % 998244353

# 結果出力
print(ans)

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]+dp[i-l])%c
print(dp[-1]%c)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
def I():
    return stdin.readline().rstrip()
def MI():
    return map(int,stdin.readline().rstrip().split())
def LI():
    return list(map(int,stdin.readline().rstrip().split()))
#main part
n,k=MI()
inf=998244353
S=[0]*(n+1)
for _ in range(k):
    l,r=MI()
    if l==r:
        S[l]=1
    else:
        for i in range(l,r+1):
            S[i]=1
s=[]
for i in range(n):
    if S[i]==1:
        s.append(i)
dp=[0]*(2*(10**5)+1)
for i in range(1,len(dp)):
    if i in s:
        dp[i+1]+=1
    for j in range(len(s)):
        if i-s[j]<0:
            break
        else:
            dp[i]+=dp[i-s[j]]
print(dp[n]%inf)

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

print(dp[-1]%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, K = NMI()
    A = list(sorted([NLI() for _ in range(K)]))
    
    ls = [0 for _ in range(N)]
    ls[0] = 1

    for n in range(1,N):
        for k in range(K):
            for x in range(A[k][0],A[k][1]+1):
                if 0 <= n-x:
                    ls[n] += ls[n-x]
                    ls[n] = ls[n]%MOD2
    print(ls[-1])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

MOD = 998244353



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

class BinaryIndexedTree():  #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

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

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

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res + 1

class RAQandRSQ():
    def __init__(self, n):
        self.bit1 = BinaryIndexedTree(n)
        self.bit2 = BinaryIndexedTree(n)

    def add(self, lt, rt, x):
        self.bit1.add(lt, -x * (lt - 1))
        self.bit1.add(rt, x * (rt - 1))
        self.bit2.add(lt, x)
        self.bit2.add(rt, -x)

    def sum(self, lt, rt):
        rsum = self.bit2.sum(rt - 1) * (rt - 1) + self.bit1.sum(rt - 1)
        lsum = self.bit2.sum(lt - 1) * (lt - 1) + self.bit1.sum(lt - 1)
        return rsum - lsum

R = RAQandRSQ(N)
R.add(1, 2, 1)

for i in range(1, N):
    s = R.sum(i, i + 1)
    for l, r in I:
        R.add(i + l, i + r + 1, s)

print(R.sum(N, N + 1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
s=[]
for _ in range(k):
    l,r=map(int,input().split())
    for i in range(l,r+1):
        s.append(i)
s=sorted(s)
ans=[0]*(10**6)
ans[0]=1
for i in range(n-1):
    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())
st = set([])
for i in range(k):
  x,y = map(int,input().split())
  for z in range(x,y+1):
    st.add(z)
ans = [1]
for i in range(1,n):
  s = 0
  for x in st:
    if i >= x:
      s = s + ans[i-x]
  ans.append(s % 998244353)   
  
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines

def main():
    large_num = 998244353
    n, k = map(int, input().split())
    n -= 1
    s = set()
    m = map(int, read().split())
    ab = zip(m, m)
    for a, b in ab:
        for i1 in range(a, b + 1):
            s.add(i1)
    dp = [0] * (n + 1)
    dp[0]=1
    s = list(s)
    s.sort()
    s = tuple(s)
    for i1 in range(1, n+1):
        for se in s:
            if se > i1:
                break
            else:
                dp[i1] += dp[i1 - se]
        dp[i1] = dp[i1] % large_num
    print(dp[-1])

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

class ABC(object):

    def __init__(self):
        pass


    def main(self):
        N, K = map(int, input().split())
        LR = [[int(_) for _ in input().split()] for i in range(K)]
        mod = 998244353

        enable_step = []
        for l, r in LR:
            for i in range(l, r+1):
                enable_step.append(i)
            
        # '0' index is not used.
        step_pattern = [0]*(N+1)
        step_pattern[1] = 1

        for i_n in range(1, N):
            if step_pattern[i_n] == 0:
                continue
            
            for j_enable_step in enable_step:
                if (i_n + j_enable_step) > N:
                    continue
                step_pattern[i_n + j_enable_step] += step_pattern[i_n]
                step_pattern[i_n + j_enable_step] %= mod
        
        ans = step_pattern[N] % mod
        print(ans)
        return


if __name__ == "__main__":
    obj = ABC()
    obj.main()
    sys.exit(0)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
N,K = map(int,input().split())
move = set()
for _ in range(K):
    x,y = map(int,input().split())
    for i in range(x,y+1):
        move.add(i)

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]
    memo[i] = memo[i]%mod
print(memo[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
B=[[0]*2 for i in range(k)]
for i in range(k):
  B[i]=list(map(int,input().split()))
mod=998244353
A=[0]*(n+1)
A[0]=1
a=1
for i in range(n):
  for j in range(k):
    A[min(n,i+B[j][0])]=A[min(n,i+B[j][0])]+a
    A[min(n,i+B[j][1]+1)]=A[min(n,i+B[j][1]+1)]-a
  a=a+A[i+1]
print(A[-2]%mod)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
lis = []
ans = [0]*n + [1]
for _ in range(k):
  a, b = map(int, input().split())
  lis = lis + [i for i in range(a, b+1)]

s = set(lis)
s = sorted(list(s))

for i in reversed(range(1, n)):
  for j in s:
    if i + j > n:
      break
    ans[i] = ans[i] + ans[i+j]
print(ans[1]%998244353)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

MOD = 998244353

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

for i in range(1, n+1):
    for l, r in lr:
        for j in range(l, r+1):
            if i - j >= 0:
                dp[i] = (dp[i] + dp[i-j]) % MOD
            else:
                break

#print(dp)
print(dp[n] % MOD)

Submission status: Time Limit Exceeded

Solution code:
# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# from time import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

# mod = int(1e9+7)
mod = 998244353
INF = 1<<50

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

def main():
    n,k = readInt()
    s = set()
    for i in range(k):
        l,r = readInt()
        for j in range(l,r+1):
            s.add(j)
    s = list(s)
    s.sort()
    dp = [0 for i in range(n)]
    dp[0] = 1
    for i in range(n):
        if dp[i]==-1:
            continue
        for j in range(len(s)):
            if i+s[j]>=n:
                break
            dp[i+s[j]] += dp[i]
            dp[i+s[j]] %= mod
    print(dp[n-1])
    return

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m= list(map(int,input().split()))
s = []
for _ in range(m):
  p,q = list(map(int,input().split()))
  for i in range(p,q+1):
    s.append(i)
ways = [1] + [0 for _ in range(n-1)]
for i in range(1,n):
  for x in s:
    if i -x >=0:
      ways[i] += ways[i-x]
print(ways[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split(" "))
d_list = []
for i in range(k):
  a,b = map(int, input().split(" "))
  d_list.extend(range(a,b+1))

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

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
grid = []
for i in range(k):
    array = list(map(int, input().strip().split(' ')))
    grid.append(array)

S = []

for i in range(k):
    for j in range(grid[i][1]-grid[i][0]+1):
        S.append(grid[i][0]+j)
S.sort()
S = set(S)
#print(S)
array = [1]

for i in range(2,n+1):
    count = 0
    for j in S:
        if i - j > 0:
            count += array[i-j-1] % 998244353
            count = count % 998244353
            #print(i,j,array[i-j-1])
    array.append(count)
    #print(i,count)

print(array[n-1])

Submission status: Time Limit Exceeded

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

MOD = 998244353

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

class BinaryIndexedTree():  #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

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

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

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res + 1

class RAQandRSQ():
    def __init__(self, n):
        self.bit1 = BinaryIndexedTree(n)
        self.bit2 = BinaryIndexedTree(n)

    def add(self, lt, rt, x):
        self.bit1.add(lt, -x * (lt - 1))
        self.bit1.add(rt, x * (rt - 1))
        self.bit2.add(lt, x)
        self.bit2.add(rt, -x)

    def sum(self, lt, rt):
        rsum = self.bit2.sum(rt - 1) * (rt - 1) + self.bit1.sum(rt - 1)
        lsum = self.bit2.sum(lt - 1) * (lt - 1) + self.bit1.sum(lt - 1)
        return rsum - lsum

R = RAQandRSQ(N)
R.add(1, 2, 1)

for i in range(1, N):
    s = R.sum(i, i + 1)
    for l, r in I:
        R.add(i + l, i + r + 1, s)

print(R.sum(N, N + 1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-09-19 20:49:34 +0900
# LastModified: 2020-09-19 21:50:15 +0900
#


import os
import sys
import numpy as np
# import pandas as pd


def main():
    unko = 998244353
    N, K = map(int, input().split())
    box = np.array([0])
    for _ in range(K):
        L, R = map(int, input().split())
        box = np.append(box, np.arange(L, R+1))
    box = sorted(box[1:])
    dp = [0]*(N+1)
    dp[1] = 1
    for i in range(1, N+1):
        if dp[i] != 0:
            for b in box:
                if i + b > N:
                    break
                dp[i+b] += dp[i]
#        print(dp)
    print(dp[N]%unko)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

for i in range(2, N + 1):
    temp = dp[i]
    for step in S:
        if step > i:
            break
        temp += dp[i - step]
        temp %= MOD
    dp[i] = temp
    
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)
import itertools as it
import collections as cl
from collections import deque
import math
from functools import reduce
from collections import defaultdict
MOD = 998244353


def li():
    return [int(x) for x in input().split()]

N, K = li()

s = set()
for _ in range(K):
    a, b = li()
    for i in range(a, b+1):
        s.add(i)

# dp[i]: マスiに到達する方法の個数
dp = [0] * (N+1)
dp[0] = 1
for i in range(N):
    for j in s:
        if i + j <= N:
            dp[i+j] += dp[i]
            dp[i+j] %= MOD
print(dp[N-1])

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_l = [  list(range(l,r+1)) for l,r in l_r ]
import itertools
s_l = list(itertools.chain.from_iterable(s_l))
d = [0] * n
d[0] = 1

for i in range(1, n):
    c = 0
    for s in s_l:
        if s <= i and d[i-s] > 0:
            c += d[i-s]
    d[i] = c%998244353
print(d[-1]%998244353)

Submission status: Time Limit Exceeded

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

mod = 998244353

for _ in range(K):
    L, R = map(int,input().split())
    for d in range(L, R+1):
        moves.add(d)

dp = [0] * (N + 1)
dp[1] = 1
# for dis in moves:
#     dp[dis] = 1

for n in range(1, N+1):
    for dis in moves:
        if n - dis >= 1:
            # print(n, n - dis)
            dp[n] += dp[n - dis]

# print(dp)
print(dp[N] % mod)

Submission status: Time Limit Exceeded

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

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

resolve()

Submission status: Time Limit Exceeded

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

for i in range(k):
    tmp = tuple(map(int, input().split()))
    lists += [i for i in range(tmp[0], tmp[1] + 1)]

lists.sort()

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

for i in range(1, n):
    for num in lists:
        if i < num:
            break

        dp[i] += dp[i - num]
        dp[i] %= mod

print(dp[n - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys

MOD = 998244353


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

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

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


def main():
    input = sys.stdin.buffer.readline
    n, k = map(int, input().split())
    lr = [tuple(map(int, input().split())) for _ in range(k)]
    dp = Bit(n)
    dp.add(1, 1)
    for i in range(2, n + 1):
        for l, r in lr:
            if i - l < 1:
                continue
            if i - r < 2:
                dp.add(i, dp.sum(i - l) % MOD)
            else:
                dp.add(i, (dp.sum(i - l) - dp.sum(i - r - 1)) % MOD)
    print((dp.sum(n) - dp.sum(n - 1)) % MOD)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, K = NMI()
    A = list(sorted([NLI() for _ in range(K)]))
    
    ls = [0 for _ in range(N)]
    ls[0] = 1

    for n in range(1,N):
        for k in range(K):
            for x in range(A[k][0],A[k][1]+1):
                if 0 <= n-x and n-x <= N:
                    ls[n] += ls[n-x]
                    ls[n] = ls[n]%MOD2
    print(ls[-1])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

mod = 998244353

result = [1]
for ni in range(1, N):
  result.append(0)
  for l, r in LR:
    for j in range(l, r+1):
      if ni-j<0: continue
      result[ni] += result[ni-j]
      result[ni] %= mod
print(result[-1])

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
que=[0]
heapq.heapify(que)
can.sort()
while que:
    now=heapq.heappop(que)
    for j in can:
        if now+j<n:
            table[now+j]=(table[now+j]+table[now])%998244353
            if not now+j in set(que):
                heapq.heappush(que,now+j)
print(table[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
s=[]
data=set(s)
for i in range(k):
    x,y=map(int,input().split())
    while(1):
        data.add(x)
        if(x>=y):
            break
        x+=1
        
dp=[0 for i in range(n+1)]
dp[1]=1
for i in range(1,n):
    for j in data:
        if(i+j<=n):
            dp[i+j]+=dp[i]
            dp[i+j]%=998244353
print(dp[n]%998244353)

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, dtype=int)
a_list[1] = 1
for i in range(k):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        s_list.append(j)
s_list.sort()
for i in range(1, n):
    for s in s_list:
        if i + s > n:
            break
        a_list[i + s] += a_list[i]
print(a_list[n] % 998244353)

Submission status: Time Limit Exceeded

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

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

c = [0]*N
c[N-1] = 1
ans = 0
for i in range(N):
  if c[N-1-i] == 0:
    continue
  for j in range(len(S)):
    if N-1-i-S[j]<0:
      continue
    elif N-1-i-S[j]==0:
      ans += c[N-1-i]
    else:
      c[N-1-i-S[j]]+=c[N-1-i]

print(ans%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
for i in range(1, N + 1):
    for j in S:
        idx = i + j
        if idx < N + 1:
            combinations[idx] += combinations[i]
            if combinations[idx] >= 998244353:
                combinations[idx] = combinations[idx] % 998244353

print(combinations[-1])

Submission status: Time Limit Exceeded

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

mod = 998244353

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

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

s = set(s)

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

s = sorted(list(s))


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

print(dp[n-1]%mod)

Submission status: Time Limit Exceeded

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

s=[]

for _ in range(k):
    lr=[int(i) for i in input().split()]
    s+=list(range(lr[0],lr[1]+1))

dp=[0]*(n+1)
dp[1]=1
for i in range(1,n+1):
    for step in s:
        if i+step<=n:
            dp[i+step]=(dp[i+step]+dp[i])%998244353
            
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from typing import Collection

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

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
#print(ans)
print(ans[-1]%mod)