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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

class Rec_memo:
    def __init__(self):
        self.memo = {}

    def solve(self,n,nums):
        nums_cleaned = []
        for i in nums:
            if i <= n:
                nums_cleaned.append(i)
            else:
                break
        if n == 0 or nums_cleaned == []:
            return 0
        elif n == nums_cleaned[0]:
            return 1
        else:
            max_num = nums_cleaned[-1]
            if (n,max_num) in self.memo.keys():
                return self.memo[(n,max_num)]
            else:
                self.memo[(n,max_num)] = sum([self.solve(n-i,nums_cleaned) % 998244353 for i in nums_cleaned]) % 998244353
                return self.memo[(n,max_num)]

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

nums.sort()
rec_memo = Rec_memo()
out = rec_memo.solve(N,nums)
print(out % 998244353)

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    MOD = 998244353
    cand = set()
    for _ in range(K):
        L, R = map(int, input().split())
        A = set(range(L,R+1))
        cand |= A

    dp = [0] * (N + 5)
    dp[0] = 1
    for i in range(N):
        for j in cand:
            if i + j <= N:
                dp[i+j] += dp[i]
                dp[i+j] %= MOD
            else:
                break

    print(dp[N-1])
    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
MOD=998244353
N,K=map(int, input().split())
s=set()
for i in range(K):
    l,r=map(int, input().split())
    s.add(l)
    s.add(r)
a = list(s)
a.sort()
n = [0]*(N)
n[0]=1
for i in range(N-1):
    p = 0
    for j in a:
        if i + 1 >= j:
            p = (p+n[i-j+1])
    n[i+1] = p

print(n[-1]%MOD)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
L = [0] * K
R = [0] * K
S = set()
for k in range(K):
    L[k],R[k] = map(int,input().split())
for k in range(K):
    for n in range(L[k], R[k] + 1):
        S.add(n)
dp = [0] * (N+1)
dp[1] = 1
S = sorted(S)
for i in range(1,N+1,-1):
    for s in S:    
        if i-s <= 0:
            break
        dp[i] += dp[i-s]
        if dp[i] >= 498244353:
            dp[i] -= 998244353
while dp[N] >= 998244353:
    dp[N] -= 998244353
while dp[N] < 998244353:
    dp[N] += 998244353    
print(dp[N])

Submission status: Wrong Answer

Solution code:
def d_leaping_tak(MOD=998244353):
    from bisect import bisect_left, bisect_right
    N, K = [int(i) for i in input().split()]
    Ranges = sorted([[int(i) for i in input().split()] for j in range(K)])

    dp = [0] * (N + 1)  # dp[i]: マス i への行き方
    dp[1] = 1
    cumsum_dp = dp[:]
    for i in range(2, N + 1):
        for l, r in Ranges:
            if i - l < 0:
                continue
            if i - r < 0:
                r = i

            dp[i] += cumsum_dp[i - l] - cumsum_dp[i - r - 1]
        dp[i] %= MOD
        cumsum_dp[i] = cumsum_dp[i - 1] + dp[i]

print(d_leaping_tak())

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
dp = [0] * N
dp[0] = 1
L = [0] * K
R = [0] * K
mod = 998244353

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

for i in range(1, N):
    # マスiにたどり着くためのパターン数を数える
    cnt = 0
    for j in range(K):
        # start = min(0, i-L[j])
        # end = R[j]
        # sum(dp[start:end]) % mod
        for k in range(L[j], R[j] + 1):
            if i - k >= 0:
                cnt += dp[i - k] & mod
            else:
                continue
    dp[i] = cnt

print(dp[N - 1])

Submission status: Wrong Answer

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

idou = set()
for i in range(0, K):
    L, R = map(int, input().split())
    idou = idou | set(range(L, R + 1))

idou = list(idou)

moves = [0] * N
moves[0] = 1
for i in range(0, N):
    for j in range(0, len(idou)):
        if i + idou[j] < N:
            moves[i + idou[j]] += moves[i]

