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: Accepted

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

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

# for i in range(k):
#     C[i][0] -= 1
#     C[i][1] -= 1

# ACLに伴い0-indexedに直した
class Bit:  # Fenwick Tree と同じ
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, l, r):  # [l,r)の合計を求める
        # 内部的には[l+1,r+1)の合計つまり(rまでの合計-lまでの合計)
        s = 0
        while r > 0:
            s += self.tree[r]
            r -= r & -r
        while l > 0:
            s -= self.tree[l]
            l -= l & -l
        return s
  
    def add(self, i, x):  # i番目にxを足す
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

# Bitの内部状態をindex順に出力
def print_bit(B):
    n = B.size
    ANS = []
    for i in range(n):
        ANS.append(B.sum(i, i+1))
    print(*ANS)

B = Bit(n)
mod = 998244353
B.add(0, 1)
for i in range(1, n):
    for j in range(k):
        B.add(i, (B.sum(max(0,i-C[j][1]), max(0,i-C[j][0]+1)))%mod)

print(B.sum(n-1,n)%mod)

Submission status: Accepted

Solution code:
from math import inf, log2


class SegmentTree:
    def __init__(self, array, func=max):
        self.n = len(array)
        self.size = 2**(int(log2(self.n-1))+1) if self.n != 1 else 1
        self.func = func
        self.default = 0 if self.func != min else inf
        self.data = [self.default] * (2 * self.size)
        self.process(array)

    def process(self, array):
        self.data[self.size : self.size+self.n] = array
        for i in range(self.size-1, -1, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def query(self, alpha, omega):
        """Returns the result of function over the range (inclusive)!"""
        if alpha == omega:
            return self.data[alpha + self.size]
        res = self.default
        alpha += self.size
        omega += self.size + 1
        while alpha < omega:
            if alpha & 1:
                res = self.func(res, self.data[alpha])
                alpha += 1
            if omega & 1:
                omega -= 1
                res = self.func(res, self.data[omega])
            alpha >>= 1
            omega >>= 1
        return res

    def update(self, index, value):
        """Updates the element at index to given value!"""
        index += self.size
        self.data[index] = value
        index >>= 1
        while index:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index >>= 1


# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

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


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


for _ in range(int(input()) if not True else 1):
    #n = int(input())
    n, k = map(int, input().split())
    #a, b = map(int, input().split())
    #c, d = map(int, input().split())
    #a = list(map(int, input().split()))
    #b = list(map(int, input().split()))
    a = [0]*(n+1)
    a[1] = 1
    st = SegmentTree(a, func=lambda a,b:a+b)
    segs = []
    for i in range(k):
        l, r = map(int, input().split())
        segs += [[l, r]]
    mod = 998244353
    for i in range(2, n+1):
        val = 0
        for l, r in segs:
            if i - l >= 1:
                val += st.query(max(1, i-r), i-l)
                val = val % mod
        st.update(i, val)
    print(st.query(n, n))

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 998244353

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        if k<0 or n<k:
            return 0
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

######################################################

N,K=mint()
lr=[lint() for _ in range(K)]
dp=[0]*(N+1)
dp[1]=1
dp[2]=-1
tmp=0
for i in range(1,N):
    tmp+=dp[i]
    tmp%=MOD
    for l,r in lr:
        if i+l<=N:
            dp[i+l]+=tmp
            dp[i+l]%=MOD
        if i+r+1<=N:
            dp[i+r+1]-=tmp
            dp[i+r+1]%=MOD
print(sum(dp)%MOD)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
mod = 998244353
a = [tuple(map(int, input().split())) for _ in range(K)]
dp = [0] * (N + 1)
dp[1] = 1
imos = [0] * (N + 1)
for i in range(1, N):
  dp[i] += imos[i]
  dp[i] %= mod
  for l, r in a:
    if i + l > N: continue
    imos[i + l] += dp[i]
    imos[i + l] %= mod
    if i + r + 1 > N: continue
    imos[i + r + 1] -= dp[i]
    imos[i + r + 1] %= mod
  imos[i + 1] += imos[i]
  imos[i + 1] %= mod
dp[-1] += imos[-1]
dp[-1] %= mod
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
input=lambda:sys.stdin.readline().rstrip()

# BinaryIndexedTree
# O(logN)で累積和取得と値の更新
# add(i,x)...i番目にxを加算
# sum(i,j)...[i,j)の累積和を取得
# sum_sub(i)...[0:i]の累積和を取得
class BinaryIndexedTree:
  def __init__(self, n):
    self.bit = [0] * n

  def add(self, i, x):
    i += 1
    while i <= len(self.bit):
      self.bit[i-1] += x
      i += i & -i

  def sum_sub(self, i):
    a = 0
    i += 1
    while i:
      a += self.bit[i-1]
      i -= i & -i
    return a

  def sum(self, i, j):
    a = 0
    if j != 0:
      a += self.sum_sub(j-1)
    if i != 0:
      a -= self.sum_sub(i-1)
    return a
mod=998244353
n,k=map(int,input().split())
lr=[]
for i in range(k):
  l,r=map(int,input().split())
  lr.append((l,r))
bit=BinaryIndexedTree(2*n+7)
bit.add(0,1)
bit.add(1,-1)
for i in range(n-1):
  x=bit.sum_sub(i)%mod
  for l,r in lr:
    bit.add(i+l,x)
    bit.add(i+r+1,-x)
print(bit.sum_sub(n-1)%mod)

Submission status: Accepted

Solution code:
mod = 998244353
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int, input().split())
    L = []
    R = []
    for _ in range(K):
        l, r = map(int, input().split())
        L.append(l)
        R.append(r)

    dp = [0] * (N+1)
    dp[1] = 1
    for i in range(2, N+1):
        dp[i] = dp[i-1]
        for k in range(K):
            l, r = L[k], R[k]
            if i - l <= 0:
                continue
            mi = max(1, i - r)
            ma = i - l
            dp[i] = (dp[i] + dp[ma] - dp[mi - 1])%mod
    print((dp[-1] - dp[-2])%mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n, K = na()
lr = []
for i in range(K):
    lr.append(na())

mod = 998244353
dp = [0] * (n+1)
cum = [0] * (n+1)

dp[1] = cum[1] = 1
for i in range(2, n+1):
    v = 0
    for u in lr:
        l = max(1, i-u[1])
        r = i-u[0]
        if l <= r:
            v += cum[r] - cum[l-1] + mod
    dp[i] = v % mod
    cum[i] = cum[i-1] + dp[i]
    if cum[i] >= mod:
        cum[i] -= mod
print(dp[n])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
X=[list(map(int,input().split())) for i in range(K)]
C=[0]*(N*3)
DP=[0]*N
mod=998244353
DP[0]=1
Y=0
for i in range(N):
  Y+=C[i]
  DP[i]+=Y
  Y%=mod
  DP[i]%=mod
  for j in range(K):
    C[i+X[j][0]]+=DP[i]
    C[i+X[j][1]+1]-=DP[i]
print(DP[N-1])

Submission status: Runtime Error

Solution code:
import numpypy as np
N,K=map(int,input().split())
arr=np.array([0]*N)
for _ in range(K):
    l,r=map(int,input().split())
    arr[l-1:r]+=1
#print(arr)
dp=np.array([0]*(2*N))
dp[1]=1

for n in range(2,N+1):
    dp[n:n+N]+=(arr*(dp[n-1]%998244353))
    #print(dp)
print(dp[N]%998244353)

Submission status: Runtime Error

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
N, K = map(int, input().split())

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

m = 998244353

S = []
for lr in LR:
    S.extend(range(lr[0], lr[1]+1))

p = ['a']*N
p[0] = 1

def getpi(i):
    if i<0:
        return 0
    if p[i] == 'a':
        t = 0
        for s in S:
            t += getpi(i-s)
        t = t%m
        p[i] = t
        return t 
    else:
        return p[i]

print (getpi(N-1))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())

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

