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:
N,K = map(int,input().split( ))
a = [0 for _ in range(N+1)]
for _ in range(K):
    L,R = map(int,input().split( ))
    for i in range(L,R+1):
        a[i] += 1
b = [0 for _ in range(N+1)]
b[0] = 1
for i in range(1,N+1):
    for j in range(1,i+1):
        b[i] += b[i-j]*a[j]
print(b[N-1])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = set()
for i in range(k):
    l = list(map(int, input().split()))
    s = set(l+list(s))
dp=[0]*(n+1)
dp[1] = 1
p = 998244353

for i in range(1, n):
    for j in s:
        if i+j > n:
            continue
        dp[i+j] += (dp[i])
        dp[i+j] %= p

print(dp[n])

Submission status: Wrong Answer

Solution code:


def findtheways(N,K,S):
  # s is o add kr sorted
  dp=[0]*(N+1)
  dp[1]=1
  for i in range(2,N+1):
    for everyItem in S:
      if (i-everyItem)>0:
        dp[i]+=dp[i-everyItem]
  return dp[N]%998244353
N, K=map(int,input().split())
final_list=[]
while K>0:
  a=list(map(int,input().split()))
  final_list+=a
  K-=1

final_list=sorted(list(set(final_list)))

print(findtheways(N,K,final_list))

Submission status: Wrong Answer

Solution code:
n,k= list(map(int, input().split()))
INF=998244353
s=[]
for i in range(k):
    j,jj=map(int,input().split())
    s.append([l for l in range(j,jj+1)])
pattern=[0 for i in range(n)]
pattern[0]=1
ls=len(s)
memo=[0 for i in range(k)]
s.sort()
for i in range(1,n):
    tmp=0
    for index,j in enumerate(s):
        if i-j[0]<0:
            break
        elif i-j[-1]>0:
            memo[index]+=pattern[i-j[0]]
            memo[index]-=pattern[i-j[-1]-1]
            if memo[index]<0:
                memo[index]+=INF
        else:
            memo[index]+=pattern[i-j[0]]

        #tmp+=sum(pattern[max(i-j[-1],0):i-j[0]+1])
        memo[index]%=INF
    pattern[i]=sum(memo)
print(pattern[-1])

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
LR=set()
inf_=998244353
dp=[0]*(N+100)
dp[1]=1

for i in range(K):
    lr=list(map(int,input().split()))
    LR = LR |set(lr)
li=list(LR)
for i in range(2,N+1):
    for j in li:
        try:
            dp[i]+=dp[i-j]
        except IndexError:
            pass
print(dp[N]%inf_)

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=[0]*(n+1)
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:
def countWays(arr, m, N): 
  
    count = [0 for i in range(N + 1)] 
 
    count[0] = 1

    for i in range(1, N + 1): 
        for j in range(m): 
            if (i >= arr[j]): 
                count[i] += count[i - arr[j]] 
 
    return count[N] 
    
n,k = map(int,input().split())

lol = set()

d = []

while k > 0:
    l,r = map(int,input().split())
    lol.add(l)
    lol.add(r)
    
    k -= 1
    
d = list(lol)
m = len(d)

print(countWays(d,m,n))

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

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

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

print(dp[N-1])

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]
        ans[i+j]=ans[i+j]%998244353
print(ans[n-1]%998244353)

Submission status: Wrong Answer

Solution code:
def main():
    MOD = 998244353
    n, k = map(int, input().split())
    s = set()
    global ans
    
    for _ in range(k):
        l, r = map(int, input().split())
        for i in range(l, r+1):
            s.add(i)
    s = list(s)
    print(s)
    
    m = [0] * (n + 1)
    m[1] = 1
    for i in range(1, n+1):
        for j in s:
            if i+j <= n:
                m[i+j] += m[i]
        m[i] %= MOD
    print(m[n])

        