print(moves)
print(moves[N - 1] % 998244353)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

a_array = array = np.zeros(N)
for k in range(K):
  L, R = map(int, input().split())
  a1 = np.zeros(L-1)
  a2 = np.ones(R-L+1)
  a3 = np.zeros(N-R)
  a = np.concatenate([a1, a2, a3], 0)
  a_array += a
a_array = np.where(a_array > 0, 1, 0)


array = np.zeros(N)
array[0] = 1
for i in range(N):
  if i == 0:
    pass
  else:
    p = int(i)
    calc = a_array[:p]
    total = np.sum(array[:p] * calc[::-1])
    #print('ここから')
    #print(array[:p])
    #print(calc[::-1])
    #print(total)
    array[p] = total
print(int(array[-1]) % 998244353)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
d = list(list(map(int,input().split())) for _ in range(k))
mod = 998244353
d = list(set(sum(d,[])))

def leap(N,D):
    dp = [0]*N # dp[i]はiへ行く場合の数 
    dp[0]=1
    for i in range(N):
        for j in D:
            if i-j >=0:
                dp[i] += dp[i-j]
    return dp
print(leap(n,d)[-1]%mod)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int, input().split())
MOD = 998244353
dp = [0 for _ in range(N)]
dp[0] = 1

L, R = [0 for _ in range(K)], [0 for _ in range(K)]
for k in range(K):
    L[k], R[k] = map(int, input().split())

for i in range(N):
    tmp = dp[i]
    for k in range(K):
        # dp[min(i+L[k], N-1):min(i+R[k]+1, N)] += dp[i]
        for d in range(min(L[k], N-1-i), min(R[k]+1, N-i)):
            dp[i+d] += tmp
            dp[i+d] %= MOD

ans = dp[N-1] % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    mod = 998244353;
    N, K = map(int, input().split())
    S = set()
    for _ in range(K):
        L, R = map(int, input().split())
        S.add(L)
        S.add(R)

    ans = [0 for _ in range(N+1)]
    ans[1] = 1
    for n in range(2, N+1):
        for num in S:
            if n - num >= 1:
                ans[n] += ans[n - num]
                ans[n] %= mod

    print(ans[N])

main()

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int, input().split())
MOD = 998244353
dp = [0 for _ in range(N)]
dp[0] = 1

L, R = [0 for _ in range(K)], [0 for _ in range(K)]
for k in range(K):
    L[k], R[k] = map(int, input().split())

for i in range(N):
    tmp = dp[i]
    for k in range(K):
        # dp[min(i+L[k], N-1):min(i+R[k]+1, N)] += dp[i]
        for d in range(min(i+L[k], N-1), min(i+R[k]+1, N)):
            dp[d] += tmp
            dp[d] %= MOD

ans = dp[N-1] % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
l = input()
N = int(l.split(" ")[0])
K = int(l.split(" ")[1])


ll = [input() for i in range(K)]

a_list = []
for llel in ll:
    a_list += list(range(int(llel.split(" ")[0]), int(llel.split(" ")[1])+1))

a_list.sort()
#print(a_list)

e = [0] * len(a_list)
maxe = [0] * len(a_list)
for i in range(len(a_list)):
    if (N-1) % a_list[i] == 0:
        maxe[i] = (N-1) // a_list[i]
    else:
        maxe[i] = (N - 2) // a_list[i]

#print(e)
##print(maxe)

def ddot():
    dp = 0
    for i in range(len(e)):
        dp += e[i] * a_list[i]
    return dp

ans = 0
while(True):
    ddd = ddot()
    if ddd == N - 1:
        ans += 1
    #print(str(e) + " " + str(ddd))
    for i in range(len(e)):
        if e[i] < maxe[i]:
            e[i] += 1
            break
        else:
            if i == len(e) - 1:
                # true end
                print(ans)
                quit()
                break
            else:
                e[i] = 0