m = 998244353

S = []
for lr in LR:
    S.extend(range(lr[0], lr[1]+1))

p = ['a']*N
p[0] = 1

def getpi(i):
    if i<0:
        return 0
    if p[i] == 'a':
        t = 0
        for s in S:
            t += getpi(i-s)
        t = t%m
        p[i] = t
        return t 
    else:
        return p[i]

print (getpi(N-1))

Submission status: Runtime Error

Solution code:
#include <iostream>
using namespace std;
using ll = __int128_t;
ll dp[1000005] = {0};
pair<int, int> p[10];
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < k; ++i)
    {
        cin >> p[i].first >> p[i].second;
    }
    ll cur = 1;
    for (int i = 1; i < n; ++i)
    {
        cur += dp[i];
        for (int j = 0; j < k; ++j)
        {
            if (i + p[j].first <= n)
            {
                dp[i + p[j].first] += cur;
                dp[i + p[j].second + 1] -= cur;
            }
        }
    }
    cout << int(dp[n] % 998244353);
}

Submission status: Runtime Error

Solution code:
#include <iostream>
using namespace std;
using ll = __int128_t;
ll dp[1000005] = {0};
pair<int, int> p[10];
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < k; ++i)
    {
        cin >> p[i].first >> p[i].second;
    }
    ll cur = 1;
    for (int i = 1; i < n; ++i)
    {
        cur += dp[i];
        for (int j = 0; j < k; ++j)
        {
            if (i + p[j].first <= n)
            {
                dp[i + p[j].first] += cur;
                dp[i + p[j].second + 1] -= cur;
            }
        }
    }
    cout << dp[n] % 998244353;
}

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
LR=[]
move=[]
P=998244353