if __name__ == '__main__':
    main()

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

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] % 998244353
            else:
                return


d[N-1] = 1
for i in range(N-1, -1, -1):
    if d[i] > 0:
        func(i)

print(d[0] % 998244353)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

    def solve(self,n,nums):
        # print(self.memo)
        nums_cleaned = [i for i in nums if i <= n]
        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) for i in nums_cleaned])
                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:
temparr = input()
temparr = temparr.split()
n = int(temparr[0])
k = int(temparr[1])
dicts = {}
dp = [0 for _ in range(n + 2)]
dp[1] = 1 
arr = []
dicts = {}
for kk in range(k):
    temparr = input()
    temparr = temparr.split()
    f = int(temparr[0])
    l = int(temparr[1]) + 1 
    for i in range(f,l):
        if i not in dicts:
            dicts[i] = 1 
for key, value in dicts.items():
    arr.append(key)
arr = sorted(arr)
#print(arr)
for i in range(1, n + 1):
    if dp[i] == 0:
        continue 
    for j in arr:
        index = i + j 
        if index > n :
            break 
        dp[index] += dp[i]
print(dp[n])

Submission status: Wrong Answer

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

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

S.sort()

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

print(dp)

print(dp[-1])

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
dp[0] = 1
for i in range(N):
    for s in S:
        if i-s < 0:
            break
        dp[i] += dp[i-s]
        if dp[i] > 998244353:
            dp[i] -= 998244353
while dp[N-1] >= 998244353:
    dp[N-1] -= 998244353
print(dp[N-1])

Submission status: Wrong Answer

Solution code:
import heapq
n,k=map(int,input().split())
can=[]
you=[0]*(n+1)
for i in range(k):
    l,r=map(int,input().split())
    you[l]=1
    if r<n:
        you[r+1]=-1
for i in range(n):
    you[i+1]+=you[i]
for i in range(n):
    if you[i]:
        can.append(i)
table=[0]*n
table[0]=1
ka=[0]*(n+1)
ka[0]=1
que=[0]
heapq.heapify(que)
can.sort()
while que:
    now=heapq.heappop(que)
    ka[now]=0
    for j in can:
        if now+j>=n:
            break
        table[now+j]=(table[now+j]+table[now])%998244353
        if ka[now+j]==0:
            heapq.heappush(que,now+j)
            ka[now+j]=1
print(table[-1]%998244353)

Submission status: Wrong Answer

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

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;
dp = [0 for _ in range(n+1)]
for i in range(2,n+1):
  for lower in range(1,i):
    if boolean[lower]:  #start + lower
      start = i - lower
      dp[i]+= dp[start]
print(dp[n]%998244353)

Submission status: Wrong Answer

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

strides = set()
c = [0] * (n + 1)
c[1] = 1

for i in range(k):
  a, b = map(int, input().split())
  strides.add(a)
  strides.add(b)
  
for i in range(1, n + 1):
  for stride in strides:
    try:
      c[i + stride] += c[i]
    except:
      pass

print(c[-1] % 998244353)

Submission status: Wrong Answer

Solution code:
import numpy as np

mod = 998244353

N, K = map(int, input().split())
LR = []
lmin = float('inf')

for _ in range(K):
    l, r = map(int, input().split())
    LR.append((l, r))
    lmin = min(l, lmin)

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

for i in range(1, N+1, lmin):
    now = dp[i] % mod
    
    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())
lr=[list(map(int,input().split())) for _ in range(k)]
mod=998244353
dp2=[0]*n
dp2[0]=1
for i in range(1,n):
    dp2[i]+=dp2[i-1]
    for l,r in lr:
        if i-l>=0:
            dp2[i]+=dp2[i-l]
        if i-r>=0:
            dp2[i]-=dp2[i-r-1]
    dp2[i]%=mod
