Problem:


Score : 400 points

Problem Statement

There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.

Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.

You are given an integer K that is less than or equal to 10, and K non-intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K].
Let S be the union of these K segments.
Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.

When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.

To help Tak, find the number of ways to go to Cell N, modulo 998244353.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq K \leq \min(N, 10)

1 \leq L_i \leq R_i \leq N

[L_i, R_i] and [L_j, R_j] do not intersect (i \neq j) 

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
L_1 R_1
L_2 R_2
:
L_K R_K

Output

Print the number of ways for Tak to go from Cell 1 to Cell N, modulo 998244353.

Sample Input 1

5 2
1 1
3 4

Sample Output 1

4

The set S is the union of the segment [1, 1] and the segment [3, 4], therefore S = \{ 1, 3, 4 \} holds.

There are 4 possible ways to get to Cell 5:

1 \to 2 \to 3 \to 4 \to 5,

1 \to 2 \to 5,

1 \to 4 \to 5 and

1 \to 5.

Sample Input 2

5 2
3 3
5 5

Sample Output 2

0

Because S = \{ 3, 5 \} holds, you cannot reach to Cell 5.
Print 0.

Sample Input 3

5 1
1 2

Sample Output 3

5

Sample Input 4

60 3
5 8
1 3
10 15

Sample Output 4

221823067

Note that you have to print the answer modulo 998244353.



Sample input:
5 2
1 1
3 4


Sample output:
4

Submission status: Accepted

Solution code:
mod = 998244353

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

s = []
for _ in range(k):
    l, r = map(int, input().split())
    s.append((l, r))

dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n+1):
    for l, r in s:
        jl = max(i - l, 0)
        jr = max(i - r - 1, 0)
        dp[i] = (dp[i] + dp[jl] - dp[jr]) % mod
    dp[i] += dp[i-1]
print((dp[n] - dp[n-1]) % mod)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
LR = []
for _ in range(K): LR.append(list(map(int,input().split())))
MOD = 998244353
dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
  for L,R in LR:
    if i+L<N: dp[i+L] += dp[i]
    if i+R+1<N: dp[i+R+1] -= dp[i]
  if i>0: dp[i+1] = (dp[i+1]+dp[i])%MOD
print(dp[-1])

Submission status: Accepted

Solution code:
def solve(l, r, i):
    if i - l < 1:
        return 0
    return dp[i - l] - dp[max(i - r - 1, 0)]


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

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

for i in range(2, n + 1):
    tmp = 0
    for l, r in lr:
        tmp += solve(l, r, i)
    tmp = tmp % MOD
    dp[i] = (dp[i - 1] + tmp) % MOD

print(tmp)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
import numba
from numba import i8

input = sys.stdin.buffer.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())


@numba.njit((i8, i8[:]), cache=True)
def main(N, LR):
    L, R = LR[::2], LR[1::2]
    K = len(L)

    dp = np.zeros(N + 1, np.int64)
    dpsum = np.zeros(N + 1, np.int64)
    dp[1] = 1
    dpsum[1] = 1

    for i in range(2, N + 1):
        for k in range(K):
            li = i - R[k]
            ri = i - L[k]
            if ri < 0:
                continue
            li = max(li, 1)
            dp[i] += dpsum[ri] - dpsum[li - 1]
            dp[i] %= mod
        dpsum[i] = dpsum[i - 1] + dp[i]
        dpsum[i] %= mod

    return dp[N]


N, K = MI()
LR = np.array(sys.stdin.buffer.read().split(), np.int64)

print(main(N, LR))

Submission status: Accepted

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

dp = [0] * (N+1)
dp[1] = 1
for i in range(1, N):
  dp[i] += dp[i-1]
  dp[i] %= MOD
  for l, r in LR:
    ll = i + l
    rr = i + r
    if ll <= N:
      dp[ll] += dp[i]
      dp[ll] %= MOD
    if rr < N:
      dp[rr+1] -= dp[i]
      dp[rr+1] %= MOD

print(dp[-1])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
mod = 998244353
d = [0] * (n + 1)
d[1] = 1
LR =[list(map(int, input().split())) for _ in range(k)]

for i in range(2, n+1):
  d[i] = d[i - 1]
  for l, r in LR:
    if i - l <= 0:
      continue
    d[i] = (d[i] + (d[i-l] - d[max(0,i-r-1)])) % mod