for i in range(K):
    temp=list(map(int,input().split()))
    LR.append(temp)
    for j in range(temp[0],temp[1]+1):
        move.append(j)
move.sort()
l=len(move)
stamp={0:1}

def dp(N):    
    if N<0:    
        return 0
    elif N in stamp.keys():
        return stamp[N]
    else:
        temp=0
        for j in range(l):
            temp+=dp(N-move[j])
            stamp[N]=temp
        return temp    
        
ans=dp(N-1)%P
print(ans)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
LR=[]
move=[]

for i in range(K):
    temp=list(map(int,input().split()))
    LR.append(temp)
    for j in range(temp[0],temp[1]+1):
        move.append(j)
move.sort()
l=len(move)
ishere={0:1}

def dp(N):    
    if N<0:    
        return 0
    elif N==0:
        return 1
    elif N in ishere.keys():
        return ishere[N]
    else:
        temp=0
        for j in range(l):
            temp+=dp(N-move[j])
            ishere[N]=temp
        return temp    
ans=dp(N-1)%998244353
print(ans)

Submission status: Runtime Error

Solution code:
N,K,*LR=map(int,open(0).read().split())
S=set()
for i in range(0,K*2,2):
    S |= set(range(LR[i],LR[i+1]+1))
cache={1:1}
def count(n):
    if n in cache:
        return cache[n]
    ans=0
    for s in S:
        ns=n-s
        if ns==1:
            ans+=1
        elif ns>1:
            ans+=count(ns)
    cache[n]=ans
    return ans
print(count(N)%998244353)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
l, r = [0] * k, [0] * k
mod = 998244353
data = []
for i in range(k):
    l, r = map(int, input().split())
    data.append(l)
    data.append(r)

data = list(set(data))
ans = 0
def check(i):
    global ans
    if i >= n:
        if i == n:
            ans += 1
        return 
    for j in range(len(data)):
        check(i + data[j])

check(1)
print(ans % mod)

Submission status: Runtime Error

Solution code:
def f(L,n):
    x=0
    if n<1:
        return 0
    if n==1:
        return 1
    if n>1:
        for i in range(len(L)):
            x+=f(L,n-L[i])
            x=x%998244353      
        return x
def f2(L,a,b):
    for i in range(min(a,b),max(a,b)+1):
        L[i]=1
    return L
N,K=map(int,input().split())
M=[]
for i in range(K):
    l=list(map(int,input().split()))
    M.append(l)
L=[0 for i in range(N+1)]
for i in range(K):
    f2(L,M[i][0],M[i][1])
X=[]
for i in range(N+1):
    if L[i]==1:
        X.append(i)
print(f(X,N)%998244353)

Submission status: Runtime Error

