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:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

mod = 998244353

class BIT:
	def __init__(self, n):
		self.n = n
		self.nums = [0] * (n+1)
		
	def add(self, i, x):
		n, nums = self.n, self.nums
		i += 1
		while i <= n:
			nums[i] += x
			i += i & -i
	
	def sum(self, i):
		nums = self.nums
		s = 0
		i += 1
		while i:
			s += nums[i]
			i -= i & -i
		return s

N, K = rl()
lr = []
for i in range(K):
	l, r = rl()
	lr.append((l,r))

bit = BIT(N+1)
bit.add(1, 1)
bit.add(2, -1)

ans = 0
for i in range(1, N+1):
	s = bit.sum(i)
	s %= mod
	#print('s', s)
	for k in range(K):
		l, r = lr[k]
		if i+l <= N:
			#print('l', i+l, s)
			bit.add(i+l, s)
			if i+r+1 <= N:
				#print('r', i+r+1, -s)
				bit.add(i+r+1, -s)
			else:
				ans += s
				ans %= mod
print(ans)
#print(bit.sum(N) % mod)

Submission status: Accepted

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

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:
'''
dp[i] = number of way to go from cell 0 to cell i
dp[0] = 1
for i in range(1, N):
    dp[i] = sum(dp[i - d] for d in seg for seg in segs)
Store dp in BIT
'''

mod = 998244353


class BIT:
    '''
    All methods use 0-based index while the internal use 1-based index
    '''

    def __init__(self, N, val=0):
        self.data = [val] * (N + 1)
        self.N = N

    def add_at(self, idx, val):
        i = idx + 1
        while i <= self.N:
            self.data[i] += val
            self.data[i] %= mod
            i += i & (-i)

    def sum_to(self, idx):
        res = 0
        i = idx + 1
        while i > 0:
            res += self.data[i]
            res %= mod
            i -= i & (-i)
        return res

    def range_sum(self, l, r):  # [l, r]
        return ((self.sum_to(r) - self.sum_to(l - 1)) + mod) % mod

    def __str__(self):
        data = [self.range_sum(i, i) for i in range(self.N)]
        return '[ ' + ' '.join(map(str, data)) + ' ]'


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

bit = BIT(N, 0)
bit.add_at(0, 1)
for i in range(N):
    for (l, r) in segs:
        lb = max(i - r, 0)
        ub = i - l
        if ub >= 0:
            val = bit.range_sum(lb, ub)
            bit.add_at(i, val)
print(bit.range_sum(N - 1, N - 1))

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
MOD = 998244353
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 = [NLI() for _ in range(K)]
    dp = [0] * (N*2+10)
    dp[1] = 1
    now = 0

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

    print(dp[N])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]
    n,k=map(int,input().split())
    MOD=998244353
    lr=[list(map(int,input().split())) for _ in range(k)]
    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 lr:
        li=i-r
        ri=i-l
        if r<0:continue
        li=max(1,li)
        dp[i]+=dpsum[ri]-dpsum[li-1]
      dpsum[i]=(dpsum[i-1]+dp[i])%MOD
    print(dp[n]%MOD)
    
if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
#
import sys
import math
import itertools

# 整数をいくつか入力
n,k = (int(i) for i in input().split())


lr = [[int(i) for i in input().split()] for i in range(k)] 

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

for i in range(2,n+1):
    for a in lr:
        if a[0] < i:
            dp[i] += ans[i-a[0]]
            if a[1] < i-1:
                dp[i] -= ans[i-a[1]-1]
    dp[i] = dp[i] % 998244353
    ans[i]=ans[i-1]+dp[i]

print(dp[n]%998244353)

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

mod = 998244353

N, K = rl()
lr = []
for i in range(K):
	l, r = rl()
	lr.append((l,r))
lr.sort()

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

ans = 0
s = 0
flags = [1] * K
for i in range(1, N+1):
	s += dp[i]
	s %= mod
	for k in range(K):
		if flags[k] == 0:
			break
		l, r = lr[k]
		if i+l <= N:
			dp[i+l] += s
			if i+r+1 <= N:
				dp[i+r+1] -= s
			else:
				ans += s
				ans %= mod
				break
		else:
			flags[k] = 0
			break
print(ans)

Submission status: Accepted

Solution code:
#配るDP
n,k=map(int,input().split())
l=[0]*k
r=[0]*k
for j in range(k):
  l[j],r[j] = map(int,input().split())