#print(ans)

Submission status: Wrong Answer

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):
    if a_list[i] == 0:
        continue
    for l, r in s_list:
        if i + l > n:
            continue
        """
        if i + r > n + 1:
            a_list[(i+l):(n+1)] += a_list[i]
        else:
        """
        a_list[(i+l):(i+r)] += a_list[i]
print(a_list[n] % 998244353)

Submission status: Wrong Answer

Solution code:
n,k = input().split()
n = int(n)
k = min(int(k),10)
s = []
for j in range(k):
    ins = input().split()
    s.append(int(ins[0]))
    s.append(int(ins[1]))
s = list(set(s))
ans = [0]*(n+1)
ans[1]=1
m = 998244353
for j in range(2,n+1):
    for k in s:
        if(k>=j):
            pass
        else:
            ans[j]=(ans[j]%m+ans[j-k]%m)%m
print(ans[-1]%m)

Submission status: Wrong Answer

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

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

# LR = [list(map(int,input().split())) for i in range(N)]
dp = [0] * (N + 1)
dp[0] = 1
for i in range(1, N):
    for d in LR:
        if i - d < 0: break
        dp[i] += (dp[i - d]) % MOD
print(dp[N-1] % MOD)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

mod = 998244353
dp = np.zeros(N)
dp[0] = 1

# O(N)で解く！
# N-1個目のマスまでdp
for i in range(N-1):
  for j in range(K):
    L = X[j][0]
    R = X[j][1]
    if R <= N-1-i:
      dp[i+L:i+R+1] += dp[i]
    else:
      dp[i+L:] += dp[i]
      
ans = int(dp[N-1]) % mod
print(ans)

Submission status: Wrong Answer

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

mod=998244353
dp=[0]*(N)
dp[0]=1
S=[]

for x in range(0,K):
	a,b=input().split(' ')
	a=int(a)
	b=int(b)
	for y in range(a,b+1):
		S.append(y)

for x in range(1,N):
	for y in S:
			dp[x]+=dp[x-y]
			dp[x]%=mod

print(dp[N-1])

Submission status: Wrong Answer

Solution code:
import subprocess
import os
import time


import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

# input = sys.stdin.readline


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

    s = {}
    for i in range(k):
        a, b = map(int, input().split())

        for x in range(a, b+1):
            s[x] = 1

    steps = list(s.keys())

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

    for i in range(1, n):
        if arr[i] == 0:
            continue

        for x in steps:
            if i + int(x) <= n:
                arr[i+x] += arr[i]
            else:
                break

    print(arr[n] % mod)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
allowed_jump = []
for i in range(k):
    l, r = map(int, input().split())
    allowed_jump.extend([l+i for i in range(r-l+1)])
    allowed_jump.sort()
print(allowed_jump)
ans = [0 for i in range(n)]
ans[0]=1
for i in range(n):
    for jump in allowed_jump:
        if i-jump>= 0:
            ans[i] += ans[i-jump]
print(ans[n-1]%998244353)

Submission status: Wrong Answer

Solution code:
import sys


def main():

    input = sys.stdin.readline

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

    S = set()

    mod = 998244353

    for i in range(K):
        l,r = map(int,input().split())

        for i in range(l,r+1):
            S.add(i)

    masu = [0] * N

    masu[0] = 1

    for i in range(N):
        for j in S:
            if i+j < N:
                masu[i+j] += masu[i]
                masu[i+j] %= mod
            else:
                break


    print(masu[N-1] % mod)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
ans=[0]*(n+1)
ans[1]=1
cnt=[]
for i in range(k):
    l,r=map(int,input().split())
    for j in range(l,r+1):
        cnt.append(j)
cnt.sort()
cnt2=1
cnt3=0
mod=998244353
if len(cnt)==n:
    print(pow(2,n-2,mod))
elif len(cnt)==n-1 and cnt[-1]==n-1:
    print(pow(2,n-2,mod))