print((d[-1] - d[-2])%mod)

Submission status: Accepted

Solution code:
def solve(l, r, i):
    if i - l < 1:
        return 0
    return dp[i - l] - dp[max(i - r - 1, 0)]


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

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

for i in range(2, n + 1):
    tmp = 0
    for l, r in lr:
        tmp += solve(l, r, i)
    tmp = tmp % MOD
    dp[i] = (dp[i - 1] + tmp) % MOD

print(tmp)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

input = sys.stdin.buffer.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())


@njit((i8, i8[:]), cache=True)
def main(N, LR):
    L, R = LR[::2], LR[1::2]
    K = len(L)

    dp = np.zeros(N + 1, np.int64)
    dpsum = np.zeros(N + 1, np.int64)
    dp[1] = 1
    dpsum[1] = 1

    for i in range(2, N + 1):
        for k in range(K):
            li = i - R[k]
            ri = i - L[k]
            if ri < 0:
                continue
            li = max(li, 1)
            dp[i] += dpsum[ri] - dpsum[li - 1]
            dp[i] %= mod
        dpsum[i] = dpsum[i - 1] + dp[i]
        dpsum[i] %= mod

    return dp[N]


N, K = MI()
LR = np.array(sys.stdin.buffer.read().split(), np.int64)

print(main(N, LR))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)
import itertools as it
import collections as cl
from collections import deque
import math
from functools import reduce
from collections import defaultdict
MOD = 998244353


def li():
    return [int(x) for x in input().split()]

N, K = li()

L, R = [], []
for _ in range(K):
    l, r = li()
    L.append(l)
    R.append(r)

# dp[i]: i番目のマスにいく場合の数
dp = [0] * (N+1)
dp[1] = 1
# 区間 [left, right)の和はdpsum[right] - dpsum[left]
# 区間 [left, right]の和はdpsum[right+1] - dpsum[left]
# マス a~bは区間だと[a-1,b-1]に対応。よってマスliからriの和はdpsum[right] - dpsum[left - 1]
dpsum = [0] * (N+1)
dpsum[1] = 1
for i in range(2, N+1):
    for j in range(K):
        li = max(i - R[j], 1)
        ri = i - L[j]
        if ri >= 0:
            dp[i] += dpsum[ri] - dpsum[li-1]
            dp[i] %= MOD
    dpsum[i] = dpsum[i-1] + dp[i]
    dpsum[i] %= MOD

print(dp[N])

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
# mod = 10**9+7
mod = 998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1
# INF = 10**18

def main():
    n,k = map(int,ipt().split())
    dp = [0]*(n+1)
    dp[1] = 1
    rng = [tuple(map(int,ipt().split())) for i in range(k)]
    for i in range(2,n+1):
        for l,r in rng:
            dp[i] += dp[max(0,i-l)]-dp[max(0,i-r-1)]
        dp[i] += dp[i-1]
        dp[i] %= mod

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

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np

# import numba
# from numba import njit, b1, i4, i8, f8

input = sys.stdin.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())


# @njit((i8, i8[:]), cache=True)
def main(N, steps):
    dp = np.zeros(N + 1, np.int64)
    dpsum = np.zeros(N + 1, np.int64)
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2, N + 1):
        for l, r in steps:
            li = i - r
            ri = i - l
            if ri < 0:
                continue
            li = max(li, 1)
            dp[i] += dpsum[ri] - dpsum[li - 1]
            dp[i] %= mod
        dpsum[i] = dpsum[i - 1] + dp[i]
        dpsum[i] %= mod

    return dp[N]


N, K = MI()

steps = []
for _ in range(K):
    l, r = MI()
    steps.append((l, r))


print(main(N, steps))

Submission status: Accepted

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

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

S = [0]*K
dp = [0]*(2*N)
dp[N] = 1

for i in range(N+1, 2*N):
  for k, (l, r) in enumerate(move):
    S[k] -= dp[i-r-1]
    S[k] += dp[i-l]
    dp[i] += S[k]
  dp[i] %= mod

print(dp[-1])

Submission status: Accepted

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

# 解説AC
dp, acc = [0] * (n + 1), [0] * (n + 1)
dp[1], acc[1] = 1, 1
for i in range(2, n + 1):
    for l, r in lr:
        accl, accr = max(i - (r + 1), 0), max(i - l, 0)
        dp[i] += acc[accr] - acc[accl]
    dp[i] %= mod
    acc[i] = (dp[i] + acc[i - 1]) % mod
