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 numpy as np
N,K=map(int,input().split())
arr=np.array([0]*N)
for _ in range(K):
    l,r=map(int,input().split())
    arr[l-1:r]+=1
#print(arr)
dp=np.array([0]*(2*N+2))
dp[1]=1

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

Submission status: Wrong Answer

Solution code:
N,K,*LR=map(int,open(0).read().split())
S=set()
for i in range(0,K*2,2):
    S |= set(range(LR[i],LR[i+1]+1))

Submission status: Wrong Answer

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

data = list(set(data))
def check():
    global ans
    for i in range(n):
        for j in range(len(data)):
            if i - data[j] < 0:
                continue
            ans[i] = (ans[i] + ans[i - data[j]]) % mod

check()
print(ans[-1] % mod)

Submission status: Wrong Answer

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

l = [0] * K
r = [0] * K

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

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

for i in range(2, N+1):
	for j in range(K):
		li = i - r[j]
		ri = i - l[j]
		if li < 0:
			continue
		if li == 0:
			dp[i] = dp[i] + dpsum[ri]
		else:
			dp[i] = dpsum[ri] - dpsum[li-1] + dp[i]
			
			
	dpsum[i] = dp[i] + dpsum[i-1]
	
print(dp[N] % MOD)

Submission status: Wrong Answer

Solution code:
#もらうDPで考える
N, K = map(int, input().split())

l = []
r = []

MOD = 998244353

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

dp = [0] * (N+1)
#スタート地点が1なので、dp[1]を1とする
dp[1] = 1

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

for i in range(2, N+1):
    for j in range(K):
        #[l[i], r[i]]
        li = i - r[j]
        ri = i - l[j]
        if ri < 0: continue
        # l1が負になるケースをハンドリング
        li = max(1, li)
        dp[i] += dpsum[ri] - dpsum[li-1] #dp[li] ~ dp[ri]の和を足す
    dpsum[i] = dpsum[i-1] + dp[i]

print(dp[N])

Submission status: Wrong Answer

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


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, K = list(map(int, _in[0].split(' ')))  # type:list(int)
    L_R_arr = []
    for i in range(K):
        _ = list(map(int, _in[i+1].split(' ')))  # type:list(int)
        L_R_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    dp = [0] * N
    sdp = [0] * (N+1)
    dp[0] = 1
    for i in range(N):
        for L, R in L_R_arr:
            dp[i] += sdp[i-L+1] - sdp[i-R]
            sdp[i+1] = (sdp[i] + dp[i]) % 998244353
    ans = dp[-1] % 998244353
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

p = []

for i in range(K):
	l, r = map(int, input().split())
	
	p = p + list(range(l, r+1))
	
dp = [0] * (N+1)
dp[1] = 1

for i in range(1, N+1):
	for move in p:
		if i + move > N:
			continue
		dp[i+move] = dp[i] + dp[i+move]	

print(dp[N])

Submission status: Wrong Answer

Solution code:
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineering College