else:
    for i in range(1,n):
        for j in range(len(cnt)):
            if i+cnt[j]>n:
                cnt=cnt[:j]
                break
            ans[i+cnt[j]]+=ans[i]
            ans[i+cnt[j]]%=mod
        if j==0:
            break
    print(ans[n])

Submission status: Wrong Answer

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

x=[]
for i in range(K):
    x.append(list(map(int, input().split())))

lr = []
def hanni(l,r):
    for i in range (l,r+1):
        lr.append(i)
    return lr

for j in range (K):
    hanni(x[j][0],x[j][1])

a = list(set(lr))


#ここまで入力処理
#ここからdp

def bubunwa(a,N):
  p=998244353
  n=len(a)
  dp=[[0 for i in range(N+1)] for j in range(n+1)]
  dp[0][0]=1

  for i in range(n):
    for j in range(N+1):
      if a[i]<=j:  
        dp[i+1][j]=dp[i][j-a[i]]+ dp[i][j]% p
      else: 
        dp[i+1][j]=dp[i][j]%p
  return dp[n][N]


print(bubunwa(a,N-1))

Submission status: Wrong Answer

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

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

area.sort()
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] += d[pos-i] % 998244353
            else:
                return


for i in range(1, N):
    func(i)
    print(d)

print(d[N-1] % 998244353)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
p = 998244353
dx = [0]*n
for i in range(k):
    l,r = map(int,input().split())
    for j in range(l-1,r):
        dx[j] = 1

dp = [0]*n
dp[0]=1
for i in range(1,n):
    for j in range(i+1):
        if dx[j]==1:
            dp[i] += dp[i-(j+1)]%p
            #print(dp)
    else:
        dp[i]=dp[i]%p
print(dp[n-1])

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split(" "))
a=[]
d=[]
e=[]
for k in range(K):
    l,r=map(int,input().split(" "))
    d.append(l)
    e.append(r)
d.sort()
e.sort()
for k in range(K):
    a+=list(range(d[k],e[k]+1))
a.sort()
b=[0 for i in range(a[-1]-1)]
b.append(1)
for i in range(N-1-a[0]):
    b.append(0)
    for j in a:
        b[-1]+=b[-j-1]
for i in range(a[0]):
    b.append(0)
for j in a:
        b[-1]+=b[-j-1]  
print(b[-1]%998244353)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = []
for j in range(K):
    S.append(list(map(int, input().split())))

m =  998244353

print(S)

dp = [0] * N
dp[0] = 1
sum_of_region = [0] * K
for i in range(1, N):
    for j in range(K):
        if i - S[j][0] >= 0:
            sum_of_region[j] += dp[i - S[j][0]]
        if i - S[j][1] - 1 >= 0:
            sum_of_region[j] -= dp[i - S[j][1] - 1]
        dp[i] += sum_of_region[j] % m
        dp[i] %= m
    print(i, dp, sum_of_region)

ans = dp[N - 1]
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    waru = 998244353
    n, k = map(int, input().split())
    move_set = set([])

    for i in range(k):
        a, b = map(int, input().split())
        move_set.add(a)
        move_set.add(b)
    sorted_set = sorted(move_set)
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n+1):
        cnt = 0
        for num in sorted_set:
            if num > i-1:
                break
            else:
                dp[i] += dp[i-num]

    print(dp[-1]%waru)

            
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

for i in range(K):
    l, r = map(int, input().split())
    D.append((l, r))

dp = [0] * N
dp[0] = 1
for i in range(1, N):
    for l, r in D:
        if i - l < 0:
            continue
        r = max(0, i - r)
        l = i - l + 1
        dp[i] += (dp[i] + sum(dp[r:l])) % MOD

print(dp[N-1])

Submission status: Wrong Answer

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

LR = [list(map(int, input().split())) for i in range(K)]
S = set()
for i in LR:
    S.add(i[0])
    S.add(i[1])
L = list(S)