Solution code:
def a(num, b):
        ans = 0
        for i in range(len(b)):
                if(num - b[i] == 0):
                        ans = ans + 1
                elif(num - b[i] > 0):
                        ans +=a(num - b[i], b)
        return ans

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

for i in range(K):
        for n in input().split():
                S.append(int(n))

S = sorted(set(S), reverse=True)
print(a(N - 1, S) % 998244353)

Submission status: Runtime Error

Solution code:
def main(N, S):
    dp = [0 if n != 0 else 1 for n in range(N)] # 初期値
    lst_S = sorted(list(S))

    for i in range(N):
        if dp[i] == 0:  # 計算時間削減のため， 時間さえ間に合えば不要かも．
            continue
        for j in lst_S:
            if i + j > N - 1:
                break
            else:
                dp[i+j] = (dp[i+j] + dp[i]) % mod
    print(dp[-1])


if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    S = set()
    for k in range(K):
        L, R = map(int, input().split())
        {S.add(i) for i in range(L, R+1)}
    main(N, S)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
X=[list (map(int,input().split())) for i in range(K)]
Y=[]
for i in range(K):
  for j in  range(X[i-1][0],X[i-1][1]+1):
    Y.append(j)
  else:
else:
  
Z=[0]*(max(Y)-1)+[1]
for i in range(N-1):
  a=0
  for j in Y:
    a=a+Z[len(Z)-j]
  break
  Z.append(a):
break
  
print(Z(-1))

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
X=[list (map(int,input().split())) for i in range(K)]
Y=[]
for i in range(K):
  for j in  range(X[i-1][0],X[i-1][1]+1):
    Y.append(j)
  else:
else:
  
Z=[0]*(max(Y)-1)+[1]
for i in range(N-1):
  a=0
  for j in Y:
    a=a+Z[len(Z)-j]
  else:
  Z.append(a):
else:
  
print(Z(-1))

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
X=[list (map(int,input().split())) for i in range(K)]
Y=[]
for i in range(K):
  for j in  range(X[i-1][0],X[i-1][1]+1):
    Y.append(j)
  else:
else:
  
Z=[0]*(max(Y)-1)+[1]
for i in range(N-1):
  a=0
  for j in Y:
    a=a+Z[len(Z)-j]
  else:
  Z.append(a):
else:
  
print(Z(N+max(Y)-2))

Submission status: Runtime Error

Solution code:
p = 998244353
n, k = map(int, input().split())
LRs = [tuple(map(int, input().split())) for _ in range(k)]
A = [0] * (2 * n)
for lj, rj in LRs:
    A[lj] += 1
    A[rj + 1] -= 1
s = 0
for i in range(1, n):
    s = (s + A[i]) % p
    for lj, rj in LRs:
        A[i + lj] += s
        A[i + rj + 1] -= s
print(s)

Submission status: Runtime Error

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

mod = 998244353

dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % modp)

print(dp[n-1])

Submission status: Runtime Error

Solution code:
mod = 998244353
n,k = map(int, input().split()) 
num_list = [list(map(int, input().split())) for _ in range(k)]
cnt_list = [0]*n
cnt_list[0] = 1
s_list = []
set_list = [0]*n

for i in range(len(num_list)):
    if num_list[i][0] == num_list[i][1]:
        s_list.append(num_list[i][0])
    else:
        for j in range(num_list[i][0],num_list[i][1]+1):
            s_list.append(j)

for i in range(len(s_list)):
    set_list[s_list[i]] = 1

for i in range(n):
    cnt_list = [x * cnt_list[i] + y for (x, y) in zip(set_list, cnt_list)]
    set_list.insert(0,0)
    set_list.pop(n)

print(cnt_list[n-1]%mod)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

n, k = map(int, input().split())
a = set()
for i in range(k):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        a.add(j)
a = list(a)

x = [0] * n
x[0] = 1

@lru_cache
def mov(i):
    y = 0

    for d in a:
        if i == 1:
            return 1
        elif i - d >= 0:
            y += mov(i - d)
    return y


print(mov(n) % 998244353)

Submission status: Runtime Error

Solution code:
div = 998244353

