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())
li = []
for i in range(K):
  l, r = map(int, input().split())
  for j in range(l, r+1):
    li.append(j)
li.sort()
    
ans = [0] * (N+1)
ans[1] = 1
for i in range(1, N+1):
  if ans[i] > 0:
    for n in li:
      if i+n <= N:
        ans[i+n] += ans[i]
print(ans[-1])

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
import heapq
import cProfile
from collections import Counter, defaultdict, deque
from functools import reduce
import math
import threading
import sys
import time


def get_int(): return int(stdin.readline().strip())


def get_tuple(): return map(int, stdin.readline().split())


def get_list(): return list(map(int, stdin.readline().split()))

mod = 998244353
n,k = get_tuple()
st = list()
for _ in range(k):
    x,y = get_tuple()
    st.append([x,y])

dp = dict()
dp[0] = 1
pref_sum = 1
last_val = 0
for i in range(1,n):
    curr_sum = 0
    for x,y in st:
        if i-x>=0:
            curr_sum += dp[i-x]
        if i - y >= 1:
                curr_sum -= dp[i - y - 1]
    pref_sum = (curr_sum+pref_sum)%mod
    dp[i]=pref_sum
diff = (dp[n-1]-dp[n-2])
if diff>0:
    print(diff%mod)
else: print(0)

Submission status: Wrong Answer

Solution code:
def inc(v):
  for x in lr:
    if (v>=x[0]) & (v<=x[1]):
      return True
  return False

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

x = [1]
for i in range(1,n):
  val = 0
  for j in range(1,min(i,lrmax) + 1):
    if inc(j):
      val += x[-j] % 998244353
  x.append(val)
print(x[-1])

Submission status: Wrong Answer

Solution code:
# ####################################################################
# import io
# import sys
# _INPUT = """\
# 7 1
# 1 3
# """
# sys.stdin = io.StringIO(_INPUT)
####################################################################
import sys
def _p(*_a):
  #return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
####################################################################
def _pa(_aa):
  #return
  for _a in _aa: _p(_a)
####################################################################
N, K = map(int, input().split())

MOD = 998244353
ans = 0

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

A.sort()

_p(N,K,A)

M = [0] * (N + 1)
M[1] = 1
for m in range(1,N+1):
  for a in A:
    p = m + a
    _p(m,a,p,M)
    if p > N: break
    M[p] += M[m]
    M[p] = M[p] % MOD

_p(M)
print(M[N] % MOD)
# exit(0)

M = [0] * (N + 1)
for n in range(2, N+1):
  # print(n)
  if M[n] > 0: continue

  for a in A:
    p = n - a
    if p == 1: M[n] += 1
    if p <= 1: break
    M[n] += M[p] % MOD
    M[n] = M[n] % MOD

_p(M)
print(M[N] % MOD)

Submission status: Wrong Answer

Solution code:
def resolve():
    n, k = map(int, input().split())
    S = []
    for _ in range(k):
        l1, r1 = map(int, input().split())
        S.append(l1)
        S.append(r1)
    S = list(set(S))

    dp = [[0 for i in range(n + 1)] for j in range(len(S) + 1)]
    for i in range(len(S) + 1):
        dp[i][1] = 1
    for i in range(1, len(S) + 1):
        for j in range(2, n + 1):
            if j - S[i - 1] >= 0 and dp[i][j - S[i - 1]] > 0:
                dp[i][j] = dp[i][j - S[i - 1]] + dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j]

    print(dp[-1][n] % 998244353)

resolve()

Submission status: Wrong Answer

Solution code:
import numpy as np
n, k = map(int, input().split())
dp = np.array([0 for i in range(n)])
 
s = []
for i in range(k):
  l, r = map(int, input().split())
  s.append([l,r])
  
dp[0] = 1
for i in range(n):
  for l,r in s:
    dp[i+l:i+r] = (dp[i+l:i+r] + dp[i]) % 998244353