dp = [0 for i in range(N)]
dp[0] = 1
for i in range(1, N):
    t = [j for j in L if j <= i]
    for j in t:
        dp[i] += dp[i-j]

print(dp[-1] % 998244353)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)

MOD = 998244353 
N, K = [int(i) for i in input().split()]
k = []
vals = []
for i in range(K):
  v = [int(i) for i in input().split()]
  vals.extend([*range(v[0], v[1] + 1)])
vals.sort()

d  = {}

def helper(n):
  if n in d:
    return d[n]
  if n == 0:
    return 1
  if n < vals[0]:
    return -1
  count = 0
  for v in vals:
    if n < v:
      break
    r = helper(n - v)
    if r != -1:
      count += r
      count %= MOD
  d[n] = count
  return count
 
print(helper(N - 1))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = set()
for _ in range(K):
    l, r = map(int, input().split())
    S = S | set(range(l, r + 1))
mod = 998244353

S_max = max(S)
dp = [0 for _ in range(2 * N)]
for s in S:
    dp[s + 1] = 1
for i in range(N + 1):
    for s in S:
        dp[i] += dp[i - s]
print(dp[N] % mod)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

s.sort()

dp = np.zeros(n * 2)
dp[1] = 1

for i in range(1, n):
    for l, r in s:
        dp[i + l:i + r + 1] += dp[i]
        dp[i + l:i + r + 1] %= mod

print(dp[n] % mod)

Submission status: Wrong Answer

Solution code:
def resolve():
    n, k = map(int, input().split())
    mod = 998244353
    dp = [0] * (3*n)
    imos = [0] * (3*n)
    lr = []
    for i in range(k):
        l, r = map(int, input().split())
        lr.append((l, r+1))
    for l, r in lr:
        imos[l] = 1
        imos[r] = -1
    now = 0
    for i in range(1, n):
        now += imos[i]
        now %= mod
        dp[i] = now
        for l, r in lr:
            imos[min(i+l, n+2)] += now
            imos[min(i+r, n+2)] += -1*now
    print(dp[n-1]%mod)
resolve()

Submission status: Wrong Answer

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):
    if a_list[i] == 0:
        continue
    for l, r in s_list:
        if i + l > n:
            continue
        if i + r > n + 1:
            a_list[(i+l):(n+1)] += a_list[i]
        else:
            a_list[(i+l):(i+r)] += a_list[i]
print(a_list[n] % 998244353)

Submission status: Wrong Answer

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

dp = [0] * (n + 1)

dp[0] = 0; dp[1] = 1

for i in range(2, n+1):
    dp[i] = dp[i-1]
    for x, y in a:
        l = i - y; r = i - x
        l = max(l, 0); r = min(r, i-1)
        dp[i] = (dp[i] + (dp[r] - (dp[l - 1] if l > 0 else 0))) % MOD
            
print(dp[-1] - dp[-2])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b
def ceil(x):
    return math.ceil(x)
def floor(x):
    return math.floor(x)

def main():
    mod = 998244353
    N, K = map(int, input().split())
    L = [0] * K
    R = [0] * K
    for i in range(K):
        L[i], R[i] = map(int, input().split())

    S = set()
    for i in range(K):
        for j in range(L[i], R[i] + 1):
            S.add(j)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
div = 998244353
n, k = map(int, input().split())
dp = [0] * (n + 1)
S = set()
for i in range(k):
    l, r = map(int, input().split())
    for x in range(l, r+1):
        S.add(x)
dp[1] = 1
for i in range(2, n+1):
    for s in S:
        idx = i - s
        if idx < 1:
            break
        dp[i] += dp[idx]
        dp[i] %= div
print(dp[-1])

Submission status: Wrong Answer

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

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

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

    # Cumulative Sum
    dp = [0] * n
    dp[0] = 1
    dp[1] = -1
    for i in range(n):
        dp[i] += dp[i-1]
        dp[i] %= mod
        for l, r in lr:
            if i + l < n:
                dp[i + l] += dp[i]
                dp[i + l] %= mod
                if i + r < n:
                    dp[i + r] -= dp[i]
                    dp[i + r] %= mod

    print(dp[n-1])

