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: Runtime Error

Solution code:
def coun(x,i):
    if dp[i]!=0:
        return dp[i]
    else:
        for j in x:
            if (j+i)<=n-1:
                dp[i]+=coun(x,i+j)
        return dp[i]

n,k=map(int,input().split())
x=[]
for i in range(k):
    a,b= map(int,input().split())
    for j in range(a,b+1):
        x.append(j)
mod=998244353
dp=[0]*n
dp[-1]=1
print(coun(x,0)%mod)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
l,r = [list(map(int,input().split())) for i in range(k)]
suji = 998244353
s = []
for i in l:
    s.append(i)
for j in r:
    s.append(j)
_s = set(s)
pos=[]

def dfs(x):
    if x > n:
        return
    if x == n:
        pos.append(True)
    for i in _s:
        dfs(x+i)
        
dfs(1)

num = pos.count(True)

print(num%suji)

Submission status: Runtime Error

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

div = set()
for _ in range(K):
  l,r = map(int,input().split())
  for i in range(l,r+1):
    div.add(i)
min_step = min(div)
dp = [-1]*N
dp[0] = 1
def calc(i):
  if dp[i] != -1: return dp[i]
  if i < min_step: dp[i]=0; return dp[i]

  dp[i] = 0
  for j in div:
    if j > i: continue
    dp[i-j] = calc(i-j)
    dp[i] = (dp[i] + dp[i-j])%mod
  dp[i] %= mod
  return dp[i]

print(calc(N-1)%mod)

Submission status: Runtime Error

Solution code:
from functools import lru_cache


s = set()
m = 998244353

def main():
    n, k = map(int, input().split())
    for i in range(k):
        l, r = map(int, input().split())
        for j in range(l, r + 1):
            s.add(j)

    # print(s)

    # for i in range(n):
    #     rec(i)

    print(rec(n - 1) % m)


@lru_cache(maxsize=10000000000)
def rec(x):
    if x == 0:
        return 1

    y = [rec(x - i) % m for i in s if x - i >= 0]
    return sum(y) % m

main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)


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)

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

def f(n):
    if flag[n]:
        return dp[n]
    flag[n] = 1
    ret = dp[n]
    for step in S:
        ret += f(n - step) % MOD
        ret %= MOD
    dp[n] = ret
    return ret

print(f(N))

Submission status: Runtime Error

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)

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

def f(n):
    if flag[n]:
        return dp[n]
    flag[n] = 1
    ret = dp[n]
    for step in S:
        ret += f(n - step) % MOD
        ret %= MOD
    dp[n] = ret
    return ret

print(f(N))

Submission status: Runtime Error

Solution code:

MOD = 998244353

def solve(N, LR, memo):
    if N == 1:
        return 1
    if N in memo:
        return memo[N]
    answer = 0 
    for l, r in LR:
        for d in range(l, r+1):
            if N-d > 0:
                answer += solve(N-d, LR, memo)
                answer %= MOD
    memo[N] = answer
    return answer


LR = []
N, K = map(int, input().split())
for i in range(K):
    L, R = map(int, input().split())
    LR.append([L, R])
memo = {}
print(solve(N, LR, memo))

Submission status: Runtime Error

Solution code:
# import numpy as np

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


S = []
for k in range(K):
    for i in range(LR[k][0], LR[k][1] + 1):
        S.append(i)
        
memo = [-1 for _ in range(N)]

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

res =  move(N - 1) % 998244353
print(res)

Submission status: Runtime Error

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

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

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

for i in range(0,N):
    for l,r in S:
        for x in range(l,r+1):
            dp[i+x] += dp[i]

print(dp[N-1]%MOD)

Submission status: Runtime Error

Solution code:
N = int(input())
ans = 0
for i in range(1, N+1):
    for j in range(1, N+1):
        if i*j <= N-1:
            ans += 1
        else:
            break
print(ans)

Submission status: Runtime Error

Solution code:
# import numpy as np
import sys, math, heapq
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
MOD = 998244353
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

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

for i in range(1, N + 1):
    for lr in LR:
        l, r = lr
        if i in range(l, r + 1):
            S.add(i)

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

Submission status: Runtime Error

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, K, LR):
    mod = 998244353
    S = []
    for lr in LR:
        S += [i for i in range(lr[0], lr[1] + 1)]
    S.sort()
    dp = [0] * (N + 1)
    dp[1] = 1
    for i in range(1, N + 1):
        for s in S:
            if i + s > N:
                break
            dp[i + s] = (dp[i + s] + dp[i]) % mod
    print(dp[N])