print(dp[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

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

D = []

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

    for i in range(L, R+1):
        D.append(i)

D.sort()

dp = np.zeros(300000)
dp[1] = 1

for d in D:
    for i in range(1, N//d):
        dp += np.roll(dp, i * d)
    dp %= 998244353

print(int(dp[N]))

Submission status: Wrong Answer

Solution code:
def main():

    m = 998244353

    n,k = tuple([int(t)for t in input().split()])

    dp = [0]*(n+2)
    imos = [0]*(n+2)

    dp[1] = 1
    imos[1] = 1
    imos[2] = -1

    pairs = []

    for i in range(k):
        p = tuple([int(t)for t in input().split()])
        pairs.append(p)
    
    state = 0
    for i in range(1,n+1):
        state += imos[i]
        dp[i] = state % m
        if state == 0:
            continue

        for l,r in pairs:
            if i+l>n:
                break
            left = i+l
            right = min(i+r+1,n+1)
            imos[left] += dp[i]
            imos[right] -= dp[i]
    
    print(dp[n])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K = [int(a) for a in input().split()]
LR = []
for _ in range(K):
    L,R = [int(a) for a in input().split()]
    LR.append([L,R])
dp = [0]*N
dp[0] = 1
f = 998244353
for i in range(1,N):
    for j in range(len(LR)):
        if i-LR[j][1] >= 0:
            dp[i] += sum(dp[i-LR[j][1]:i-LR[j][0]+1]) %f
        elif i-LR[j][0] >= 0: 
            dp[i] += sum(dp[:i-LR[j][0]+1]) %f
print(int(dp[-1]))

Submission status: Wrong Answer

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

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

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

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

# mS[n] := patterns of move +n
mS = [0] * (maxS + 1)
mS[0] = 1
for i in range(maxS):
    for s in S:
        if i + s < maxS + 1:
            mS[i + s] += mS[i]
# print(mS)
# exit()

dp = mS[:-1].copy()
dpp = []
for dpi in dp:
    dpp.append([dpi])
# print(dpp)

mat = [[0] * maxS for _ in range(maxS)]
for i in range(maxS):
    for s in S:
        if i + s - 1 < maxS:
            mat[i][i + s - 1] = 1
# pl(mat)


def mat_mul(a, b):
    I, J, K = len(a), len(b[0]), len(b)
    c = [[0] * J for _ in range(I)]
    for i in range(I):
        for j in range(J):
            for k in range(K):
                c[i][j] += a[i][k] * b[k][j]
            c[i][j] %= MOD
    return c


def mat_pow(x, n):
    y = [[0] * len(x) for _ in range(len(x))]

    for i in range(len(x)):
        y[i][i] = 1

    while n > 0:
        if n & 1:
            y = mat_mul(x, y)
        x = mat_mul(x, x)
        n >>= 1

    return y


ans = mat_mul(mat_pow(mat, N - maxS), dpp)
# pl(ans)
print(ans[0][0])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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
dp[1] = 1
for i in range(1, n-1):
    tmp = 0
    for j in range(k):
        l, r = sec[j]
        if (i + 1) - l >= 0:
            tmp = (tmp + dp[i+1-l]) % mod
        if i - r >= 0:
            tmp = (tmp - dp[i-r]) % mod
    
    dp[i+1] = (dp[i] + tmp) % mod

print(dp[n-1])

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

mod = 998244353

# How many are there to climb
step = [0] * (n+1)


for i in range(1,n+1):
    for s in S:
        if i+s<=n:
            step[i+s]+=1
print(step[n])

Submission status: Wrong Answer

Solution code:
def resolve():
    n, k = map(int, input().split())
    S = []
    for _ in range(k):
        l1, r1 = map(int, input().split())
        S.append(l1)
        S.append(r1)
    S = list(set(S))

    dp = [[0 for i in range(n + 1)] for j in range(len(S) + 1)]
    for i in range(len(S) + 1):
        dp[i][1] = 1
    for i in range(1, len(S) + 1):
        for j in range(2, n + 1):
            if j - S[i - 1] >= 0 and dp[i][j - S[i - 1]] > 0:
                dp[i][j] = dp[i][j - S[i - 1]] + dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j]

    print(dp[-1][n])

resolve()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list([1]+[0]*(n-1))
lst=[]
for i in range(k):
    x,y=map(int,input().split())
    lst+=list(range(x,y+1))

from functools import lru_cache
@lru_cache(maxsize = None)
def f():
    for j in lst:
        if j<=i:a[i]+=a[i-j]
for i in range(1,n):f()
print(a[-1]%998244353)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K = [int(a) for a in input().split()]
LR = []
for _ in range(K):
    L,R = [int(a) for a in input().split()]
    LR.append([L,R])
dp = [0]*N
dp[0] = 1
print(dp,LR)
f = 998244353
for i in range(1,N):
    for j in range(len(LR)):
        if i-LR[j][1] >= 0:
            dp[i] += sum(dp[i-LR[j][1]:i-LR[j][0]+1]) %f
        elif i-LR[j][0] >= 0: 
            dp[i] += sum(dp[:i-LR[j][0]+1]) %f
print(dp)
print(int(dp[-1]))

Submission status: Wrong Answer

Solution code:
MOD = 998244353


def main():
    N, K = map(int, input().split())

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

    dp = [0 for _ in range(N + 1)]
    dp[1] = 1

    for n in range(2, N + 1):
        for S in SN:
            L, R = S
            L =  n - L
            R = n - R

            print("n={},L={},R={}".format(n, L, R))
            print("n-R={}, n-L={}".format(n - R, n - L))
            dp[n] = (dp[n] + sum(dp[(n - R):(n - L)+1])) % MOD
            print(dp)

    print(dp[N])


main()

Submission status: Wrong Answer

Solution code:
p = 998244353
def segfunc(x,y):
    return (x+y)%p

class SegmentTree():
    def __init__(self,A,n,ide_ele):
        self.ide_ele=ide_ele
        self.num =2**(n-1).bit_length()
        self.seg = [self.ide_ele]*2*self.num
        #set_val
        for i in range(n):
            self.seg[i+self.num-1]=A[i]
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=segfunc(self.seg[2*i+1],self.seg[2*i+2])

    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = segfunc(self.seg[k*2+1],self.seg[k*2+2])

    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res,self.seg[p])
            if q&1 == 1:
                res = segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,self.seg[p])
        else:
            res = segfunc(segfunc(res,self.seg[p]),self.seg[q])
        return res