p=998244353
dp=[0]*(n+max(r)+100)
dp[1]=1
dp[2]=-1
for i in range(1,n+1):
  dp[i] += dp[i-1]
  dp[i] %= p
  
  for lj,rj in zip(l,r):
    dp[i+lj] += dp[i]
    dp[i+lj] %= p
    dp[i+rj+1] -= dp[i]
    dp[i+rj+1] %= p
print(dp[n])

Submission status: Accepted

Solution code:
#配るDP
n,k=map(int,input().split())
l=[0]*k
r=[0]*k
for j in range(k):
  l[j],r[j] = map(int,input().split())
p=998244353
dp=[0]*(n+max(r)+100)
dp[1]=1
dp[2]=-1
for i in range(1,n+1):
  dp[i] += dp[i-1]
  dp[i] %= p
  
  for lj,rj in zip(l,r):
    dp[i+lj] += dp[i]
    dp[i+lj] %= p
    dp[i+rj+1] -= dp[i]
    dp[i+rj+1] %= p
print(dp[n])

Submission status: Accepted

Solution code:
def main():
    mod=998244353
    n,k=map(int,input().split())
    region=[]
    for _ in range(k):
        a,b=map(int,input().split())
        region.append((a,b))

    #dp[i]はマスiに行く方法の個数
    #workにdp[i-1]からの増減分を保持
    dp=[0]*(n+1)
    work=[0]*(n+1)

    #initialize
    for j in region:
        if 1+j[0]<=n:
            work[1+j[0]]+=1
        if 1+j[1]+1<=n:
            work[1+j[1]+1]-=1    

    for i in range(2,n+1):
        dp[i]=dp[i-1]+work[i]
        dp[i]%=mod
        for j in region:
            if i+j[0]<=n:
                work[i+j[0]]+=dp[i]
                work[i+j[0]]%=mod
            if i+j[1]+1<=n:
                work[i+j[1]+1]-=dp[i]
                work[i+j[1]+1]%=mod
    print(dp[n])


main()

Submission status: Accepted

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

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

MOD = 998_244_353


@njit((i8, i8[:]), cache=True)
def main(N, LR):
    L, R = LR[::2], LR[1::2]
    K = len(L)
    F = np.zeros(N + 10, np.int64)
    F[0] = 1
    for n in range(1, N + 10):
        F[n] += F[n - 1]
        for k in range(K):
            l, r = L[k], R[k] + 1
            if n - l >= 0:
                F[n] += F[n - l]
            if n - r >= 0:
                F[n] -= F[n - r]
        F[n] %= MOD
    ans = F[N - 1] - F[N - 2]
    return ans % MOD


N, K = map(int, readline().split())
LR = np.array(read().split(), np.int64)

print(main(N, LR))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
mod = 998244353
L = [list(map(int, input().split())) for _ in range(K)]
D = {1: -1}
dp = [0 for _ in range(N)]
dp[0] = 1
for i in range(K):
    if L[i][0] in D:
        D[L[i][0]] -= 1
    else:
        D[L[i][0]] = -1
    if L[i][1]+1 in D:
        D[L[i][1]+1] += 1
    else:
        D[L[i][1]+1] = 1
dp[1] = -D[1] - 1
for i in range(2, N):
    for j in D:
        if i >= j:
            dp[i] += (-D[j]) * dp[i-j]
            dp[i] %= mod
print(dp[N-1])

Submission status: Accepted

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

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

cum = [0 for _ in range(2 * N + 1)]
cum[1] = 1

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

Submission status: Accepted

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

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

area.sort()
d = [0] * N
a = [0] * N


def func(pos):
    for l, r in area:
        if pos + l - 1 < N:
            a[pos + l-1] += d[pos]
        if pos + r < N:
            a[pos + r] -= d[pos]
    d[pos+1] = (d[pos] + a[pos]) % 998244353


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

print(d[N-1] % 998244353)

Submission status: Accepted

Solution code:
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:
        dp[i+l] += now
        dp[i+r+1] -= now
    now += dp[i+1]
    now %= mod
print(now)

Submission status: Accepted

Solution code:
n,k = (int(x) for x in input().split())
lr = []
for _ in range(k):
    l,r = (int(x) for x in input().split())
    lr.append((l,r))
lr.sort()

mod = 998244353

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

for i in range(2,n+1):
    cnt = 0
    for l,r in lr:
        if l >= i:
            break
        else:
            cnt += dp[i-l] - dp[max(0,i-r-1)]
    dp[i] = (dp[i-1] + cnt) % mod