if __name__ == '__main__':
    # N, K = map(int, input().split())
    # LR = [[int(i) for i in input().split()] for _ in range(K)]
    # solve(N,K,LR)

    # test
    from random import randint
    from func import random_str

    N, K = 2 * 10 ** 5, 1
    LR = [[1, N]]
    solve(N, K, LR)

Submission status: Runtime Error

Solution code:
from functools import lru_cache


s = set()

def main():
    n, k = map(int, input().split())
    for i in range(k):
        l, r = map(int, input().split())
        for j in range(l, r + 1):
            s.add(j)

    # print(s)

    # for i in range(n):
    #     rec(i)


    print(rec(n - 1) % 998244353)



@lru_cache(maxsize=100000000)
def rec(x):
    if x == 0:
        return 1

    y = [rec(x - i) for i in s if x - i >= 0]
    return sum(y)

main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
n, k = map(int, input().split())
a = []
mod = 998244353
for i in range(k):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        a.append(j)
dp = [0] * (n + 20)
dp[0] = 1
for i in range(n):
    for j in a:
        dp[i + j] += dp[i]
        dp[i + j] %= mod

print(dp[n - 1])

Submission status: Runtime Error

Solution code:
from sys import stdin


class DFS():
    def __init__(self,N,S):
        self.N = N
        self.S = S
        self.cnt = 0

    def dfs(self, i):
        if i == self.N-1:
            self.cnt += 1
            return
        elif i > self.N-1:
            return
        else:
            for s in self.S:
                self.dfs(i+s)
            return


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, K = list(map(int, _in[0].split(' ')))  # type:list(int)
    L_R_arr = []
    for i in range(K):
        _ = list(map(int, _in[i+1].split(' ')))  # type:list(int)
        L_R_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    ans = 0
    S = []
    for L, R in L_R_arr:
        S.extend([i for i in range(L, R+1)])
    S = sorted(set(S))

    dfs = DFS(N, S)
    dfs.dfs(0)
    ans = dfs.cnt
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
nk=map(int,input().split())
a=[]
for i in range(k):
  lr=map(int,input().split())
  for i in range(l,r+1):
    a.append(i)
a=list(set(a))
dp=[0]*n
dp[0]=1
for i in range(1,n):
  for j in a:
    if i>=j:
      dp[i]+=dp[i-j]
return dp[-1]

Submission status: Runtime Error

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

mod = 998244353
n, k = [int(e) for e in si().split()]
dp, coins = [0 for _ in range(200000+1)], []
while k:
    k -= 1
    a, b = [int(e) for e in si().split()]
    for i in range(a, b+1):
        coins.append(i)
        dp[1+i] = 1

for i in range(1, n+1):
    for coin in coins:
        if i >= coin:
            dp[i] = (dp[i]+dp[i-coin]) % mod
print(dp[n])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 998244353
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,K = IL()
data = ILL(K)
data.sort()

class SegmentTree:
  def __init__(self, n, e):
    self.n = n
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
 
  def get(self, i):
    i += self.size
    ret = self.node[i]
    while i > 1:
      i >>= 1
      ret += self.node[i]
    return ret
 
  def add(self, l, r, val):
    l, r = l + self.size, r + self.size
    while l < r:
      if l & 1:
        self.node[l] += val
        self.node[l] %= MOD
        l += 1
      if r & 1:
        r -= 1
        self.node[r] += val
        self.node[r] %= MOD
      l, r = l >> 1, r >> 1
      
ST = SegmentTree(N,0)
ST.add(1,2,1)

for i in range(1,N+1):
  for k in range(K):
    l,r = data[k]
    if i+l <= N:
      ST.add(i+l,min(i+r+1,N+1),ST.get(i))

print(ST.get(N)%MOD)

Submission status: Runtime Error

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 998244353
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,K = IL()
data = ILL(K)
data.sort()

class SegmentTree:
  def __init__(self, n, e):
    self.n = n
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
 
  def get(self, i):
    i += self.size
    ret = self.node[i]
    while i > 1:
      i >>= 1
      ret += self.node[i]
    return ret
 
  def add(self, l, r, val):
    l, r = l + self.size, r + self.size
    while l < r:
      if l & 1:
        self.node[l] += val
        self.node[l] %= MOD
        l += 1
      if r & 1:
        r -= 1
        self.node[r] += val
        self.node[r] %= MOD
      l, r = l >> 1, r >> 1
      
ST = SegmentTree(N,0)
ST.add(1,2,1)

for i in range(1,N+1):
  for k in range(K):
    l,r = data[k]
    ST.add(i+l,min(i+r+1,N+1),ST.get(i))

print(ST.get(N)%MOD)