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:
n, k = map(int, input().split())
mod = 998244353
S = []
for _ in range(k):
    l, r = map(int, input().split())
    S.append([l, r])


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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
L=[]
R=[]
h=[0,1,-1]+[0]*400010
M=998244353
for i in range (k):
    l,r=map(int,input().split())
    L.append(l)
    R.append(r)
N=0
for i in range (1,n):
    N=(N+h[i]+100*M)%M
    for j in range (k):
        h[L[j]+i]+=N
        h[R[j]+i+1]-=N
print(((N+h[n])+100*M)%M)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

for i in range(N):
    DP[i] += cnt
    DP[i] %= mod
    cnt = DP[i]
    for l, r in Move:
        if i + l < N:
            DP[i+l] += DP[i]
        if i + r + 1 < N:
            DP[i + r + 1] -= DP[i]

print(DP[-1])

Submission status: Accepted

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

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


mod = 998244353
n,k = readints()
s = [readints() for i in range(k)]

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

b = [0] * k

for i in range(2,n+1):
    for j in range(k):
        l,r = s[j]
        if i-l>0:
            b[j] += a[i-l]
        if i-r-1>0:
            b[j] -= a[i-r-1]
        a[i] += b[j]
        a[i] %= mod

print(a[-1])

Submission status: Accepted

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

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

for i in range(2, n + 1):
    for l, r in lr:
        if l >= i:
            continue

        ll = max(1, i - r)
        rr = i - l
        dp[i] += cumsum[rr] - cumsum[ll - 1]
        dp[i] %= mod
    cumsum[i] = cumsum[i - 1] + dp[i]
    cumsum[i] %= mod

print(dp[n] % mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 998244353

class BIT2:
    def __init__(self, N):
        self.N = (N+1)
        self.data0 = [0] * (N+1)
        self.data1 = [0] * (N+1)
        
    def _add(self, data, k, x):
        while k < self.N: #k <= Nと同義
            data[k] += x
            k += k & -k

    def _sum(self, data, k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s

    def add(self, l, r, x):
        self._add(self.data0, l, -x*(l-1))
        self._add(self.data0, r, x*(r-1))
        self._add(self.data1, l, x)
        self._add(self.data1, r, -x)

    def sum(self, l, r):
        return self._sum(self.data1, r-1) * (r-1) + self._sum(self.data0, r-1) - self._sum(self.data1, l-1) * (l-1) - self._sum(self.data0, l-1)
    
N, K = map(int, readline().split())
bit = BIT2(N)
d = []
for _ in range(K):
    L,R = map(int, readline().split())
    d.append((L,R))

bit.add(1,2,1)

for i in range(2,N+1):
    for k in range(K):
        L,R = d[k]
        tmp = bit.sum(max(1,i-R),max(1,i-L+1))%MOD
        bit.add(i,i+1,tmp)
print(bit.sum(N,N+1)%MOD)

Submission status: Accepted

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))
    
A = [0]*(N+1)
A[1] = 1
S = [0]*(N+1)
S[1] = 1

for i in range(2,N+1):
    for k in range(K):
        L,R = data[k]
        A[i] += (S[max(0,i-L)]- S[max(0,i-R-1)]) % MOD
        A[i] %= MOD
    S[i] = (S[i-1] + A[i]) % MOD

print(A[N])

Submission status: Accepted

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)
A = [0]*(N+1)
A[1] = 1
S = [0]*(N+1)
S[1] = 1

for i in range(2,N+1):
    for k in range(K):
        L,R = data[k]
        A[i] += (S[max(0,i-L)]- S[max(0,i-R-1)]) % MOD
        A[i] %= MOD
    S[i] = (S[i-1] + A[i]) % MOD

print(A[N])

Submission status: Accepted

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

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

MOD = 998244353
for i in range(1, N):
    for l, r in R:
        a = max(i - r, 0)
        b = i - l
        if b < 0:
            continue
        W[i + 1] += (W[b + 1] - W[a])
        W[i + 1] %= MOD
    W[i + 1] += W[i]
    
print(W[N] - W[N - 1])

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 998244353


def main():
    N, K, *LR = map(int, read().split())
    interval = [(l, r) for l, r in zip(*[iter(LR)] * 2)]

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

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

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

    print(dp[N - 1])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 998244353


def main():
    N, K, *LR = map(int, read().split())
    interval = [(l, r) for l, r in zip(*[iter(LR)] * 2)]

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

    for i in range(1, N + 1):
        dp[i] = (dp[i] + dp[i - 1]) % MOD
        for l, r in interval:
            if i + l <= N:
                dp[i + l] += dp[i]
                if i + r + 1 <= N:
                    dp[i + r + 1] -= dp[i]

    print(dp[N])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 998244353