N,K = list(map(int,input().split()))
Ms = []
for i in range(K):
    Ms.append(list(map(int,input().split())))
Ms.sort(key=lambda x:x[0])

A = [0]*N
A[0] = 1
SegTree = SegmentTree(A,N,0)

for i in range(1,N):
    S = 0
    for k in range(K):
        L,R = Ms[k]
        iL,iR = max(0,i-L),max(0,i-R)
        S += SegTree.query(iL,iR+1)%p
    SegTree.update(i,S)
    A[i]=S
print(SegTree.query(N-1,N))

Submission status: Wrong Answer

Solution code:
#ABC179-d
import sys,math,collections,itertools
input = sys.stdin.readline
m=998244353

N,K=list(map(int,input().split()))
DP = [0]*(2*10**5+1)
move = []
for _ in range(K):
    l,r=list(map(int,input().split()))
    move += list(range(l,r+1))

ans = 0
for i in range(2,N+1):
    for mo in move:
        if i-mo<=0:
            break
        elif i-mo==1:
            DP[i]+=1
        else:
            DP[i]+= DP[i-mo]
print(DP[N]%m)

Submission status: Wrong Answer

Solution code:
import math

CON = 998244353

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

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

# def calc(num):
#     i = 1
#     while num - i >= i:
#         if num - i == i:
#             dp[num] += (dp[num - 1 - i] ** fact(num - 1 - i) ) * (dp[i] ** fact(i))
#         else:
#             dp[num] += perm(num - 1 , (num - 1) - i, i) * ( dp[num - 1 - i] ** math.factorial(num - 1 - i) ) * (dp[i] ** math.factorial(i))
#         i += 1