print((dp2[-1]-dp2[-2])%mod)

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
from numpy import *
N,K = map(int,input().split())
LR = [list(map(int,input().split())) for k in range(K)]
D = (N+2)*[0]
dp = (N+1)*[0]
dp[1] = 1
mod = 998244353

for L,R in LR:
  D[L]+=1
  D[R+1]-=1

D = cumsum(D)

for i in range(1,N+1):
  for j in range(1,i):
    if D[j]==1:
      dp[i] = (dp[i]+dp[i-j])%mod

print(dp)

Submission status: Wrong Answer

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

import itertools
l_r_list_1 = list(itertools.chain.from_iterable(l_r_list))

l_r_set=set(l_r_list_1)

mv_list=list(l_r_set)

dp = [0]*(n)

for i in range(n):
    for j in range(len(mv_list)):
        if i > mv_list[j]:
            dp[i] += dp[i - mv_list[j]]
        elif i == mv_list[j]:
            dp[i] += 1

print(dp[-1] % 998244353)

Submission status: Wrong Answer

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

S = []
for l,r in LR:
    for _ in range(l,r+1):
        S.append(_)
S = list(set(S))

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

Submission status: Wrong Answer

Solution code:
import collections
import math
import sys
sys.setrecursionlimit(10**7)
inf=998244353


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

for i in range(K):
    s1,s2=map(int,input().split())
    for j in range(s1,s2+1):
        SS.append(j)

# Driver program to test above function 

table = [0 for k in range(N-1)] 

for s in SS:
    if s<N-1:
        table[s-1]+=1
for i in range(0,N-1):
    for s in SS:
        if i+s<N-1:
            table[i+s]+=table[i]
            table[i+s]%=inf
print(table[-1]%inf)

Submission status: Wrong Answer

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


combinations = [0] * (N + 1)
combinations[1] = 1
S.sort()
for i in range(1, (N + 1 - S[0])):
    if combinations[i] == 0:
        break
    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: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 998244353

n, k = map(int, input().split())
dp = [0] * n
dp[0] = 1
dp[1] = -1 % MOD
delta = []
for _ in range(k):
    l, r = map(int, input().split())
    delta.append((l, 1))
    delta.append((r+1, -1 % MOD))

total = 0
for i in range(n):
    total += dp[i]
    total %= MOD
    for p, d in delta:
        if i + p >= n:
            break
        dp[i + p] += total * d
        dp[i + p] %= MOD
print(total % MOD)

Submission status: Wrong Answer

Solution code:
n,k = (int(x) for x in input().split())
s = []
for _ in range(k):
    a,b = (int(x) for x in input().split())
    s+=list(range(a,b+1))
    
mod = 998244353

l = [0]*(n)
min_num = min(s)
for i in range(min_num,n):
    for j in s:
        l[i] = (l[i]+(l[i-j])) % mod
    if i in s:
        l[i] += 1
print(l[n-1])

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
S = {}
for i in range(k):
  tmp = list(map(int,input().split()))
  lr = range(tmp[0],tmp[1]+1)
  S = set(lr).union(S)

MOD = 998244353

dp = [0]*(n+1)
if 1 in S:
  dp[1] = 1

for i in range(n+1):
  for j in S:
    if i-j > 0:
      dp[i] += dp[i-j]
print(dp[n]%MOD)

Submission status: Wrong Answer

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

d=[]

for i in range(k):
  l,r=map(int,input().split())
  if l not in d:
    d.append(l)
  if r not in d:
    d.append(r)
#print(d)
m=[0]*n
m[0]=1

for i in range(n):
  for j in range(len(d)):
    if (i+d[j])<n:
      m[i+d[j]]+=m[i]

#print(m)
print(m[n-1]%998244353)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from numba import njit, i8

@njit((i8[:], i8, i8[:] ), cache=True)
def call(cell, n, leap):
    for i in range(n):
        if cell[i]:
            for j in leap:
                if i + j < n:
                    cell[i+j] += cell[i]
    return cell