print(dp[n])

Submission status: Accepted

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

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


def get(l, r, i):
    return dp_sum[max((i - l), 0)] - dp_sum[max((i - r-1), 0)]


for i in range(1, N+1):
    for l, r in LR:
        dp[i] += get(l, r, i) % MOD
    dp_sum[i] = (dp_sum[i - 1] + dp[i])%MOD
print(dp[N] % MOD)

Submission status: Accepted

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

dp = [0] * (n + 1)
acc = [0] * (n + 1)
dp[1], acc[1] = 1, 1
for i in range(2, n + 1):
    for l, r in lr:
        dp[i] += acc[max(i - l, 0)]
        dp[i] -= acc[max(i - (r + 1), 0)]
    dp[i] %= mod
    acc[i] = (dp[i] + acc[i - 1]) % mod
print(dp[n])

Submission status: Accepted

Solution code:
N, K = [int(v) for v in input().split()]

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

links = sorted(links, key=lambda x: x[1])

count = [1]
sub = [0, 1]
subtotal = 1

for i in range(1, N):
    v = 0
    for l, r in links:
        r2 = i - l + 1
        l2 = i - r
        if l2 < 0:
            l2 = 0
        if r2 >= 0:
            v += sub[r2] - sub[l2]

    count.append(v % 998244353)
    subtotal = (subtotal + v) % 998244353
    sub.append(subtotal )

print(count[-1])

Submission status: Accepted

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

dp = [0]*(N+1)
acc = [0]*(N+1) # acc[i] = dp[1] + ... dp[i]

dp[1] = 1
acc[1] = 1
for i in range(2, N+1):
    for lr in LR:
        l = lr[0]
        r = lr[1]

        dp[i] += (acc[max(0, i - l)] - acc[max(0, i - r - 1)] + MOD)
        dp[i] %= MOD
    acc[i] = (acc[i-1] + dp[i]) % MOD
    
    

print(dp[N])
# print(acc)
# print(dp[N])

Submission status: Accepted

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

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

moves = [0] * N
moves[0] = 1

rui_wa = [0] * N
rui_wa[0] = 1

for i in range(1, N):
    for j in range(0, K):
        l = max(i - L[j], 0)
        r = max(i - R[j], 0)
        if i - L[j] < 0:
            continue

        moves[i] += (rui_wa[l] - rui_wa[r - 1]) % 998244353

    rui_wa[i] = (moves[i] + rui_wa[i - 1])  % 998244353



print(moves[N - 1] % 998244353)

Submission status: Accepted

Solution code:
(n,_),*s=[[*map(int,t.split())]for t in open(0)]
d=[1,-1]+[c:=0]*2*n
for i in range(n):
 c=(c+d[i])%998244353
 for l,r in s:d[i+l]+=c;d[i-~r]-=c