main()

Submission status: Wrong Answer

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

#import
#import math
#import numpy as np
#= int(input())
#= input()
modnum = 998244353

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

def mod(num):
    return num % modnum

S = []

for l, r in LR:
    for i in range(l, r + 1):
        if not i in S:
            S.append(i)

dp = [0] * N

dp[0] = 1

for i in range(1, N):
    for s in S:
        if not s > i:
            dp[i] = mod(dp[i] + dp[i - s])
        else:
            break

print(dp[N-1])

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    
    n,k = map(int,input().split())
    tmpset = set()
    for _ in range(k):
        morty,morty1= map(int,input().split())
        for i in range(morty,morty1+1):
            tmpset.add(i)
        
    dp = [0]*(n+1)
    dp[0] = 1
    for i in range(len(dp)):
        if(dp[i]>0):
            for tmp in tmpset:
                if tmp+i<=n:
                    dp[tmp+i]+=dp[i]
                    dp[tmp+i]%=998244353
    print(dp)
    print(dp[n-1])


        


    




















if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
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 = np.array(list(set(s)))

dp = np.array([0] * (2 * n))
dp[0] = 1

# s = np.array(sorted(list(s)))

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

print(dp[n-1]%mod)

Submission status: Wrong Answer

Solution code:
mod=998244353
n,k=map(int,input().split())
s=set()
for i in range (k):
    x,y=map(int,input().split())
    s.update([x,y])

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


for i in range (2,n+1):
    x=0
    for val in s:
        if (i-val)<0:
            continue
        x+=dp[i-val]
    if x<mod:
        dp[i]=x
    else:
        dp[i]=x%mod

print (dp[n])

Submission status: Wrong Answer

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):
    if a_list[i] == 0:
        continue
    for l, r in s_list:
        if i + l > n:
            continue
        if i + r > n:
            a_list[(i+l):(n+1)] += a_list[i]
        else:
            a_list[(i+l):(i+r)] += a_list[i]
print(a_list[n] % 998244353)

Submission status: Wrong Answer

Solution code:
N, K=map(int, input().split())
wa = set([])
for _ in range(K):
  l, r =map(int, input().split())
  [wa.add(i) for i in range(l,r+1)]
wa = sorted(list(wa))
if wa[0]!=1:
  print(0)
  exit()
from collections import deque
wa = deque(wa)
dp = [0]*N
dp[0]=1
koma = wa.popleft()
sakanoboru = []
waru = 998244353
for i in range(1,N):
  if koma == i:
    sakanoboru.append(koma)
    if wa: koma = wa.popleft()
  for j in sakanoboru:
    dp[i]+=dp[i-j]%waru
print(dp[-1]%waru)

Submission status: Wrong Answer

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

dp = [[-1]*(N) for _ in range(len(S)+1)]
dp[0][0] = 0
for i in range(len(S)):
  for j in range(N):
    if dp[i][j] == -1:
      continue
    n = 1
    while (j + S[i]*n) < N:
      dp[i + 1][j + S[i]*n] = max(dp[i + 1][j + S[i]*n], dp[i][j] + 1)
      dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
      n += 1
ans = 0
for i in range(len(S)+1):
  if dp[i][N-1] != -1:
    ans += dp[i][N-1]%MOD
print(ans%MOD)

Submission status: Wrong Answer

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))
dp[1] += 1

for i in range(1, N+1):
    now = dp[i] % mod
    if not now:
        break
    for l, r in LR:
        try:
            dp[i+l:i+r+1] += now
        except:
            break

print(dp[-1] % mod)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
mod=998244353
step=set()
for i in range(k):
    l,r=map(int,input().split())
    for j in range(l,r+1):
        step.add(j)