print(cnt%mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

mod = 998244353

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

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

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

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

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
LRs = []
P = 998244353
for _ in range(K):
  l,r = map(int, input().split())
  LRs.append((l,r))
  
memo = [0]*(N+2)
memo[1] = 1
memo[2] = -1
rlt = [0]*(N+2)
rlt[1] = 1


for i in range(1,N+1):
  for t in LRs:
    l = min(t[0]+i,N+1)
    r = min(t[1]+i+1,N+1)
    memo[l] = memo[l]+rlt[i]
    memo[r] = memo[r]-rlt[i]
  rlt[i+1] = (rlt[i]+memo[i+1])%P
  
print(rlt[N])

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
# from heapq import heappop, heappush
# from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
# import math
# from itertools import product, accumulate, combinations, product
# import bisect
# import numpy as np
# from copy import deepcopy
#from collections import deque
# from decimal import Decimal
# from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())


def run():
    N, K = mapline()
    G = []
    for i in range(K):
        l, r = mapline()
        G.append((l, r))

    dp = [0]* N
    dp[0] = 1
    a = [0] * N
    a[1] = -1
    for k in range(0, N):
        if k >= 1:
            dp[k] = (dp[k-1] + a[k]) % mod
        for l, r in G:
            if k+l <= N-1:
                a[k+l] = (a[k+l] + dp[k]) % mod
            if k+r+1 <= N-1:
                a[k+r+1] = (a[k+r+1] - dp[k]) % mod

    print(dp[N-1])




if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
LR = [list(map(int,input().split())) for i in range(K)]
LR.sort()
mod = 998244353
ma = [0] * N
ma[0] = 1
for i in range(N):
    if i >1:
        ma[i] += ma[i-1]
    p = ma[i]%mod
    if p != 0:
        for l,r in LR:
            if i+l <N:
                ma[i+l] += p
            else:
                break
            if i+r+1<N:
                ma[i+r+1] -= p
print(ma[N-1]%mod)

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split()))
p = 998244353
LR = []
for i in range(K):
    LR.append(list(map(int,input().split())))
T = [0]*(2*N+10)
T[1] = 1
S = [0]*(2*N+10)
S[1] = 1
S[2] = -1
for i in range(1,N):
    for j in range(K):
        L,R = LR[j]
        S[i+L]=S[i+L]+T[i]
        S[i+R+1]=S[i+R+1]-T[i]
    T[i+1] = (T[i]+S[i+1])%p
print(T[N])

Submission status: Accepted

Solution code:
import math

CON = 998244353

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

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

def solve():
    dp[1] = 1
    cs[1] = 1

    for i in range(2, N + 1):
        for pts in LR:
            if i - pts[0] > 0: dp[i] += cs[i-pts[0]] 
            if i - pts[1] > 0: dp[i] -= cs[i-(pts[1] + 1)] 
        dp[i] = dp[i] % CON
        cs[i] = (cs[i-1] + dp[i]) % CON

    print(dp[N])

solve()

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq

n,k = ma()
mod =998244353
lr=[]
for i in range(k):
    lr.append(lma())
lr.sort()
dp = [0]*(n+1) #dp[i]:和がiになる組み合わせの数 dp[i] = sum_{d in S} dp[i-d]を高速化したい
dp[0]=1
tot=[0]*(n+1) #tot[i] = sum dp[0:i] 和がi以下になる組み合わせ
tot[0]=1
for i in range(1,n):
    for l,r in lr:
        if i-l<0:
            continue
        elif i-r<0:
            r=i
        dp[i]+=tot[i-l]-tot[i-r-1]
        dp[i]%=mod
    tot[i]=(tot[i-1] + dp[i])%mod
    
print(dp[n-1])

Submission status: Accepted

Solution code:
MOD = 998244353
class SegmentTree:
    def __init__(self, a):
        self.padding = 0
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)//2] = self.seg_data[i] + self.seg_data[i-1]
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] += x
        self.seg_data[idx] %= MOD
        while idx:
            idx = (idx-1) // 2
            self.seg_data[idx] = (self.seg_data[2*idx+1] + self.seg_data[2*idx+2]) % MOD
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.seg_data[self.N - 1 + i] % MOD
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1&1 == 0: # idx1が偶数
                    result = (result + self.seg_data[idx1]) % MOD
                if idx2&1 == 1: # idx2が奇数
                    result = (result + self.seg_data[idx2]) % MOD
                    idx2 -= 1
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            return result


N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(K)]
a = [0] * (N+1)
a[1] = 1
dp = SegmentTree(a)
for i in range(2, N+1):
    for l, r in LR:
        ll = max(0, i - l)
        rr = max(0, i - r)
        dp.update(i, dp.query(rr, ll+1))

print(dp.query(N, N+1))