def calc(num):
    for i in range(1, num//2 + 1):
        dp[num] += dp[num - i] * dp[i]

def perm(n,p,q):
    return fact(n) // ( fact(p) * fact(q) )


def solve():
    # dp初期設定
    for scp in LR:
        for pnt in range(scp[0],scp[1] + 1):
            dp[pnt] = 1
    
    for j in range(2,N + 1):
        calc(j)

    print(dp[N-1])


solve()

Submission status: Wrong Answer

Solution code:
m = 998244353

N,K = map(int,input().split())
s=set()
for i in range(K):
    i1,i2 = map(int,input().split())
    s.update(set(range(i1,i2+1)))
memo = [-1]*(N+1)
def saiki(n):
    if n == 1:
        return 1
    elif n <=0:
        return 0
    elif memo[-1] != 0:#use memo
        return memo[n]

    count = 0
    for i in s:
        count += saiki(n-i)
        count = count % m
    memo[n] = count
    
    return count
print(saiki(N))

Submission status: Wrong Answer

Solution code:
import itertools
n,k = map(int,input().split())
lr = []
for _ in range(k):
    a,b = map(int,input().split())
    lr.append(list(range(a,b+1)))
lr = list(itertools.chain.from_iterable(lr))
count = [0] * n
for a in lr:
    count[a-1] = 1
for i in range(n):
    for j in lr:
        if count[i-j] > 0:
            count[i] = count[i-j] + 1
    print(count)
print(count[-2])

Submission status: Wrong Answer

Solution code:
PRIME = 998244353
n, k = map(int, input().split())
a = [0 for i in range(n + 1)]
a[1] = 1

l = []
r = []

for i in range(k):
  _l, _r = map(int, input().split())
  l.append(_l)
  r.append(_r)

for i in range(1, n):
  for j in range(k):
    if i + l[j] <= n:
      a[i + l[j]] += 1
    if i + r[j] + 1 <= n:
      a[i + r[j] + 1] += PRIME - 1

for i in range(1, n + 1):
  a[i] = (a[i - 1] + a[i]) % PRIME

print(a[n] % PRIME)

Submission status: Wrong Answer

Solution code:
def inc(v):
  for x in lr:
    if (v>=x[0]) & (v<=x[1]):
      return True
  return False

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

x = [1]
for i in range(1,n):
  val = 0
  for j in range(1,i+1):
    if inc(j):
      val += x[-j] % 998244353
  x.append(val)
print(x[-1])

Submission status: Wrong Answer

Solution code:
def main():
    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):
        for num in sorted_set:
            if num+1 > i:
                break
            else:
                dp[i] += dp[i - num]
    print(dp[-1] % 998244353)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

paths = []
for i in range(K):
    L, R = map(int, input().split(" "))
    paths += list(range(L, R+1))

log = [0] * N
for i in range(N):
    if i == 0:
        log[i] = 1
    for d in paths:
        if i - d >= 0:
            log[i] += log[i-d]

print(log[N-1])

Submission status: Wrong Answer

Solution code:
def tansaku(now):
    new_masu = []
    for i in range(len(now)):
        for d in S:
            if now[i]+d == N:
                global ans
                ans += 1
            elif now[i]+d < N:
                new_masu.append(now[i]+d)

    now = new_masu
    ans %= 998244353
    if len(now) != 0:
        tansaku(now)
    else:
        print(ans)


N, K = map(int, input().split())
S = []
now = [1]
ans = 0

for i in range(K):
    L, R = map(int, input().split())
    for j in range(R-L+1):
        S.append(L+j)
S = list(set(S))
print(S)

tansaku(now)

Submission status: Wrong Answer

Solution code:
n,k = input().split()
goal = int(n)
loup = int(k)
total = set()
dp = [0] * (goal + 1)
dp[0] = 1



#集合の作成
for k in range(loup):
	a,b = map(int, input().split())
	l = set(range(a,b+1))
	total = total | l

#main
for i in range(1,goal + 1):
	for n in range(1,max(total) + 1):
		if n not in total:
			continue
        
		if i-n >= 0:
			dp[i] = dp[i] + dp[i-n]

print(dp[goal] % 998244353)

Submission status: Wrong Answer

Solution code:
import itertools

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

mod = 998244353

m_list = []