N, K = map(int, input().split())
L = set()
for _ in range(K):
    L = L.union(set(list(map(int, input().split()))))

Lst = list(L)
Lst.sort()

def cntroot(remaining, cnt, Lst):
    for x in Lst:
        if (remaining - x) >  0:
            cnt = cntroot(remaining - x, cnt, Lst)
        elif (remaining - x) == 0:
            cnt += 1
            break
        else:
            break
    return cnt

print(cntroot(N - 1, 0, Lst) % div)

Submission status: Runtime Error

Solution code:
div = 998244353

N, K = map(int, input().split())
L = set()
for _ in range(K):
    L = L.union(set(list(map(int, input().split()))))

Lst = list(L)
Lst.reverse()
print(Lst)

def cntroot(remaining, cnt, Lst):
    for x in Lst:
        if (remaining - x) >  0:
            cnt = cntroot(remaining - x, cnt, Lst)
        elif (remaining - x) == 0:
            cnt += 1
        else:
            pass
    return cnt

print(cntroot(N - 1, 0, Lst) % div)

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
dp = [0]*(N*2+1)
dp[1] = 1
dp[2] = -1
mod = 998244353
LR = [list(mapint()) for _ in range(K)]
for i in range(1, N+1):
    dp[i] = (dp[i]+dp[i-1])%mod
    for l, r in LR:
        dp[i+l] = (dp[i+l]+dp[i])%mod
        dp[i+r+1] = (dp[i+r+1]-dp[i])%mod

print(dp[N])

Submission status: Runtime Error

Solution code:
# 配るDP
def resolve():
  base = 998244353
  N, K = map(int, input().split(" "))

  LRs = []
  for _ in range(K):
    (L, R) = map(int, input().split(" "))
    LRs.append((L, R))

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

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

    for lr in LRs:
      left = i + lr[0]
      right = i + lr[1] + 1
      if left <= N:
        dp[left] += dp[i]
        dp[left] = mod(dp[left], base)
      if right <= N:
        dp[right] -= dp[i]
        dp[right] = mod(dp[right], base)
  print(mod(dp[-1], base))

if __name__ == "__main__":
  resolve()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from bisect import bisect_left,bisect

icase=0
if icase==0:
    n,k=map(int,input().split())

    s=[]
    for i in range(k):
        li,ri=list(map(int,input().split()))
        for i in range(li,ri+1):
            s.append(i)
elif icase==1:
    n,k=5,2
    s=[1, 3, 4]
elif icase==2:
    n,k=60,3    
    s=[5, 6, 7, 8, 1, 2, 3, 10, 11, 12, 13, 14, 15]

s.sort()

mod=998244353

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

iri=[0]*n
for si in s:
    iri[si]=1
for i in range(1,n):
    iri[i]=iri[i]+iri[i-1]    

for i in range(1,n):
#    ir=min(bisect(s,n-i)+1,n)
    ir=min(iri[n-i]+1,n)
    for si in s[:ir]:
        j=i+si
        if j<=n:
            dp[j]=(dp[j]+dp[i])%mod
#    print(i,ir,dp)

print(dp[n])

Submission status: Runtime Error

Solution code:
n, K = [int(a) for a in input().split()]
s = [[int(a) for a in input().split()] for _ in range(K)]

MOD = 998244353

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

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

print(dp[n] % MOD)

Submission status: Runtime Error

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

mod = 998244353

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

for i in range(n+1):
  for j in range(k):
    left = max(0, i-lr[j][1])
    right = max(0, i-lr[j][0]+1)
    
    dp[i] += sdp[right] - sdp[left]
  if i+1 <= n:
    sdp[i+1] = sdp[i]%mod + dp[i]%mod

print(dp%mod)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
S = []
for i in range(K):
    L, R = map(int, input().split())
    S += [i in range(L, R+1)]
A = [1]
for n in range(1,N):
    s = sum(A[n - i] for i in S if n - i >= 0) % 998244353
    A.append(s)
print(A[N-1])

Submission status: Runtime Error