Submission status: Accepted

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

    for i in range(2, n+1):
        dp[i] = dp[i-1]
        for l, r in LRs:
            dp[i] += dp[max(i-l, 0)] - dp[max(i-r-1, 0)]
            dp[i] %= 998244353

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

Z = 998244353


def input():
    return sys.stdin.readline().rstrip('\n')


def calc(N, K, LR):
    f = [0] * N
    a = [0] * N
    f[0] = 1
    a[0] = -1
    for i in range(N - 1):
        for (l, r) in LR:
            if i + l - 1 < N:
                a[i + l - 1] = a[i + l - 1] + f[i]
            if i + r < N:
                a[i + r] = a[i + r] - f[i]
        f[i + 1] = (a[i] + f[i]) % Z
    return f[N - 1]


(N, K) = tuple([int(s) for s in input().split()])
LR = [tuple([int(s) for s in input().split()]) for _ in range(K)]
print(calc(N, K, LR))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
cum = [0, 1]
dp = [0, 1]

lr = [list(map(int, input().split())) for _ in range(k)]    
mod = 998244353
# i: 目標のマス
def check(i):
    res = 0
    for l, r in lr:
        if i - l < 1:
            continue
        res += cum[i-l] - cum[max(i-r-1,0)]
        res %= mod
    return res


for i in range(2,n+1):
    dp.append(check(i))
    cum.append((cum[-1]+dp[-1])%mod)

print(dp[-1])

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,K = LI()
L,R = LIR(K,2)

LR = [(L[i],R[i]) for i in range(K)]
LR.sort(key=lambda x:x[0])

L = [LR[i][0] for i in range(K)]
R = [LR[i][1] for i in range(K)]

S = [0]*K

dp = [0]*N
dp[0] = 1
for i in range(N):
    for k in range(K):
        if i > R[k]:
            S[k] += dp[i-L[k]] - dp[i-R[k]-1]
            S[k] %= mod
        elif i < L[k]:
            S[k] += 0
        else:
            S[k] += dp[i-L[k]]
            S[k] %= mod
        dp[i] += S[k]
        dp[i] %= mod


print(dp[-1])

Submission status: Accepted

Solution code:
def main():
    Q = 998244353
    N, K = map( int, input().split())
    LR = [ tuple( map( int, input().split())) for _ in range(K)]
    LR.sort()
    dp = [0]*(N+1)
    dp[1] = 1
    S = [0]*K
    for i in range(2,N+1):
        for j, (l, r) in enumerate(LR):
            if l <= i:
                S[j] += dp[i-l]
            if r < i:
                S[j] -= dp[i-r-1]
            S[j] %= Q
        dp[i] += sum(S)
        dp[i] %= Q
    # print(dp)
    print(dp[N])
        
if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp = [0]*(N+1)
dp_sum = [0]*(N+1)
dp[1] = dp_sum[1] = 1
for i in range(2,N+1):
    for l,r in move:
        if 0<i-l:
            dp[i] += dp_sum[i-l]
            if 0<i-r-1:
                dp[i] -= dp_sum[i-r-1]
        dp[i] %= mod
    dp_sum[i] = dp_sum[i-1] + dp[i]
            
print(dp[-1]%mod)

Submission status: Accepted

Solution code:

def solve():
    MOD = 998244353
    N, K = map(int, input().split())
    LR_L = [[int(x) for x in input().split()] for y in range(K)]
    # S = set()
    # for i in range(K):
    #     _l, _r = map(int, input().split())
    #     _s = set(list(range(_l, _r+1)))
    #     S |= _s

    # dp[i] : iに到達する経路数
    dp = [0] * (N+1)
    dp[1] = 1
    dp[2] = -1
    for i in range(1, N+1):
        dp[i] += dp[i-1]
        dp[i] %= MOD
        # for d in S:
        #     if i-d > 0:
        #         dp[i] = (dp[i] + dp[i-d]) % MOD
        for li, ri in LR_L:
            if i + li < N+1:
                dp[i+li] += dp[i]
                dp[i+li] %= MOD
            if i + ri + 1 < N+1:
                dp[i+ri+1] -= dp[i]
                dp[i+ri+1] %= MOD
    print(dp[N])


solve()

Submission status: Accepted

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

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

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

x = 0
for i in range(1,n):
    x = (x+dp[i])%mod
    for l,r in alist:
        if i+l > n:
            continue
        dp[i+l]= (dp[i+l]+x)%mod
        if i+r+1<=n:
            dp[i+r+1] = (dp[i+r+1]-x)%mod
x = (x+dp[n])%mod
print(x)

Submission status: Accepted

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