for _ in range(k):
    l, r = map(int, input().split())
    t_list = list(range(l,r+1))
    m_list.append(t_list)

m_list = list(itertools.chain.from_iterable(m_list))

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

for i in range(n):
    for j in range(len(m_list)):
        dp[i] += dp[i-m_list[j]]

print(dp[n-1] % mod)

Submission status: Wrong Answer

Solution code:
def main():
    n,k = map(int,input().split())
    rngs = []
    for i in range(k):
        rngs.append(list(map(int,input().split())))
    print(solve(n,k,rngs))


def solve(n,k,rngs):
    mod = 998244353
    imos = [0] * (n+2)
    dp = [0] * (n+1)
    dp[1] = 1
    temp = 1

    for i in range(1,n+1):
        #print("i:",i,"temp:",temp)
        dp[i] = temp
        temp += imos[i]



        for rng in rngs:
                start,end = rng
                start += i
                try:
                    imos[start] += 1
                except IndexError:
                    continue
                try:
                    imos[end+1] -= 1
                except IndexError:
                    continue
    #print(dp)
    #print(imos)
    return dp[n]%mod



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K, *LR = map(int, read().split())

MOD = 998244353
a = []
dp = [0] * (N+1)

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

for L, R in zip(LR, LR):
    if L in a:
        continue
    else:
        a.append(L)
    if R in a:
        continue
    else:
        a.append(R)

for i in range(N+1):
    for j in a:
        if i - j <= 0:
            continue
        else:
            dp[i] += dp[i-j]

print(dp[N] % MOD)

Submission status: Wrong Answer

Solution code:
import heapq
n,k=map(int,input().split())
can=[]
for i in range(k):
    l,r=map(int,input().split())
    for j in range(l,r+1):
        can.append(j)
table=[0]*n
table[0]=1
ka=[0]*(n+1)
ka[0]=1
que=[0]
heapq.heapify(que)
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())
S = set()
ans = [0] * (N + 1)
i = 1

for _ in range(K):
    S = S | set(map(int, input().split()))

while True:
    for d in S:
        flg = False
        if i + d <= N:
            flg = True
            ans[i + d] += 1
    if flg == False:
        break

print(ans[N] % 998244353)

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K, *LR = map(int, read().split())

MOD = 998244353
a = []
dp = [0] * (N+1)

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

for L, R in zip(LR, LR):
    if L in a:
        continue
    else:
        a.append(L)
    if R in a:
        continue
    else:
        a.append(R)

print(a)

for i in range(N+1):
    for j in a:
        if i - j <= 0:
            continue
        else:
            dp[i] += dp[i-j]

print(dp[N] % MOD)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[[int(i) for i in input().split()] for _ in range(k)]
s=set()
for x in a:
     s.add(x[0])
     s.add(x[1])
s=list(s)

count = [1]+[0]*n
for x in range(n + 1):
     for c in s:
          if x-c>=0:
               count[x]+=count[x-c]
print(count[-2]%998244353)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 998244353
N, K = map(int, readline().split())
data = []
for _ in range(K):
    L,R = map(int, readline().split())
    data.append((L,R))
    
data = sorted(data)

dp = [0]*(N+1)
dp[1] = 1
for i in range(2,N+1):
    for k in range(K):
        L,R = data[k]
        if i-L >= 0:
            dp[i] += sum(dp[i-R:i-L+1])%MOD

print(dp[N])

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

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

mod = 998244353
col = list(s)
counts = [0]*(n+1)
for i in range(1, n+1):
    for c in col:
        if c > i:
            break
        if c == i:
            counts[i] += 1
            counts[i] = counts[i] % mod
            continue
        else:
            counts[i] += counts[i-c]
            counts[i] = counts[i] % mod

print(counts[n-1] % mod)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

D = np.zeros(N, dtype=int)
D[0] = 1

for n in range(N):
  for lr in LR:
    for i in range(lr[0], lr[1] + 1): 	
    	D[n] += D[n - i] % 998244353
      
print(D[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])
    array[p] = total
g = 998244353
print(int(array[-1]) % g)

Submission status: Wrong Answer

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