Solution code:
def count(n, S, memo):
    if n < 0:
        return 0
    elif n == 1:
        return 1
    elif memo[n] > -1:
        return memo[n]
    else:
        x = 0
        for s in S:
            x += count(n - s, S, memo)
        memo[n] = x
        return memo[n]


N, K = map(int, input().split())
S = set()
for i in range(K):
    L, R = map(int, input().split())
    S = S | (set(range(L, R+1)))
memo = [-1] * (N + 1)
print(count(N, S, memo) % 998244353)

Submission status: Runtime Error

Solution code:
import math
import sys
import os
import numpy as np

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")
MOD = 998244353    

N,K = LI()
LRs = [LI() for _ in range(K)]

S = set()
for LR in LRs:
    for i in range(LR[0],LR[1]+1):
        S.add(i)

cell = [0]*(N)
cell[0] = 1

# Sa = sorted(list(S),reverse=True)
for i in range(N):
    for s in S:
        if i+s<N:
            cell[i+s]+=cell[i]


# for s in Sa:
#     i = 0
#     while i+s<N:
#         # print(i,s)
#         cell[i+s] += cell[i]
#         i += 1
#     print(s,cell)
ans = cell[-1]
print(ans)

Submission status: Runtime Error

Solution code:
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os
    import re
    with open(__file__) as f:
        source = f.read().split('###''nbacl')
    for s in source[1:]:
        s = re.sub("'''.*", '', s)
        sp = s.split(maxsplit=1)
        if os.path.dirname(sp[0]):
            os.makedirs(os.path.dirname(sp[0]), exist_ok=True)
        with open(sp[0], 'w') as f:
            f.write(sp[1])

    import nbmodule
    nbmodule.cc.compile()
    exit(0)

from nbmodule import solve
import numpy as np
i8 = np.int64
i4 = np.int32


def main():
    f = open('d4.txt')
    N, K = [int(x) for x in f.readline().split()]
    LR = np.fromstring(f.read(), i8, sep=' ').reshape((-1, 2)).T.copy()
    L = LR[0]
    R = LR[1]
    arg = np.argsort(L)
    left = L[arg]
    right = R[arg]
    w = right - left + 1
    ans = solve(N, left, w)
    print(ans)


if __name__ == '__main__':
    main()

'''
###nbacl nbmodule.py
import numpy as np
from numba import njit
from numba.types import i8, i4
from numba.pycc import CC
ni4 = np.int32
ni8 = np.int64
cc = CC('nbmodule')

MOD = 998244353


@cc.export('solve', (i8, i8[:], i8[:]))
def solve(N, left, w):
    l0 = w.max()
    dp_len = N + l0
    dp_prev = np.zeros(dp_len, ni8)
    dp_prev[l0] = 1
    dp = np.zeros(dp_len, ni8)
    left_min = left[0]
    ret = 0
    while l0 + left_min < dp_len:
        for k in range(left.shape[0]):
            pre = 0
            for i in range(l0 + left[k], dp_len):
                cur = pre + dp_prev[i - left[k]] - dp_prev[i - left[k] - w[k]]
                dp[i] += cur
                pre = cur
        ret += dp[-1]
        dp_prev, dp = dp, dp_prev
        dp_prev %= MOD
        dp.fill(0)
        l0 += left_min

    return ret % MOD

if __name__ == '__main__':
    cc.compile()
'''

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
x=998244353
S=[]
for i in range(K):
    l,r=map(int,input().split())
    for j in range(l,r+1):
      S.append(j)
S=list(set(S))
dp=[0 for i in range(N)]
for i in range(len(S)):
    dp[S[i]]=1
for i in range(N):
    for j in range(len(S)):
        if(i-S[j]>0):
            dp[i]+=dp[i-S[j]]
            dp[i]=dp[i]%x
print(dp[-1])

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
x=998244353
S=[]
for i in range(K):
    l,r=map(int,input().split())
    for j in range(l,r+1):
      S.append(j)
S=list(set(S))
dp=[0 for i in range(N)]
for i in range(len(S)):
    dp[S[i]]=1
for i in range(N):
    for j in range(len(S)):
        if(i-S[j]>0):
            dp[i]+=dp[i-S[j]]
            dp[i]=dp[i]%x
print(dp[-1])