D = [1]
M = 100
memo = []
memo2 = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      l1 = i - min(i, r)
      r1 = i - l + 1
      l2 = (l1 + M - 1) // M
      r2 = r1 // M
      l3 = (l2 + M - 1) // M
      r3 = r2 // M
      if r3 > l3:
        count += sum(D[l1:l2*M]) + sum(memo[l2:l3*M]) + sum(memo2[l3:r3]) + sum(memo[r3*M:r2]) + sum(D[r2*M:r1])
      elif r2 > l2:
        count += sum(D[l1:l2*M]) + sum(memo[l2:r2]) + sum(D[r2*M:r1])
      else:
        count += sum(D[l1:r1])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
    if len(memo) % M == 0:
      memo2.append(sum(memo[-M:]))
print(D[-1])

Submission status: Accepted

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

import sys
input=sys.stdin.readline

mod=998244353

n,k=map(int,input().split())
arr=[list(map(int,input().split()))+[i] for i in range(k)]
dp=[0]*(n+1)
dp[1]=1
sums=[0]*k
for i in range(2,n+1):
  for l,r,j in arr:
    if l>i:
      continue
    elif l<=i<=r:
      sums[j]+=dp[i-l]
    else:
      sums[j]-=dp[i-r-1]
      sums[j]+=dp[i-l]
    sums[j]%=mod
  for j in range(k):
    dp[i]+=sums[j]
print(dp[n]%mod)

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
#import itertools
#import heapq
#from collections import deque
#d = deque()

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    mod=998244353
    dp=[0]*(2*(10**5)+10)
    dp[0]=1
    n,k=map(int, readline().rstrip().split())
    #s=set()
    #lr=[0]*(2*(10**5)+10)
    ll=[0]*(2*(10**5)+10)
    rr=[0]*(2*(10**5)+10)
    for i in range(k):
        ll[i],rr[i]=map(int, readline().rstrip().split())
    for i in range(n-1):
        if i > 0:
            dp[i]+=dp[i-1]

        if dp[i] == 0:
            continue

        for j in range(k):
            if i+ll[j] <= n:
                dp[i+ll[j]] += dp[i]
                dp[i+ll[j]]%=mod
            if i+rr[j]+1 <= n:
                dp[i+rr[j]+1] -= dp[i]
                dp[i+rr[j]+1]%=mod
    print(dp[n-1])
    #for i in range(n):
    #    if i > 0:
    #        lr[i]+=lr[i-1]
    #    if lr[i] > 0:
    #        s.add(i)

    #arr=list(map(int, readline().rstrip().split()))
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

Solution code:
mod = 998244353
n,k = map(int,input().split())
s = [list(map(int,input().split())) for i in range(k)]
c = [0]*(n+1)
c[0] = 1
for i in range(n):
    for j,k in s:
        if i+j<n+1:
            c[i+j] += c[i]
        if i+k<n:
            c[i+k+1] -= c[i]
    if i>0:
        c[i+1] += c[i] 
        c[i+1] %= mod

print(c[n-1])

Submission status: Accepted

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

s=[0 for _ in range(N+1)]
s[1]=1
for i in range(1,N):
  s[i+1] = s[i]
  for l,r in LR:
    s[i+1]+=(s[max(0,i-l+1)]-s[max(0,i-r)])%P
    s[i+1]%=P
print((s[N]-s[N-1])%P)

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self,len_A, mod):
        self.N = len_A + 10
        self.bit = [0]*(len_A+10)
        self.mod = mod
        
    def query(self,i):
        res = 0
        idx = i+1
        while idx:
            res += self.bit[idx]
            idx -= idx&(-idx)
        return res

    def update(self,i,x):
        idx = i+1
        while idx < self.N:
            self.bit[idx] += x
            self.bit[idx] %= self.mod
            idx += idx&(-idx)

n, k = map(int, input().split())
mod = 998244353
bit = BIT(n,mod)
dp = [0]*(n+3)
lr = []
for i in range(k):
    l, r = map(int, input().split())
    lr.append((l, r))
    if l != r:
        for g in range(l, r+1):
            dp[g] = 1
            bit.update(g, 1)
    else:
        dp[l] = 1
        bit.update(l, 1)
lr.sort()

for i in range(1, n+1):
    ssum = 0
    for g in range(k):
        if i > lr[g][1]:
            ssum += bit.query(i-lr[g][0]) - bit.query(i-lr[g][1]-1)
        else:
            if lr[g][0] < i:
                ssum += bit.query(i-lr[g][0]) 
            break
    dp[i] += ssum
    dp[i] %= mod
    bit.update(i, ssum)
print(dp[n-1])