def main():
    N, K, *LR = map(int, read().split())
    interval = [(l, r) for l, r in zip(*[iter(LR)] * 2)]

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

    for i in range(1, N + 1):
        dp[i] = (dp[i] + dp[i - 1]) % MOD
        cur = dp[i]
        for l, r in interval:
            if i + l <= N:
                dp[i + l] += cur
                dp[min(i + r + 1, N + 1)] -= cur

    print(dp[N])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 998244353

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

E = [0] * N

def update(i, v):
	while i < N:
		E[i] = (E[i] + v) % MOD
		i |= i+1

def query(i):
	r = 0
	while i > 0:
		r += E[i-1]
		i &= i-1

	return r % MOD

update(0, 1)
update(1, -1)

for i in range(N-1):
	v = query(i+1)
	for L, R in P:
		if i + L < N:
			update(i+L, v)

			if i + R + 1 < N:
				update(i+R+1, -v)


print(query(N))

Submission status: Accepted

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
import numpy as np
#import sympy
import math
md = 998244353

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

for l,r in lr:
    s |= set(range(l,r+1))


dp = [0]*(n+1)
dp[1]=1
#dp[2]=-1
c = [0]*(n+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]
                dp[i+r+1] %= md

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

Submission status: Accepted

Solution code:
p = 998244353
n, k = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(k)]
DP = [0] * (2 * n + 1)
DP[0] = 1
DP[1] = -1
for i in range(n):
    for l, r in LR:
        DP[i + l] += DP[i]
        DP[i + r + 1] -= DP[i]
    DP[i + 1] += DP[i]
    DP[i + 1] %= p
print(DP[n - 1])

Submission status: Accepted

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

kukan = list()
for i in range(K):
  l, r =  map(int, input().split())
  kukan.append((l, r))
dp = [0] * (N+1)
dp[1] = 1
dp_sum = [0] * (N+1)
dp_sum[1] = 1
for i in range(0, N+1):
  for j in range(K):
    from_l = i - kukan[j][1]
    from_r = i - kukan[j][0]
    if from_r < 0:
      continue
    else:
      from_l = max(1, from_l)
      dp[i] += dp_sum[from_r] - dp_sum[from_l - 1]
      dp[i] %= 998244353
  dp_sum[i] = dp[i] + dp_sum[i-1]
print(dp[N] % 998244353)

Submission status: Accepted

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)%998244353
toori[2*10**5+1]+=aaa


for now in range(2,n):#nowが今の場所
    hueru=0
    for a,i in enumerate (root):
        hueru+=(toori[2*10**5+now-i[0]] - toori[2*10**5+now-1-i[1]])
    aaa+=hueru
    aaa%=998244353
    toori[2*10**5+now]+=aaa
    toori[2*10**5+now]%=998244353
    


print(toori[2*10**5+n-1]%998244353)

Submission status: Accepted

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
    for i in range(1, N):
        for l, r in D:
            if i - l >= 0:
                acc += dp[i-l]
                acc %= MOD
            if i - r - 1 >= 0:
                acc -= dp[i-r-1]
                acc %= MOD
        dp[i] = acc
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
p = 998244353
n, k = map(int, input().split())
LRs = [tuple(map(int, input().split())) for _ in range(k)]
A = [0] * (2 * n + 1)
for lj, rj in LRs:
    A[lj] += 1
    A[rj + 1] -= 1
s = 0
for i in range(1, n):
    s = (s + A[i]) % p
    for lj, rj in LRs:
        A[i + lj] += s
        A[i + rj + 1] -= s
print(s)

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

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

for i in range(N):
  for l, r in move:
    dp[i+l] += dp[i]
    dp[i+l] %= mod
    dp[i+r+1] -= dp[i]
    dp[i+r+1] %= mod
  if i:
    dp[i+1] += dp[i]
  dp[i] %= mod

print(dp[N-1])

Submission status: Accepted

Solution code:
MOD = 998244353

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

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

for i in range(1,N):
    for L, R in l:
        dp[i] += sdp[max(0,i - L+1)] - sdp[max(0,i - R)]
        dp[i] %= MOD
    sdp[i+1] = sdp[i] + dp[i]
    sdp[i+1] %= MOD

print(dp[N-1])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
moves = [tuple(map(int, input().split())) for _ in range(K)] #Sを構成する区間の情報
MOD = 998244353

DP = [0 for _ in range(N)] #DP[n]で0からnまで動く動き方の数
DP[0] = 1
DP_sum = [0 for _ in range(N)] #のちのためにDPの累積和を格納するための配列を確保する
DP_sum[0] = 1