def main():
    n, k = map(int, sys.stdin.buffer.readline().split())
    leap = set()
    cell = np.array([0]*n, np.int64)
    cell[0] = 1 
    for x in sys.stdin.buffer.readlines():
        l, r = map(int, x.split())
        leap |= set(range(l,r+1)) 
    leap = np.array(list(leap))
    c = call(cell, n, leap)
    print(c[-1]%998244353)

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 = 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:
n , k = map(int, input().split())

li = [0]*(n+2)
lis=[]
lis2 =[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+1):
    if li[i]==1:
        lis.append(i)

for i in range(1,n):
    for j in lis:
        lis2[i]%=998244353
        lis2[i+j]+=lis2[i]

print(lis2[n]%998244353)

Submission status: Wrong Answer

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

s = [0 for _ in range(n + 1)]
s[1] = 1
for i in range(1, n):
    x = 0
    for l, r in seg:
        x += (s[max(0, i - l + 1)] - s[max(0, i - r)]) % MOD
        x %= MOD
    s[i + 1] = (s[i] + x) % MOD
print(s[-1] - s[-2])

Submission status: Wrong Answer

Solution code:
import collections

N, K = map(int, input().split())
L = list()
R = list()
for _ in range(K):
    line = list(map(int, input().split()))
    L.append(line[0])
    R.append(line[1])

S = collections.deque()
for left, right in zip(L, R):
    s = range(left, right+1)
    if len(S) == 0:
        S.extend(s)
    elif right < S[0]:
        S.extendleft(s[::-1])
    else:
        S.extend(s)
print(S)

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

Submission status: Wrong Answer

Solution code:
n,k = (int(x) for x in input().split())
s = []
for _ in range(k):
    a,b = (int(x) for x in input().split())
    s+=list(range(a,b+1))

mod = 998244353

l = [0]*(n)
min_num = min(s)
for i in range(min_num,n):
    for j in s:
        l[i] += (l[i-j])
    if i in s:
        l[i] += 1
    l[i] %= mod
print(l[n-1])

Submission status: Wrong Answer

Solution code:
(n,k),*e=[[*map(int,i.split())]for i in open(0)]
mod=998244353
a=[0]*n
a[0]=1
b=[]
e.sort()
for i,j in e:
    b+=range(i,j+1)
m=len(b)
if len(b)>n//2:
    c=range(1,n+1)
    c=set(c)-set(b)
    c=list(c)
    c.sort()
    b=c
for i in range(n):
    if a[i]==0:break
    for j in b:
        if i+j<n:
            a[i+j]+=a[i]
            a[i+j]%=mod
        else:break
print(pow(2,n-3,mod)-a[-1] if m>n//2 else a[-1])

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def soinsubunkai_e(n,m): #高速素因数分解 m[n]=nを割ることの出来る最小の素数
    a = set()
    i = 1
    while n>1:
        a.add(m[n])
        n=n//m[n]
    nokori=n
    a.add(nokori)
    return a

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def era(n): #b[n]=nを割ることの出来る最小の素数　の配列を生成　エラトステネスの篩
    b=[i for i in range(n+1)]
    for i in range(2,int(math.sqrt(n)+10)):
        j=1
        temp=i*j
        while temp<=n:
            b[temp]=min(i,b[temp])
            temp+=i
    return b


def main():
    #l,r,d=map(int,input().split())
    MODT=998244353
    n,k=map(int,input().split())
    step= set()
    for i in range(k):
        l,r=map(int,input().split())
        aa=[l+j for j in range(r-l+1)]
        aa=set(aa)
        step=step.union(aa)
    dp=[0 for i in range(n*2+2)]
    dp[1]=1
#    print(step)
    for i in range(1,n+1):
        for j in step:
            if i+j<=n:
                dp[i+j]+=dp[i]
                dp[i+j]%=MODT
            else:
                break
 #   print(dp)
    print(dp[n]%MODT)






if __name__ == "__main__":

    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    M = []
    mod = 998244353
    for i in range(K):
        a, b = map(int, input().split())
        M.append(a)
        M.append(b)
    M = set(M)
    dp = [0]*(N+1)
    dp[1] = 1
    for i in range(2,N+1):
        for s in M:
            if i-s >=0:
                dp[i] += dp[i-s]
    print(dp[N]%mod)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

li = [0]*(n+2)
lis=[]
lis2 =[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+1):
    if li[i]==1:
        lis.append(i)

for i in range(1,n):
    for j in lis:
        lis2[i+j]+=lis2[i]

print(lis2[n]%998244353)

Submission status: Wrong Answer

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)