s = []
for i in range(k):
    l,r = map(int,input().split())
    if l == r:
        s.append(l)
    else:
        s.append(l)
        s.append(r)
s.sort()
# print(s)
dp = [0 for i in range(n+1)]
dp[1] = 1
for i in range(2,n+1):
    for j in s:
        if i-j >= 1:
            dp[i] += dp[i-j]
    # print(dp)
print(dp[n] % mod)

Submission status: Wrong Answer

Solution code:
import collections

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

c = 0
q = collections.deque()
for i in range(k):
    l,r = map(int,input().split())
    for j in range(l,r+1):
        c += 1
        q.append(j)
print(q)

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

i = 0
while q:
    i += 1
    tmp = q.pop()
    for j in range(1,n+1):
        if j+tmp <= n:
            dp[j+tmp] = (dp[j] + 1)%mod

print(dp[n]%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:
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+1):
        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:
def main():
    mod = 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):
        for num in sorted_set:
            if num+1 > i:
                break
            else:
                dp[i] += dp[i - num]
    print(dp[-1] % mod)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

s = []
for i in range(k):
    l,r = map(int,input().split())
    if l == r:
        s.append(l)
    else:
        s.append(l)
        s.append(r)
s.sort()
# print(s)
dp = [0 for i in range(n+1)]
dp[1] = 1
for i in range(2,n+1):
    for j in s:
        if i-j >= 1:
            dp[i] += dp[i-j]
            dp[i] %= mod
    # print(dp)
print(dp[n])

Submission status: Wrong Answer

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

d_set = set()

for k in range(K):
    L,R = map(int, input().split())
    d_set |= set(list(range(L,R+1)))

dp = [0] * (N+1)
# init
for d in d_set:
    dp[d] = 1

for i in range(N):
    for d in d_set:
        if i+d > N:
            break
        dp[i+d] += dp[i]

print(dp[N-1]%MOD)

Submission status: Wrong Answer

Solution code:
m = 998244353

N,K = map(int,input().split())
s=set()
for i in range(K):
    i1,i2 = map(int,input().split())
    s.update(set(range(i1,i2+1)))
memo = [0]*(N+1)
def saiki(n):
   #print("---")
    #print(n)
    if n == 1:
        return 1
    elif n <=0:
        return 0
    elif memo[n] != 0:#use memo
        return memo[n]

    count = 0
    for i in s:
        count += saiki(n-i)
        count = count % m
    memo[n] = count
    #print(count)
    
    return count

Submission status: Wrong Answer

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

L = [0 for _ in range(N)]
R = [0 for _ in range(N)]

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

S = []
for i in range(K):
    for s in range(L[i],R[i]+1):
        S.append(s)

A = [0 for _ in range(N)]

A[0] = 1

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

print(A[N-1])

Submission status: Wrong Answer

Solution code:
import sys
import itertools

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

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


for i in range(K):
    a, b = map(int, input().split())
    for j in range(a-1, b):
        dp[j+1] = 1
        q.append(j+1)


# print(dp)

for i in range(1, N):
    for j in q:
        if i - j < 1:
            break
        dp[i] = dp[i] + dp[i-j]
        # print(i, j, dp[i-j], dp)

print(dp[N-1] % 998244353)

Submission status: Wrong Answer

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

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

mod = 998244353
col = list(s)
counts = [0]*(n+1)
for i in range(1, n+1):
    for c in col:
        if c > i:
            break
        if c == i:
            counts[i] += 1
            continue
        else:
            counts[i] += counts[i-c] % mod

print(counts[n-1] % mod)

Submission status: Wrong Answer

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

pool = []
for _ in range(K):
  L, R = map(int, input().split())
  pool += list(range(L, R+1))

ex = [False] * (N+1)
memo = [0] * (N+1)
ex[0] = True
memo[0] = 1

def calc(n):
  if not ex[n]:
    memo[n] = sum([calc(n-i) for i in pool if (n-i) >= 0]) % 998244353
  ex[n] = True
  return memo[n]

_ = calc(N)
print(memo[-2])

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] < 0:
    dp[N] += 998244353    
print(dp[N])