print(c)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, K = NMI()
    LR = list(sorted([NLI() for _ in range(K)]))
    
    dp = [0 for _ in range(N)]
    dp[0] = 1
    
    cumsum = [0 for _ in range(N+1)]
    cumsum[0] = 0
    cumsum[1] = 1
    
    for n in range(1,N):
        for k in range(K):
            r = n-LR[k][0]
            l = n-LR[k][1]
            if r < 0:
                continue
            else:
                l = max(0,l)
            dp[n] += cumsum[r+1]-cumsum[l]
        dp[n] = dp[n]%MOD2
        cumsum[n+1] = (dp[n] + cumsum[n])%MOD2
    print(dp[-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    lr = [list(map(int, input().split())) for _ in range(k)]
    dp = [0] * (n + 1)
    dp[1] = 1
    dpsum = [0] * (n + 1)
    dpsum[1] = 1
    mod = 998244353

    for i in range(2, n + 1):
        for j in range(k):
            li = max(i - lr[j][1], 1)
            ri = i - lr[j][0]
            if ri < 0:
                continue
            dp[i] = (dp[i] + dpsum[ri] - dpsum[li - 1]) % mod
        dpsum[i] = dpsum[i - 1] + dp[i]

    print(dp[-1] % mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    lr = [list(map(int, input().split())) for _ in range(k)]
    dp = [0] * (n + 1)
    dp[1] = 1
    dpsum = [0] * (n + 1)
    dpsum[1] = 1
    mod = 998244353

    for i in range(2, n + 1):
        for j in range(k):
            li = i - lr[j][1]
            ri = i - lr[j][0]
            if ri < 0:
                continue
            dp[i] = (dp[i] + dpsum[ri] - dpsum[li - 1]) % mod
        dpsum[i] = dpsum[i - 1] + dp[i]

    print(dp[-1] % mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

LR.sort()
dp[1] = 1
dp_sum = [0]*(N+1) # dp[i]の累積和
dp_sum[1] = 1

for i in range(2, N+1):
    for l, r in LR:
        if i - l >= 1:
            dp[i] += dp_sum[i-l] - dp_sum[max(0, i-r-1)]
            dp[i] %= MOD
    dp[i] %= MOD
    dp_sum[i] = dp_sum[i-1] + dp[i]
        
print(dp[N]%MOD)

Submission status: Accepted

Solution code:
(n,_),*s=[[*map(int,t.split())]for t in open(0)]
d=[1,-1]+[0]*2*n
for i in range(n):
  d[i]=(d[i-1]+d[i])%998244353
  for l,r in s:
    d[i+l]+=d[i]
    d[i-~r]-=d[i]
print(d[n-1])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
mod=998244353
lr=[]
for i in range(k):
    lr.append(list(map(int,input().split())))
d=[0]*(n+1)
d[0]=1
for i in range(n): 
    for l,r in lr:
        r+=1
        d[min(n,i+l)]+=d[i]
        d[min(n,i+r)]-=d[i]
    if i!=0:
        d[i+1]+=d[i]
    d[i+1]%=mod
#print(d)
print(d[n-1]%mod)

Submission status: Accepted

Solution code:
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] * 300000
dpsum = [0] * 300000
dp[1] = 1
dpsum[1] = 1

for i in range(2, N+1):
    for j in range(K):
        li = min(L[j], i)
        ri = min(R[j], i + 1)
        dp[i] += dpsum[i - li] - dpsum[i - ri - 1]

    dp[i] %= 998244353
    dpsum[i] = dpsum[i-1] + dp[i]

print(dp[N])

Submission status: Accepted

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


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

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


# n, k = LI()
# s = set()
# for i in range(k):
#     l, r = LI()
#     s |= set(range(l, r + 1))

# # a = len(s)
# dp = [0] * (n + 1)
# dp[1] = 1

# for i in range(1, n+1):
#     for j in range(1, i):
#         if i-j in s:
#             dp[i] += dp[j] % 998244353
#             # dp[i] += dp[j]
# print(dp[n] % 998244353)

# 配るDP
n, k = map(int, input().split())
lr = []
for _ in range(k):
    l, r = map(int, input().split())
    lr.append((l, r))
mod = 998244353
dp = [0]*(2*n+1)
dp[0] = 1
dp[1] = -1
now = 1
for i in range(n-1):
    for l, r in lr:
        # 始点に足して終点は引く
        # imos法というらしい
        dp[i+l] += now
        dp[i+r+1] -= now
    now += dp[i+1]
    now %= mod
print(now)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
mod=998244353
lr=[]
for i in range(k):
    lr.append(list(map(int,input().split())))
d=[0]*(n+1)
d[0]=1
for i in range(n): 
    for l,r in lr:
        r+=1
        d[min(n,i+l)]+=d[i]
        d[min(n,i+r)]-=d[i]
    if i!=0:
        d[i+1]+=d[i]
    d[i+1]%=mod
#print(d)
print(d[n-1]%mod)

Submission status: Accepted

Solution code:
p = 998244353
n, k = map(int, input().split())
LRs = []
for j in range(k):
    lj, rj = map(int, input().split())
    LRs.append((lj, rj))
A = [0] * (n + 1)
i0 = min(lj for lj, rj in LRs)
A[0] = 1
A[i0] = 1
for i in range(i0 + 1, n):
    A[i] = A[i - 1]
    for j in range(k):
        lj, rj = LRs[j]
        if i - lj >= 0:
            A[i] += A[i - lj]
        if i - 1 - rj >= 0:
            A[i] -= A[i - 1 - rj]
        A[i] %= p
print(A[n - 1])

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
L = []
for _ in range(K):
  l,r = map(int,input().split())
  L.append((l,r))
DP = [0] * N
DP[0] = 1
con = [0] * (N + 1)
con[1] = 1
for i in range(1 , N):
  s = 0
  for l,r in L:
    s += con[max(0 , i - l + 1)] - con[max(0 , i - r)]
  DP[i] = s
  con[i + 1] = (con[i] + DP[i]) % 998244353
  
print(DP[N - 1] % 998244353)

Submission status: Accepted

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

INF = 998244353

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

dp = [0] * N
dp[0] = 1
a_sum = [0] * N
a_sum[0] = 1
for i in range(1, N):
    for lr in LR:
        if i - lr[0] >= 0:
            if i - lr[1]-1 >= 0:
                # print(i, lr, dp[i], i-lr[0], i-lr[1]-1, a_sum[i-lr[0]], a_sum[i-lr[1]-1])
                dp[i] = dp[i] + a_sum[i-lr[0]] - a_sum[i-lr[1]-1]
            else:
                dp[i] = dp[i] + a_sum[i-lr[0]]
    dp[i] %= INF
    a_sum[i] = a_sum[i-1] + dp[i]
    a_sum[i] %= INF
    # print(i, dp, a_sum)
print(dp[-1])

Submission status: Accepted

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

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

dp = [0] * (N + 1)
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = max(i - R[j], 1)
        ri = i - L[j]
        if ri < 1:
            continue
        dp[i] += (dp_sum[ri] - dp_sum[li - 1]) % MOD
    dp_sum[i] = (dp_sum[i - 1] + dp[i]) % MOD

print(dp[-1] % MOD)

Submission status: Accepted

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

LR = []

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

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

for i in range(2, N + 1):
    for l, r in LR:
        if i - l >= 1:
            dp[i] += (cumsum[i - l] - cumsum[max(i - r - 1, 0)]) % MOD
    dp[i] = dp[i] % MOD
    cumsum.append(cumsum[-1] + dp[i])

print(dp[-1] % MOD)

Submission status: Accepted

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

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

for i in range(N):
  for j in range(K):
    dp[i]+=dpc[max(i-L[j]+1,0)]-dpc[max(i-R[j],0)]
  dp[i]%=998244353
  dpc[i+1]=dpc[i]+dp[i]

print(dp[N-1])

Submission status: Accepted

Solution code:
import numpy as np  # noqa
import numba
from numba import njit, b1, i4, i8, f8

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

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


jumps = np.array(jumps)


@njit((i8, i8, i8[:]), cache=True)
def main(N, m, jumps):
    L, R = jumps[::2], jumps[1::2]
    dpsum = np.zeros(N + 1)
    dp = np.zeros(N + 1)
    dp[1] = dpsum[1] = 1

    for i in range(2, N + 1):
        for j in range(len(L)):
            mn = max(0, i - R[j])
            mx = max(mn, i - L[j])
            dp[i] = (dp[i] + dpsum[mx] - dpsum[mn - 1]) % m
        dpsum[i] = (dp[i] + dpsum[i - 1]) % m
    return dp[N]


print(int(main(N, m, jumps)))

Submission status: Accepted

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

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

    dp = np.zeros(N + 1, dtype=np.int64)
    dp[1] = 1
    cumsum = np.zeros(N + 1, dtype=np.int64)
    cumsum[1] = 1
    for i in range(2, N + 1):
        for left_section, right_section in section:
            left = max(i - right_section - 1, 0)
            right = i - left_section
            if right < 0:
                continue
            dp[i] += cumsum[right] - cumsum[left]
        cumsum[i] = cumsum[i - 1] + dp[i]
        dp[i] %= MOD
        cumsum[i] %= MOD
    print(dp[N] % MOD)
    # print(dp)
    # print(cumsum)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

count = 0
for _ in range(K):
    a,b = map(int, input().split())
    for _1 in range(_):
        x,y = L[_1],R[_1]
        if x <= a <= y or x <= b <= y :
            L[_1] = min(a,x)
            R[_1] = max(b,y)
            break
    else:
        L[_],R[_] =a,b
        count += 1
L,R = L[0:count+1],R[0:count+1]

MOD = 998244353
dp = [0]*(4*10**5+100)
for l, r in zip(L, R):
    dp[min(N + 1, 1 + l)] += 1
    dp[min(N + 1, 1 + r + 1)] -= 1

for i in range(2,N+1):
    number = dp[i-1] + dp[i]
    if number > MOD:
        number -= MOD
    dp[i] = number
    for l, r in zip(L,R):
        dp[i + l] += number
        dp[i + l] %= MOD
        dp[i + r +1] -= number
        dp[i + r +1] %= MOD

print(dp[N]%MOD)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
lr=[list(map(int,input().split())) for _ in range(k)]
accum=[0]*k
dp=[0]*(n+1)
dp[1]=1
mod=998244353
for num in range(2,n+1):
    for i in range(k):
        l,r=lr[i]
        if l<num<=r:
            accum[i]+=dp[num-l]
            accum[i]%=mod
            dp[num]+=accum[i]
        elif r<num:
            accum[i]+=dp[num-l]-dp[num-r-1]
            accum[i]%=mod
            dp[num]+=accum[i]
        dp[num]%=mod
print(dp[n])

Submission status: Accepted

Solution code:
# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
import bisect
# import heapq # priolity-queue
# from time import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

# mod = int(1e9+7)
mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n,k = readInt()
    l = []
    r = []
    for i in range(k):
        a,b = readInt()
        l.append(a)
        r.append(b)
    dp = [0 for i in range(n+1)]
    dp[1] = 1
    dpsum = [0 for i in range(n+1)]
    dpsum[1] = 1
    for i in range(2,n+1):
        for j in range(k):
            lj = max(1,i - r[j])
            rj = i - l[j]
            if rj<1:
                continue
            dp[i] += dpsum[rj] - dpsum[lj-1]
            dp[i] %= mod
        dpsum[i] = dpsum[i-1] + dp[i]
    print(dp[n])
    return

if __name__=='__main__':
    main()

Submission status: Accepted

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

mod = 998244353

m_list = []

for _ in range(k):
    m_list.append(list(map(int, input().split())))

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

dp_sum = [0]*n
dp_sum[0] = 1

for i in range(1, n):
    for j in range(k):
        l, r = m_list[j]
        il = i-l
        ir = i-r-1
        if il < 0:
            continue
        else:
            if ir < 0 :
                dp[i] += dp_sum[il]
            else:
                dp[i] += dp_sum[il] - dp_sum[ir]
            dp[i] %= mod
    dp_sum[i] = dp_sum[i-1] + dp[i]
    dp_sum[i] %= mod

print(dp[n-1] % mod)

Submission status: Accepted

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    # mod = 1000000007                # 10^9+7
    mod = 998244353
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
    
    
    n, k = mi()
    L = [lmi() for _ in range(k)]
    dp = [0] * n
    dp[0] = 1
    acc = [0] * (n + 1)    # acc[i] = sum(dp[:i])
    acc[1] = 1
    for i in range(1, n):
        s = 0
        for l, r in L:
            # sum(dp[i-r:i-l+1]) を足していく
            s = (s + acc[max(0, i - l + 1)] - acc[max(0, i - r)]) % mod
        dp[i] = s
        acc[i+1] = (acc[i] + dp[i]) % mod
        # debug(dp)
        # debug(acc)
    print(dp[n-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
C = 998244353
L = [None]*K
for j in range(K):
    l, r = list(map(int, input().split()))
    L[j] = [l, r+1]

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

for i in range(N-1):
    if i > 0:
        imsm[i] = imsm[i-1]+imos[i]
        dp[i] = imsm[i] % C
    a = dp[i]
    # print(i,dp)
    for j in range(K):
        l, r = L[j]
        nl = min(i+l, N)
        nr = min(i+r, N)
        imos[nl] += a
        imos[nr] -= a
        # print(i, imos)
dp[N-1] = (imsm[N-2]+imos[N-1]) % C
print(dp[N-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    mod=998244353
    n, k = map(int, input().split())
    lr = []
    for i in range(k):
        l, r = map(int, input().split())
        lr.append((l, r))
    ans=[1]
    acc_ans=[1]
    for i in range(1, n):
        wa = 0
        for l, r in lr:
            if i-r > 0:
                wa+=-acc_ans[i-r-1]+acc_ans[i-l]
            elif i-l>=0:
                wa+=acc_ans[i-l]
        wa%=mod
        ans.append(wa)
        acc_ans.append(wa+acc_ans[-1])
    print(ans[-1])


if __name__ == '__main__':
    main()