step=list(step)
dp={}
for i in range(n+max(step)):
    dp[i]=0
dp[0]=1
for i in range(n):
    for x in step:
        if i+x>n:
            break
        dp[i+x]+=dp[i]
        dp[i+x]%=mod
print(dp[n-1])

Submission status: Wrong Answer

Solution code:
n,k = tuple(map(int,input().split()))
boolean = [False for _ in range(n+1)]
for _ in range(k):
  l,r = tuple(map(int,input().split()))
  for num in range(l,r+1):
    boolean[num] = True;
FINAL = [i for i in range(len(boolean)) if boolean[i]]
dp = [0 for _ in range(n+1)]
for i in range(2,n+1):
  for lower in FINAL:  #optimized!
    if boolean[lower]:  #start + lower
      start = i - lower
      if start >= 1:
      	dp[i]+= dp[start]
print(dp[n]%998244353)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
def main():
    import numpy as np

    N, K = map(int, input().split())
    S = set()
    for _ in range(K):
        l, r = map(int, input().split())
        for n in range(l, r + 1):
            S.add(n)
    MOD = 998244353

    dp = np.zeros(N, dtype=np.int64)
    dp[0] = 1
    for i in range(N):
        for d in S:
            dp[i] += dp[i - d] % MOD
    print(dp[-1] % MOD)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

S.sort()
A = [1]
n = 1
while n <= N - 1:
    for i in S:
        s = sum(A[n - i] for i in S if n - i >= 0) % 998244353
        A += [s]
        s = 0
        n += 1
        
print(S)
print(A[N-1])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
step = []
for i in range(k):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        step.append(j)
step.sort()
print(step)
lg = len(step)
dp = [0 for _ in range(n + 1)]
dp[1] = 1
for i in range(n + 1):
    for j in step:
        if j < i:
            dp[i] += dp[i - j] 
        else:
            break

print(dp[n]% 998244353)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

li = np.array([0]*(n+2))
lis2 =np.array([0]*(3*n))
lis2[1]=1

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

for i in range(1,n+1):
    li[i]+=li[i-1]

for i in range(1,n):
    lis2[i]%=998244353
    lis2[i:i+n+2]+=li*lis2[i]

print(lis2[n]%998244353)

Submission status: Wrong Answer

Solution code:
import sys
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 998244353
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,K = IL()
lr = [IL() for i in range(K)]
lr.sort()

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

for i in range(2,N+1):
  tmp = 0
  for l,r in lr:
    if tmp >= r:
      continue
    elif l <= tmp < r:
      l = tmp+1
    if 1 <= i-l:
      dp[i] += data[i-l] - data[max(i-r-1, 0)]
  data[i] = (data[i-1] + dp[i]) %mod
print(dp[N])

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=[]
for _ in range(k):
    l,r=map(int,input().split())
    temp=list(range(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]%99824435
    for j in s:
        ans[i+j]+=ans[i]
print(ans[n-1]%998244353)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
s = []
for _ in range(k):
    a,b = map(int,input().split())
    for i in range(a,b+1):
        s.append(i)
goal = n-1
flist = [0 for _ in range(n)]#flist[i]でf(i)の値

#t = [1,2,3,5,6,7,8,10,11,12,13,14,15]
#t = [1,2]

flist[0] = 1
for current in range(n):
    if flist[current] == 0:
        for num in s:
            if current+num <= n-1:
                flist[current+num] += flist[current]

print(flist[-1]%998244353)

Submission status: Wrong Answer

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    mod = 998244353
    n, k = map(int, input().split())
    dp = [0] * n
    dp[0] = 1
    s = [tuple(map(int, input().split())) for _ in range(k)]
    total = 0
    for i in range(n - 1):
        total = (total + dp[i]) % mod
        for l, r in s:
            if i + l < n:
                dp[i + l] += total
                if i + r + 1 < n:
                    dp[i + r + 1] -= total
    print(dp[-1])


if __name__ == '__main__':
    resolve()