for n in range(1,N):
  # やりたいこと DP[n] = Σ_(集合Sに属するiについて) DP[n-i]
  # しかし、上記右辺の和を愚直に計算するとTLEする
  # → Sが区間10個以下の和集合であることに注目。区間和は、累積和の差を使えばO(1)で計算できる。
  for l,r in moves:
    # DP[n] += DP[n-l] + DP[n-l-1] + … + DP[n-r]の計算
    if n-l >= 0:
      DP[n] += DP_sum[n-l]
      if n-r-1 >= 0: #右端が-1に到達する場合には、以下の処理は行わない。
        DP[n] -= DP_sum[n-r-1]
    DP[n] %= MOD
    
  DP_sum[n] = (DP_sum[n-1] + DP[n]) % MOD #次以降のnのため、累積和を更新
  
print(DP[N-1] % MOD)

Submission status: Accepted

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

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

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

print(dp[n])

Submission status: Accepted

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] - dp[N-1])%998244353)

Submission status: Accepted

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


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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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] - DP[N-1])%998244353)

Submission status: Accepted

Solution code:
# 解説を見て解き直し
N, K = [int(x) for x in input().split()]

ranges = [tuple(int(x) for x in input().split()) for _ in range(K)]
ranges.sort()
p = 998244353

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

for i in range(2, N + 1):
    dp = 0
    for l, r in ranges:
        rj = i - l
        lj = max(1, i - r)  # 1以上
        if rj <= 0: continue
        dp += dpsum[rj] - dpsum[lj - 1]
        dp %= p
    dpsum[i] = dpsum[i - 1] + dp
    dpsum[i] %= p

print(dp)

Submission status: Accepted

Solution code:
# 解説を見て解き直し
N, K = [int(x) for x in input().split()]

ranges = [tuple(int(x) for x in input().split()) for _ in range(K)]
ranges.sort()
p = 998244353

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

for i in range(2, N + 1):
    dp = 0
    for l, r in ranges:
        rj = max(0, i - l)
        lj = max(1, i - r)
        dp += dpsum[rj] - dpsum[lj - 1]
        dp %= p
    dpsum[i] = dpsum[i - 1] + dp
    dpsum[i] %= p

print(dp)

Submission status: Accepted

Solution code:
# 解説を見て解き直し
N, K = [int(x) for x in input().split()]

ranges = [tuple(int(x) for x in input().split()) for _ in range(K)]
ranges.sort()
p = 998244353

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

for i in range(2, N + 1):
    for l, r in ranges:
        rj = i - l
        lj = max(1, i - r)  # 1以上
        if rj <= 0: continue

        dp[i] += dpsum[rj] - dpsum[lj - 1]
        dp[i] %= p
    dpsum[i] = dpsum[i - 1] + dp[i]
    dpsum[i] %= p

print(dp[N])

Submission status: Accepted

Solution code:
import math
import sys
import os

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    

# もらうDP(forcus on destination), 区間の和を足しこむ=累積和
N,K = LI()
LRs = [LI() for _ in range(K)]

dp = [0]*(N+1)
cum = [0]*(N+1)
dp[1] = 1
cum[1] = 1
for i in range(2, N+1):
    for j in range(K):
        l, r = LRs[j]
        start = max(0,i-r-1)
        end = max(0,i-l)
        dp[i] += cum[end] - cum[start]
        dp[i] %= MOD
    # 累積和を更新
    cum[i] = (cum[i-1] + dp[i]) % MOD
ans = dp[N]
print(ans)

Submission status: Accepted

Solution code:
def main():
    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)
    s = [0] * (n + 1)
    dp[1] = 1
    s[1] = 1
    for i in range(2, n + 1):
        for j in range(k):
            l = max(1, i - R[j])
            r = i - L[j]
            if r < 1: continue
            dp[i] += s[r] - s[l - 1]
            dp[i] %= MOD
        s[i] = s[i - 1] + dp[i]
        s[i] %= MOD
    print(dp[n])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
ps = []
MOD = 998244353
s = set()
for _ in range(k):
    l,r = map(int, input().split())
    ps.append([l,r])

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

for i in range(1,n):
    for l, r in ps:
        dp[i] += acc[max(0,i-l+1)] - acc[max(0,i-r)]
    acc.append((acc[i] + dp[i])%MOD)
print(dp[n-1]%MOD)

Submission status: Accepted

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    

# もらうDP, 区間の和を足しこむ
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]