print(s)

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

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
ra = range

def main():
    N, K = map(int, input().split())
    MOD = 998244353
    cand = set()
    for _ in range(K):
        L, R = map(int, input().split())
        A = set(ra(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())

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

class SegTree:
  #init(init_val, ide_ele): 配列init_valで初期化 O(N)
  def __init__(self, init_val, segfunc, ide_ele):
    #init_val: 配列の初期値
    #segfunc: 区間にしたい操作
    #ide_ele: 単位元
    #n: 要素数
    #num: n以上の最小の2のべき乗
    #tree: セグメント木(1-index)
    n = len(init_val)
    self.segfunc = segfunc
    self.ide_ele = ide_ele
    self.num = 1 << (n - 1).bit_length()
    self.tree = [ide_ele] * 2 * self.num
    # 配列の値を葉にセット
    for i in range(n):
      self.tree[self.num + i] = init_val[i]
    # 構築していく
    for i in range(self.num - 1, 0, -1):
      self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

  #update(k, x): k番目の値をxに更新 O(logN)
  def update(self, k, x):
    #k番目の値をxに更新
    #k: index(0-index)
    #x: update value
    k += self.num
    self.tree[k] = x
    while k > 1:
      self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
      k >>= 1

  #query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
  def query(self, l, r):
    #[l, r)のsegfuncしたものを得る
    #l: index(0-index)
    #r: index(0-index)
    res = self.ide_ele
    l += self.num
    r += self.num
    while l < r:
      if l & 1:
        res = self.segfunc(res, self.tree[l])
        l += 1
      if r & 1:
        res = self.segfunc(res, self.tree[r - 1])
      l >>= 1
      r >>= 1
    return res
  
#segfunc
def segfunc(x,y):
  return x+y #区間和
#ide_ele
ide_ele=0 #区間和

#初期化
seg=SegTree([0]*(N+1), segfunc, ide_ele)
seg.update(1,1)

for i in range(2,N+1):
  for l,r in lrlist:
    if i-l<1:
      continue
    elif i-r<1:
      left=1
      right=i-l
    else:
      left=i-r
      right=i-l
    
    current=seg.query(i,i+1)
    sum_intv=seg.query(i-r,i-l+1)
    seg.update(i,current+sum_intv)
    #print(i,left,right,current,sum_intv)
    
  seg_i=seg.query(i,i+1)
  seg.update(i,seg_i%MOD)
    
print(seg.query(N,N+1))

Submission status: Wrong Answer

Solution code:
from collections import deque
from typing import Collection

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

s = set()
for lri in lr:
    s |= lri
s = list(s)

"""dp = [0]*(n+10)
dp[0] = 1
q = deque([0])
while(q):
    print(dp)
    now = q.popleft()
    for si in s:
        if now+si < n:
            dp[now+si] += dp[now]
            q.append(now+si)
print(dp)
print(dp[n-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
#print(ans)
print(ans[-1]%mod)

Submission status: Wrong Answer

Solution code:
from bisect import*
n,k=map(int,input().split());D=[];S=[1]+[0]*~-n;m=998244353
for _ in "_"*k:D+=eval("[*range("+input().replace(" ",",")+"+1)]")
D.sort()
for i in range(2,n+1):
  for d in D[:bisect(D,i)]:S[i-1]+=S[i-d-1]
  S[i-1]%=m
print(S[-1])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
mod = 998244353
D = []
dp = [0] * (N+1)
for i in range(K):
    L, R = map(int, input().split())
    D.append([L, R])

dp[0] = 1
a = 0
for i in range(N):
    a += dp[i]
    a %= mod
    for d in D:
        if i + d[0] > N:
            continue
        dp[i + d[0]] += a
        if i + d[1] + 1 > N:
            continue

        dp[i + d[1] + 1] -= a

print(dp[N-1])

Submission status: Wrong Answer

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 + [a, b]

s = set(lis)

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

Submission status: Wrong Answer

Solution code:
def solve():
    N, K = map(int,input().split())
    L = []
    R = []
    S = set()
    MOD = 998244353
    for _ in range(K):
        l, r = map(int,input().split())
        L.append(l)
        R.append(r)

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

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

    for i in range(1,N+1):
        for s in S:
            if i+s >= N+1:
                break
            dp[i+s] += dp[i] % MOD
            dp[i+s] %= MOD
    
    print(dp[-1])
    
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# map(int, input().split())
mod = 998244353

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

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

kukans = list(sorted(kukans, key=lambda x:x[0]))

ruiseki_dp = [0]
for i in range(1,N+1):
    if i == 1:
        ruiseki_dp.append(1)
    else:
        # たどり着くためにできるマスの動き
        able_kukans = []
        for L,R in kukans:
            if R <= i-1:
                able_kukans.append([L,R])
            elif L <= i-1 < R:
                able_kukans.append([L,i-1])
                break
            else: # i-1 < L
                break
        
        next_dp = 0
        for L, R in able_kukans:
            next_dp = (next_dp+ruiseki_dp[i-L]-ruiseki_dp[i-R-1])%mod

        ruiseki_dp.append((ruiseki_dp[-1]+next_dp)%mod)
    
print(ruiseki_dp[-1]-ruiseki_dp[-2])

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

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

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

for i in range(2,N+1):
    for j in numlist:
        if j >= i:
            break
        dp[i] += dp[i-j]
    
print(dp[N] % 998244353)

Submission status: Wrong Answer

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

for _ in range(K):
  L, R = map(int, input().split())
  S.extend(range(L,R+1))
  
print(S)


DP =[0]*N
DP[0] = 1

for i in range(1,N):
  for j in S:
    if i >= j:
      DP[i] += DP[i-j]
      
print(DP[-1]%998244353)

Submission status: Wrong Answer

Solution code:
N,K=list(map(int,input().split()))
method=[]
for x in range(K):
	a,b=list(map(int,input().split()))
	method += list(range(a,b+1))
#print(method)
nums=[0]*(N+1)
nums[1]=1
for x in range(1,N):
	for step in method:
		if x+step>N:
			break
		nums[x+step]+=nums[x]
print(nums[N]%998244353)
print(nums)

Submission status: Wrong Answer

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

def input(): return sys.stdin.readline()[:-1]
mod = 10**9 + 7
mod2 = 998244353
def readInt():return int(input())
def readIntList():return list(map(int,input().split()))
def readStringList():return list(input())
def readStringListWithSpace():return list(input().split())
def readString():return input()

from itertools import accumulate
 
def execute():
    n,k = readIntList()
    s = set()
    for _ in range(k):
        l,r = readIntList()
        s.add(l)
        s.add(r)
    s = list(s)
    dp = [0]*(n+1)
    for i in s :
        dp[i] = 1
    # dp[0] = 1
    for val in range(1,n+1):
        for coin in s:
            if val >= coin:
                dp[val] += dp[val-coin]
    print(dp[n-1]%mod2)

    


    
 
if __name__ == "__main__":
    execute()