'''
from os import path
import sys
from heapq import heappush,heappop
from functools import cmp_to_key as ctk
from collections import deque,defaultdict as dd 
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input().rstrip()
def mi():return map(int,input().split())
def li():return list(mi())
abc='abcdefghijklmnopqrstuvwxyz'
#mod=1000000007
mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]

def bo(i):
    return ord(i)-ord('a')



    
def solve():

    
    # for _ in range(ii()):

    n,k = mi()

    seg = []

    for i in range(k):
        seg.append(li())

    dp = [0]*(n+1)

    dp[1] = 1
    for i in range(2,n+1):
        dp[i] += dp[i-1]
        dp[i] %= mod
        for j in range(k):
            if seg[j][0] >= i:
                continue


            l = max(1,i - seg[j][1])

            r =  i - seg[j][0]

            dp[i] += dp[r] - dp[l-1]
            dp[i] += mod
            dp[i] %= mod


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


        









        
if __name__ =="__main__":

    
    if path.exists('input.txt'):
        sys.stdin=open('input.txt', 'r')
        sys.stdout=open('output.txt','w')
    else:
        input=sys.stdin.readline
    solve()

Submission status: Wrong Answer

Solution code:
mod = 998244353

# 貰うDP
def main(N, S):
    dp = [0 if n != 0 else 1 for n in range(N)]     # dp[i]はマスiに行く通り数． (答えはdp[-1]), dp[0] = 1 (最初にいる場所だから1通り)
    A = [0 if n != 0 else 1 for n in range(N)]      # dp[i] = A[i] - A[i-1] (i >= 1), A[0] = dp[0] = 1 (i = 0) が成り立つような配列を考える．

    for i in range(1, N):   # 今いる点 (注目点)
        for l, r in S:  # 選択行動範囲 (l: 始点, r: 終点)
            if i - l < 0:   # 注目点が選択行動範囲の始点より手前の場合 → 注目点に来るために使用することはできない．
                break
            else:           # 注目点に来るために使用することができる場合
                dp[i] += A[i-l] - A[max(i-r-1, 0)]  # lからrの間で，注目点に行くために使用できる点を逆算． そこに行くことができる = 選択行動範囲の値を選択することで注目点に達することができる通り数．
        dp[i] %= mod
        A[i] = (A[i-1] + dp[i]) % mod
    print(dp[-1])

if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    S = {tuple(map(int, input().split())) for k in range(K)}
    S = sorted(list(S), key = lambda x:x[0])    # 始点でsort (範囲の重複がないため)
    main(N, S)

Submission status: Wrong Answer

Solution code:
mod = 998244353

# 貰うDP
def main(N, S):
    dp = [0 if n != 0 else 1 for n in range(N)]     # dp[i]はマスiに行く通り数． (答えはdp[-1]), dp[0] = 1 (最初にいる場所だから1通り)
    A = [0 if n != 0 else 1 for n in range(N)]      # dp[i] = A[i] - A[i-1] (i >= 1), A[0] = dp[0] = 1 (i = 0) が成り立つような配列を考える．

    for i in range(1, N):   # 今いる点 (注目点)
        for l, r in S:  # 選択行動範囲 (l: 始点, r: 終点)
            if i - l < 0:   # 注目点が選択行動範囲の始点より手前の場合 → 注目点に来るために使用することはできない．
                break
            else:           # 注目点に来るために使用することができる場合
                dp[i] += A[i-l] - A[max(i-r-1, 0)]  # lからrの間で，注目点に行くために使用できる点を逆算． そこに行くことができる = 選択行動範囲の値を選択することで注目点に達することができる通り数．
        dp[i] %= mod
        A[i] = (A[i-1] + dp[i]) % mod
    print(dp, A)

if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    S = {tuple(map(int, input().split())) for k in range(K)}
    S = sorted(list(S), key = lambda x:x[0])    # 始点でsort (範囲の重複がないため)
    main(N, S)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
S = set()
for _ in range(K):
	a,b = map(int, input().split())
	S.add(a)
	S.add(b)
dp = [0]*(N+1)
dp[1] = 1
mod = 998244353
l = sorted(list(S))
for i in range(1,N+1):
	for j in l:
		if(i >= j):
			dp[i] += dp[i-j]
			dp[i] %= mod
print(dp[-1])

Submission status: Wrong Answer

Solution code:
def N():
    return int(input())
def L():
    return list(map(int,input().split()))
def NL(n):
    return [list(map(int,input().split())) for i in range(n)]
mod = pow(10,9)+7
md = 998244353

n,k = L()
lr = NL(k)

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

for i in range(1,n+1):
    dp[i] = (dp[i]+dp[i-1])%md
    for l,r in lr:
        if i+l < n+1:
            dp[i+l] += dp[i]
            dp[i+l] %= md
            if i+r+1 < n+1:
                dp[i+r+1] -= dp[i]

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

Submission status: Wrong Answer

Solution code:
root=[]
n,k = map(int,input().split())
for i in range(k):
    x,y = map(int,input().split())
    root.append([x,y])

toori=[0]*(2*10**5)+[0]*n+[0]*(2*10**5)
toori[2*10**5]=1
cum=[0]*k
for a,i in enumerate (root):
    s=0
    for j in range (i[0],i[1]+1):
        s+=toori[2*10**5+1-j]
    cum[a]=s
aaa=sum(cum)
toori[2*10**5+1]+=aaa

Submission status: Wrong Answer

Solution code:
import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array

# 時々使う
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    D = [il() for _ in range(K)]

    dp = [0] * (N)
    dp[0] = 1
    acc = [0] * (N + 1)
    acc[1] = 1
    for i in range(1, N):
        for l, r in D:
            left = max(0, i - r)
            right = max(0, i - l + 1)
            dp[i] += (acc[right] - acc[left]) % MOD
        acc[i+1] = acc[i] + dp[i]
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

for i in range(2, N+1):
    for l, r in S:
            DP[i] += (DP[max(i-l, 0)] - DP[max(i-r-1, 0)])
    DP[i] += DP[i-1]
    DP[i] %= 998244353

print(DP[N]%998244353)

Submission status: Wrong Answer

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

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

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

for i in range(2, N+1):
    for l, r in S:
            DP[i] += (DP[max(i-r, 0)] - DP[max(i-l-1, 0)])%998244353
    DP[i] += DP[i-1]

print(DP[N]%998244353)

Submission status: Wrong Answer

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

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

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

for i in range(2, N+1):
    for l, r in S:
            DP[i] += (DP[max(i-l, 0)] - DP[max(i-r-1, 0)])%998244353
    DP[i] += DP[i-1]

print(DP[N]%998244353)

Submission status: Wrong Answer

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

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

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

S.sort()

for i in range(2, N+1):
    for l, r in S:
            DP[i] = (DP[max(i-l, 0)] - DP[max(i-r-1, 0)])%998244353
    DP[i] += DP[i-1]

print(DP[N]%998244353)

Submission status: Wrong Answer

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

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

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

S.sort()

for i in range(2, N+1):
    for l, r in S:
        if 0 <= i - r <= N and 0 <= i - l - 1 <= N:
            DP[i] = (DP[i-r] - DP[i-l-1])%998244353
    DP[i] += DP[i-1]

print(DP[N]%998244353)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc179/tasks/abc179_d

n, k = map(int, input().split())
leaps = []
for _ in range(k):
    l, r = map(int, input().split())
    leaps.append((l, r))
mod = 998244353
dp = [0] * (n + 1)
dp[1] = 1

for i in range(2, n + 1):
    for l, r in leaps:
        li = i - l
        ri = i - r
        dp[i] += dp[max(li, 0)] - dp[max(ri - 1, 0)]
        dp[i] %= mod


print(dp[n] % mod)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    ikimasu = sys.stdin.buffer.readline
    ini = lambda: int(ins())
    ina = lambda: list(map(int, ikimasu().split()))
    ins = lambda: ikimasu().strip()
    MOD = 998244353
    class ModInt:
        def __init__(self, x):
            self.x = x % MOD

        def __str__(self):
            return str(self.x)

        __repr__ = __str__

        def __add__(self, other):
            return (
                ModInt(self.x + other.x) if isinstance(other, ModInt) else
                ModInt(self.x + other)
            )

        def __sub__(self, other):
            return (
                ModInt(self.x - other.x) if isinstance(other, ModInt) else
                ModInt(self.x - other)
            )

        def __mul__(self, other):
            return (
                ModInt(self.x * other.x) if isinstance(other, ModInt) else
                ModInt(self.x * other)
            )

        def __truediv__(self, other):
            return (
                ModInt(
                    self.x * pow(other.x, MOD - 2, MOD)
                ) if isinstance(other, ModInt) else
                ModInt(self.x * pow(other, MOD - 2, MOD))
            )

        def __pow__(self, other):
            return (
                ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
                ModInt(pow(self.x, other, MOD))
            )

        __radd__ = __add__

        def __rsub__(self, other):
            return (
                ModInt(other.x - self.x) if isinstance(other, ModInt) else
                ModInt(other - self.x)
            )

        __rmul__ = __mul__

        def __rtruediv__(self, other):
            return (
                ModInt(
                    other.x * pow(self.x, MOD - 2, MOD)
                ) if isinstance(other, ModInt) else
                ModInt(other * pow(self.x, MOD - 2, MOD))
            )

        def __rpow__(self, other):
            return (
                ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
                ModInt(pow(other, self.x, MOD))
            )

    n,k = ina()
    dp = [ModInt(0)]*(n+1)
    dp[1] = 1
    pair = [(0,0)]*k
    for i in range(k):
        l,r = ina()
        pair[i] = (l,r)
    for i in range(1,n):
        tmp = i
        dp[tmp]+=dp[tmp-1]
        for j in range(k):
            if(tmp+pair[j][0])<=n:
                # print(tmp,pair[j][0])
                dp[tmp+pair[j][0]]+=dp[tmp]
                # print(dp)
            if(tmp+pair[j][1])<=n-1:
                # print(tmp,pair[j][1])
                dp[tmp+pair[j][1]+1]-=dp[tmp]
                # print(dp)
    print(dp)
    print(dp[n])
        
        
    

    
    
        


    
        


        


    




















if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    ikimasu = sys.stdin.buffer.readline
    ini = lambda: int(ins())
    ina = lambda: list(map(int, ikimasu().split()))
    ins = lambda: ikimasu().strip()
    MOD = 998244353
    class ModInt:
        def __init__(self, x):
            self.x = x % MOD

        def __str__(self):
            return str(self.x)

        __repr__ = __str__

        def __add__(self, other):
            return (
                ModInt(self.x + other.x) if isinstance(other, ModInt) else
                ModInt(self.x + other)
            )

        def __sub__(self, other):
            return (
                ModInt(self.x - other.x) if isinstance(other, ModInt) else
                ModInt(self.x - other)
            )

        def __mul__(self, other):
            return (
                ModInt(self.x * other.x) if isinstance(other, ModInt) else
                ModInt(self.x * other)
            )

        def __truediv__(self, other):
            return (
                ModInt(
                    self.x * pow(other.x, MOD - 2, MOD)
                ) if isinstance(other, ModInt) else
                ModInt(self.x * pow(other, MOD - 2, MOD))
            )

        def __pow__(self, other):
            return (
                ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
                ModInt(pow(self.x, other, MOD))
            )

        __radd__ = __add__

        def __rsub__(self, other):
            return (
                ModInt(other.x - self.x) if isinstance(other, ModInt) else
                ModInt(other - self.x)
            )

        __rmul__ = __mul__

        def __rtruediv__(self, other):
            return (
                ModInt(
                    other.x * pow(self.x, MOD - 2, MOD)
                ) if isinstance(other, ModInt) else
                ModInt(other * pow(self.x, MOD - 2, MOD))
            )

        def __rpow__(self, other):
            return (
                ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
                ModInt(pow(other, self.x, MOD))
            )

    n,k = ina()
    dp = [ModInt(0)]*(n+1)
    dp[1] = 1
    pair = [(0,0)]*k
    for i in range(k):
        l,r = ina()
        pair[i] = (l,r)
    for i in range(1,n):
        tmp = i
        dp[tmp]+=dp[tmp-1]
        for j in range(k):
            if(tmp+pair[j][0])<=n:
                print(tmp,pair[j][0])
                dp[tmp+pair[j][0]]+=dp[tmp]
                print(dp)
            if(tmp+pair[j][1])<=n-1:
                print(tmp,pair[j][1])
                dp[tmp+pair[j][1]+1]-=dp[tmp]
                print(dp)
    print(dp)
    print(dp[n])
        
        
    

    
    
        


    
        


        


    




















if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

leng = 0
for i in range(1,n):
    for j in s:
        leng = j[1] - j[0]
        dp[i] += sum(dp[max(0, i-leng-j[0]):max(0,min(n, i-j[0]+1))])

print(dp[-1]//998244353)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp = np.zeros(N+2, dtype = int)
dp[1] = 1
dp[2] = -1

atai = 0
for i in range(1, N+2):
    atai += dp[i]
    for LR in LRs:
        if(i+LR[0] <= N):
            dp[i+LR[0]] += atai
        if(i+LR[1] <= N):
            dp[i+LR[1]+1] -= atai

#    print(dp)

#復元
ruisekiwa = [0]

for hoge in dp:
    ruisekiwa.append(ruisekiwa[-1]+hoge)
print(ruisekiwa[N+1] % 998244353)

Submission status: Wrong Answer

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

dp = (3*N)*[0]
dp[0] = 1
dp[1] = -1

for n in range(N):
  for L,R in LR:
    dp[L+n]+=dp[n]
    dp[n+R+1]-=dp[n]
    dp[n+1] = (dp[n]+dp[n+1])%998244353

print(dp[N-1])

Submission status: Wrong Answer

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

li = [0]*(n+2)
lis = []
lr=[]
lis2 =[0]*(3*n)
lis2[1]=1

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

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

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

print(lis2[n]%998244353)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
ls = []
rs = []
ps = []
MOD = 998244353
s = set()
for _ in range(k):
    l,r = map(int, input().split())
    for i in range(l,r+1):
        s.add(i)
dp = [0] * (n+1)
dp[0] = 1
imos = [0]
for i in range(n):
    for d in sorted(list(s), reverse=True):
        if i - d >= 0:
            dp[i] += dp[i-d]
            dp[i-1] -= dp[i]
            dp[i] %= MOD

print(dp[n-1])

Submission status: Wrong Answer

Solution code:
mod = 998244353
n,k =map(int,input().split())
step =[0]*(n+1)
# step[0]=1
step[1]=1
stepsum=[0]*(n+1)
stepsum[1]=1
l=[0]*k
r=[0]*k
for i in range(k):
    l[i],r[i]=map(int,input().split())

for i in range(2,n+1):
    for j in range(k):
        li = i - r[j]
        ri = i - l[j]
        if ri <= 0:
            continue
        # li = max(1,li)
        step[i] += stepsum[ri] - stepsum[max(0,li-1)]
        # step[i] %= mod
        # print(step)
    stepsum[i] = ( stepsum[i-1] + step[i] )%mod


print(step[n])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# DP, 累積和
n, k = list(map(int, input().split()))
s = list()
for i in range(k):
     l, r = list(map(int, input().split()))
     s.append((l, r))

mod = 998244353
i = 1
dp = [0] * (n+1)
dp[1] = 1
dpsum = [0] * (n+1)
dpsum[1] = 1
for i in range(2, n+1):
    for l, r in s:
        li = i-r
        ri = i-l
        if ri < 1: continue
        li = max(li, 1)
        dp[i] += dpsum[ri] - dpsum[li-1]
    dpsum[i] = (dpsum[i-1] + dp[i]) % mod
    
print(dp[n])

Submission status: Wrong Answer

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

MOD = 998244353

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

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


for i in range(2, N+1):
    for j in range(len(L_list)):
        if i - R_list[j]-1 < 0:
            R_pos = 0
        else:
            R_pos = i - R_list[j] - 1
        dp[i] += (sdp[i - L_list[j]] - sdp[R_pos])%MOD
    sdp[i] = sdp[i-1] + dp[i]
    sdp[i] %= MOD
    #print(dp)
    #print("s", sdp)
print(dp[N])

Submission status: Wrong Answer

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

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

leng = 0
for i in range(1,n):
    for j in s:
        leng = j[1] - j[0]
        dp[i] += sum(dp[max(0, i-leng-j[0]):max(0,min(n, i-j[0]+1))])

print(dp[-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import numpy as np

# 標準入力を取得
N, K = list(map(int, input().split()))
S = []
for k in range(K):
    L_k, R_k = list(map(int, input().split()))
    S.append((L_k, R_k))

# 求解処理
S = sorted(S, key=lambda s: s[0])
m = np.array([0 if i != 0 else 1 for i in range(N)], dtype=np.uint64)
for i in range(N):
    m_i = int(m[i])
    if m_i == 0:
        continue
    for L_k, R_k in S:
        if i + L_k >= N:
            break
        m[i + L_k: i + R_k + 1] += m_i

ans = int(m[N - 1]) % 998244353

# 結果出力
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import numpy as np

# 標準入力を取得
N, K = list(map(int, input().split()))
S = []
for k in range(K):
    L_k, R_k = list(map(int, input().split()))
    S.append((L_k, R_k))

# 求解処理
S = sorted(S, key=lambda s: s[0])
m = np.array([0 if i != 0 else 1 for i in range(N)], dtype=np.uint64)
for i in range(N - 1):
    m_i = int(m[i])
    if m_i == 0:
        continue
    for L_k, R_k in S:
        if i + L_k >= N:
            break
        m[i + L_k: i + R_k + 1] += m_i

ans = int(m[N - 1]) % 998244353

# 結果出力
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    mod = 998244353
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = -1
    left = [0] * k
    right = [0] * k
    for i in range(k):
        left[i], right[i] = map(int, input().split())
        right[i] += 1
    for i in range(n + 1):
        dp[i] += dp[i - 1]
        for j in range(k):
            if i + left[j] <= n:
                dp[i + left[j]] += dp[i]
            if i + right[j] <= n:
                dp[i + right[j]] -= dp[i]
        dp[i] %= mod
    print(dp[n])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import numpy as np

# 標準入力を取得
N, K = list(map(int, input().split()))
S = []
for k in range(K):
    L_k, R_k = list(map(int, input().split()))
    S.append((L_k, R_k))

# 求解処理
S = sorted(S, key=lambda s: s[0])
m = np.array([0 if i != 0 else 1 for i in range(N)], dtype=np.uint64)
for i in range(N - 1):
    m_i = m[i]
    if m_i == 0:
        continue
    for L_k, R_k in S:
        if i + L_k >= N:
            break
        m[i + L_k: i + R_k + 1] += m_i

ans = int(m[N - 1]) % 998244353

# 結果出力
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = list(map(int, input().split()))
numlist=[]
for i in range(k):
    l,r=list(map(int, input().split()))
    for j in range(l,r+1):
        numlist.append(j)
numlist.sort()
nlen=len(numlist)
count=[0]*(n+2)
count[0]=1
for i in range(n-1):
    count[i]%=998244353
    for j in range(nlen):
        num=numlist[j]-1
        if i+1>num:
            count[i+1]+=count[i-num]
print(count[i+1])

Submission status: Wrong Answer

Solution code:
n,k = list(map(int, input().split()))
numlist=[]
for i in range(k):
    l,r=list(map(int, input().split()))
    for j in range(l,r+1):
        numlist.append(j)
numlist.sort()
nlen=len(numlist)
count=[0]*n
count[0]=1
for i in range(n-1):
    for j in range(nlen):
        num=numlist[j]
        if i+2>num:
            count[i+1]+=count[i+1-num]
print(count[i+1])

Submission status: Wrong Answer

Solution code:
n,k = list(map(int, input().split()))
numlist=[]
for i in range(k):
    l,r=list(map(int, input().split()))
    for j in range(l,r+1):
        numlist.append(j)
numlist.sort()
nlen=len(numlist)
count=[0]*n
count[0]=1
for i in range(n-1):
    for j in range(nlen):
        num=numlist[j]
        print(i+2,num)
        if i+2>num:
            count[i+1]+=count[i+1-num]
print(count[i+1])

Submission status: Wrong Answer

Solution code:
#D
n,k = list(map(int, input().split()))
numlist=[]
for i in range(k):
    l,r=list(map(int, input().split()))
    for j in range(l,r+1):
        numlist.append(j)
numlist.sort()
nlen=len(numlist)
count=[0]*n
count[0]=1
for i in range(n-1):
    for j in range(nlen):
        num=numlist[j]
        print(i+2,num)
        if i+2>num:
            print("go")
            count[i+1]+=count[i+1-num]
    print(count)
print(count[i+1])

Submission status: Wrong Answer

Solution code:
MOD = 998244353
N, K = map(int, input().split()) #Nはマス目の数、Kは区間の数(Kは10以下)
kukan = [tuple(map(int, input().split())) for _ in range(K)]

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

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

for i in range(2, N+1):
    for l, r in kukan:
        li = max(i - l, 0)
        ri = max(i - r - 1, 0)

        dp[i] += sumdp[li] - sumdp[ri]

    sumdp[i] = sumdp[i-1] + dp[i]

print(dp[N])

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

mod = 998244353

n, k = map(int, input().split())
l = []
r = []
for _ in range(k):
    l_, r_ = map(int, input().split())
    l.append(l_)
    r.append(r_)
dp = [0] * (n + 1)
dp_csum = [0] * (n + 1)
dp[1] = 1
dp_csum[1] = 1
for i in range(2, n + 1):
    for j in range(k):
        left = i - r[j]
        right = i - l[j]
        if right > 0:
            dp[i] += dp_csum[right] - dp_csum[max(left, 1) - 1]
            dp[i] %= mod
            dp_csum[i] = dp_csum[i - 1] + dp[i]
            dp_csum[i] %= mod
print(dp[-1])

Submission status: Wrong Answer

Solution code:
def readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 998244353
import math
def solve(N,S):
    """
    Tak begins in cell=1 and wants to move to cell=N.  All cells are along a line and 1,2,...,N is from left to right.
    Args:
        N(int):  The number of cells.
        S(list):  The set containing all integers in the non-intersecting intervals.

    Returns:
        int:  The number of ways for Tak to go from cell=1 to cell=N.
    """
    dp=[0]*(N+1)
    dp_sums=[0]*(N+1)
    dp[1]=dp_sums[1]=1
    
    for i in range(2,N+1):
        for le,ri in S:
            if i>= ri+1:
                dp[i]+=dp_sums[i-le]-dp[i-ri-1]
                dp_sums[i]=dp_sums[i-1]+dp[i]
            elif i>le and i<ri+1:
                dp[i]+=dp_sums[i-le]
                dp_sums[i]=dp_sums[i-1]+dp[i]
            elif i<=le:
                dp_sums[i]=dp_sums[i-1]+dp[i]
        dp[i]%=mod
        dp_sums[i]%=mod
    return dp[N]

N,K=readMap()
S=[]
for _ in range(K):
    S.append(readList())
print(solve(N,S))

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.append([L,R])
A = [1]
for n in range(1,N):
    for i in S:
        s = sum(A[n - i] for s in S for i in range(s[0], s[1] + 1) if n - i >= 0) % 998244353
        A.append(s)
print(A[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.append([L,R])
A = [1]
for n in range(1,N):
    for i in S:
        s = sum(A[n - i] for s in S for i in range(s[0], s[1] + 1) if n - i >= 0) % 998244353
        A.append(s)
        s = 0
print(A[N-1])

Submission status: Wrong Answer

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

sys.setrecursionlimit(10**7)

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

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

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

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

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

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


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