dp = [0]*(N+1)
# 組み合わせの数の累積和(区間和を足しこむため)
cum = [0]*(N+1)
dp[1] = 1
cum[1] = 1
for i in range(2, N+1):
    for j in range(K):
        l, r = LRs[j]
        start = max(0,i-r-1)
        end = max(0,i-l)
        # print('l,r: ',l,r)
        # print('start,end', start,end)
        dp[i] += cum[end] - cum[start]
        # dp[i] += cum[i-l]
        # if i - l >= 0:
        #     dp[i] += cum[i-l]
        # if i - (r+1) >= 0:
        #     dp[i] -= cum[i-(r+1)]
    # dp[i] = (dp[i] % MOD + MOD) % MOD
    dp[i] %= MOD
    # 累積和を更新
    cum[i] = (cum[i-1] + dp[i]) % MOD
print(dp[N])

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

Submission status: Accepted

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

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

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

# O(NK)
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(li, 1)
        dp[i] += (cumsum[ri]-cumsum[li-1])%mod
    cumsum[i] = cumsum[i-1]+dp[i]

print(dp[n]%mod)

Submission status: Accepted

Solution code:
MOD = 998244353
N, K = map(int, input().split())
rl = [list(map(int, input().split())) for _ in range(K)]
dp = [0] * (N + 1)
sdp = [0] * (N + 1)
dp[1] = 1
sdp[1] = 1

for i in range(2, N + 1):
    for j in range(K):
        l, r = rl[j][0], rl[j][1]
        tl = max(1, i - r)
        tr = max(0, i - l)
        dp[i] += sdp[tr] - sdp[tl - 1]
        dp[i] %= MOD
    sdp[i] += dp[i] + sdp[i - 1]
    sdp[i] %= MOD

print(dp[N])

Submission status: Accepted

Solution code:
import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n,k=map(int,input().split())
dp=[0]*n
sdp=[0]*(n+1)
sdp[1]=1
dp[0]=1
mod=998244353
lr=[list(map(int,input().split())) for _ in range(k)]
for i in range(1,n):
    for j in range(k):
        l,r=lr[j]
        left=max(0,i-r)
        right=max(0,i-l+1)
        dp[i]+=(sdp[right]-sdp[left])
        dp[i]%=mod
    sdp[i+1]=(sdp[i]+dp[i])%mod
print(dp[-1])

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
# MOD = 10 ** 9 + 7
MOD = 998244353
num_list = []
str_list = []

def main():
    n, k = i_map()
    num_list = i_row_list(k)

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

    for i in range(2, n+1):
        for j in range(k):
            li = i - num_list[j][1]
            ri = i - num_list[j][0]
            if ri < 0:
                continue
            li = max(li, 0)
            dp[i] += dp_sum[ri] - dp_sum[li-1]
            dp[i] %= MOD
        dp_sum[i] = dp_sum[i-1] + dp[i]
    
    print(dp[n]%MOD)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

for p in range(2, n+1):
    for i, j in lr:
        dp[p] += dp[max(p-i, 0)] - dp[max(p-j-1, 0)]
        dp[p] %= mod
    dp[p] += dp[p-1]

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

Submission status: Accepted

Solution code:
import sys
#from collections import deque
#from functools import *
#from fractions import Fraction as f
from copy import *
from bisect import *	
#from heapq import *
from math import gcd,ceil,sqrt
from itertools import permutations as prm,product
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
di=[[-1,0],[1,0],[0,1],[0,-1]]
def inc(d,c,x=1):
	d[c]=d[c]+x if c in d else x
def bo(i):
	return ord(i)-ord('A')	
def li():
	return [int(xx) for xx in input().split()]
def fli():
	return [float(x) for x in input().split()]	
def comp(a,b):
	if(a>b):
		return 2
	return 2 if a==b else 0		
def gi():	
	return [xx for xx in input().split()]
def fi():
	return int(input())
def pro(a): 
	return reduce(lambda a,b:a*b,a)		
def swap(a,i,j): 
	a[i],a[j]=a[j],a[i]	
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())			
def gh():
	sys.stdout.flush()
def isvalid(i,j):
	return 0<=i<n and 0<=j<m and a[i][j]!="."
def bo(i):
	return ord(i)-ord('a')	
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)

t=1
mod=998244353



while t>0:
	t-=1
	n,k=mi()
	d=[0]*(2*n+5)
	a=[]
	for i in range(k):
		a.append(li())
	d[1]=1	
	d[2]=-1
	for i in range(1,n+1):
		d[i]+=d[i-1]
		d[i]%=mod
		for j in range(k):
			d[i+a[j][0]]+=d[i]
			d[i+a[j][1]+1]-=d[i]
	
		
		
	print(d[n])

Submission status: Accepted

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]] = (dp[i+LR[0]] + atai) % 998244353
        if(i+LR[1] <= N):
            dp[i+LR[1]+1] = (dp[i+LR[1]+1] -atai) % 998244353

#    print(dp)

#復元
ruisekiwa = [0]

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