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
D = []
for _ in range(K):
    l, r = map(int, input().split())
    D.append((l,r))
imos = [0]*(N+2)
dp = [0]*(N+1)
imos[0]=1
imos[1]=-1
for i in range(N):
    dp[i] = dp[i-1] + imos[i]
    dp[i] %= MOD
    for a, b in D:
        imos[min(i+a,N+1)] += dp[i]
        imos[min(i+b+1,N+1)] -= dp[i]

print(dp[N-1])

Submission status: Accepted

Solution code:
N, K = [int(s) for s in input().split()]
rans = []
for _ in range(K):
    l, r= [int(s) for s in input().split()]
    rans.append((l, r))
rans.sort()

prev = -1
newrans = []
for ran in rans:
    l, r = ran
    if l <= prev:
        newrans[-1] = max(r, newrans[-1])
    else:
        newrans.append([l,r])
    prev = max(prev, r)

MOD = 998244353

rans = newrans
sums = [0, 1]
s = 1
# print(rans)
for i in range(2, N+1):
    # print(sums, i)
    for ran in rans:
        l = i - ran[0]
        r = max(i - ran[1] - 1, 0)
        # print(l, r, s)
        if l >= 0:
            s = (s + sums[l] - sums[r]) % 998244353
    sums.append(s)
# print(sums)
if N == 1:
    print(1)
else:
    print((sums[-1] - sums[-2]) % 998244353)

Submission status: Accepted

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

N, K = map(int, input().split())
kukans = []

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

kukans = list(sorted(kukans, key=lambda x:x[0]))

ruiseki_dp = [0]
for i in range(1,N+1):
    if i == 1:
        ruiseki_dp.append(1)
    else:
        # たどり着くためにできるマスの動き
        able_kukans = []
        for L,R in kukans:
            if R <= i-1:
                able_kukans.append([L,R])
            elif L <= i-1 < R:
                able_kukans.append([L,i-1])
                break
            else: # i-1 < L
                break
        
        next_dp = 0
        for L, R in able_kukans:
            next_dp = (next_dp+ruiseki_dp[i-L]-ruiseki_dp[i-R-1])%mod

        ruiseki_dp.append((ruiseki_dp[-1]+next_dp)%mod)
    
print((ruiseki_dp[-1]-ruiseki_dp[-2])%mod)

Submission status: Accepted

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

MOD = 998244353
class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self

    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self

    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj

    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self

    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self

    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj

    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

LR.sort(key=lambda x: x[1])
pl = pr = -1
LR2 = []
for l, r in LR:
    if LR2:
        pl, pr = LR2.pop()
        if l <= pl:
            LR2.append((l, r))
        elif l <= pr:
            LR2.append((pl, r))
        else:
            LR2.append((pl, pr))
            LR2.append((l, r))
    else:
        LR2.append((l, r))

dp = [Mint() for _ in range(N + 5)]
dp[1] += 1
dp[2] -= 1
for i in range(1, N):
    dp[i] += dp[i - 1]
    for l, r in LR2:
        nl = min(i + l, N + 1)
        nr = min(i + r, N + 1)
        dp[nl] += dp[i]
        dp[nr + 1] -= dp[i]
dp[N] += dp[N - 1]
print(dp[N])

Submission status: Accepted

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

S = [[int(_) for _ in input().split()] for _ in range(K)]
p = 998244353

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

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

for i in range(1, N):
    for l, r in S:
        s = i - r
        e = i - l
        
        if e >= 0:
            dp[i] += dsum[e]
        if s > 0:
            dp[i] -= dsum[s-1]
        dp[i] %= p
    dsum[i] = dsum[i-1] + dp[i]
    dsum[i] %= p

print(dp[N-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 998244353

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

dist = [0] * (N + 1)
dist[1] = 1
for i in range(1, N + 1):
    dist[i] += dist[i - 1]
    dist[i] %= mod
    for l, r in LR:
        if i + l <= N:
            dist[i + l] += dist[i]
        if i + r + 1 <= N:
            dist[i + r + 1] -= dist[i]
    if i == 1:
        dist[i] = 0

print(dist[N])

Submission status: Accepted

Solution code:
MOD = 998244353

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

# dp[i]: マスiに移動する方法
dp = [0] * 200010
dp[0] = 1

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

print(dp[N-1])

Submission status: Accepted

Solution code:
P = 998244353

def val(x):
	return (x+P)%P

n, k = map(int,input().split())
plages = []
for _ in range(k):
	x,y=map(int,input().split())
	plages+=[[x,y]]
#plages.sort()

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

for i in range(2,n+1):
	for p in plages:
		l = max(0,i-p[1])
		r = max(0,i-p[0])
		add= 0
		if l==0 and r==0:add=0
		elif l==0: add = pref[r]
		else:
			add = val(pref[r]-pref[l-1])
		# ~ print("i = ",i,"p = ",p,"l = ",l, "r = ",r, "add = ",add)
		ans[i] += add
		ans[i]%=P
	pref[i] = pref[i-1]+ans[i]
	pref[i]%=P
	
# ~ print("pref : ",pref)
# ~ print("ans  : ",ans)

print(ans[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

imos=[0]*(n+10)
imos[0]=1

now=0
for i in range(n):
    now+=imos[i]
    for j in range(k):
        l,r=lr[j]
        if i+l>n:
            continue
        imos[i+l]+=now
        imos[i+l]%=mod
        if i+r>n:
            continue
        imos[i+r+1]-=now
        imos[i+r+1]%=mod

print(imos[n-1]%mod)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, K = [int(x) for x in input().split()]
    LR = [[int(x) for x in input().split()] for _ in range(K)]

    MOD = 998244353

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

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

    dp[N] += c


    print(dp[N] % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 998244353

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

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

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


for i in range(1,N+1):
    ruiseki[i]= (ruiseki[i] + ruiseki[i-1])%MOD
    dp[i]=ruiseki[i]
    if i == 1:
        dp[1]=1
    for k in range(K):
        l,r = LR[k]
        ruiseki[min(N+1,i+l)]= (ruiseki[min(N+1,i+l)] + dp[i])%MOD
        ruiseki[min(N+1,i+r+1)]=(ruiseki[min(N+1,i+r+1)] - dp[i])%MOD

print(dp[N])

Submission status: Accepted

Solution code:
#from collections import deque
#from heapq import heapify, heappop, heappush
#from bisect import insort
#from math import gcd
mod = 998244353
#N = int(input())
N, K = map(int, input().split())
LR = []
for k in range(K):
	L, R = map(int, input().split())
	LR.append((L,R))
counter = [0 for _ in range(N)]
for i in LR:
	l = i[0]
	r = i[1]
	if l < N:
		counter[l] += 1
	if r + 1 < N:
		counter[r+1] -= 1
sm = 0
counter[0] = 1
for k in range(1, N):
	counter[k] += sm
	sm = counter[k]%mod
	if sm == 0:
		continue
	for i in LR:
		l = i[0]
		r = i[1]
		if k + l < N:
			counter[k+l] += sm
			counter[k+l] %= mod
		if k + r + 1 < N:
			counter[k+r+1] -= sm
			counter[k+r+1] %= mod
print(counter[-1]%mod)
#A = list(map(int, input().split()))
#flag = True
#for k in range(N):
#ans = 0
#print(ans)
#print('Yes')
#print('No')

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=998244353
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

lst=[0]*(n+1)
lst[0]=1
lst[1]=-1

now=0
# print(lst)
for i in range(n):
    now+=lst[i]
    now%=mod
    for j in range(k):
        l,r=lr[j]
        if i+l<=n:
            lst[i+l]+=now
            lst[i+l]%=mod
        if i+r+1<=n:
            lst[i+r+1]-=now
            lst[i+r+1]%=mod
    # print(lst,now)
ans=0
for i in range(n):
    ans+=lst[i]
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    N, K = read_ints()
    L, R = [], []
    for _ in range(K):
        l, r = read_ints()
        L.append(l)
        R.append(r)
    dp = [0]*N
    prefix = [0]*N
    dp[0] = 1
    prefix[0] = 1
    modulo = 998244353
    for i in range(1, N):
        for k in range(K):
            left = max(0, i-R[k])
            right = i-L[k]
            if right < 0:
                continue
            if left == 0:
                dp[i] = (dp[i]+prefix[right])%modulo
            else:
                dp[i] = (dp[i]+prefix[right]-prefix[left-1])%modulo
        prefix[i] = (prefix[i]+prefix[i-1]+dp[i])%modulo
    return dp[N-1]


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
P = 998244353

N, K = [int(x) for x in input().split()]
intervals = []
for _ in range(K):
    L, R = [int(x) for x in input().split()]
    intervals.append([L, R])

dp = [0]*(N + 1)
csum = [0]*(N + 1)
dp[1] = 1
csum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        L, R = intervals[j]
        dp[i] = (dp[i] +  csum[max(0, i - L)] - csum[max(0, i - R - 1)]) % P
    csum[i] = (csum[i - 1] + dp[i]) % P

ans = dp[N]
print(ans)

Submission status: Accepted

Solution code:
def main():
    MOD = 998244353
    n,k = map(int,input().split())
    LR = []
    for _ in range(k):
        LR.append(tuple(map(int,input().split())))
    
    dp = [0]*(n+1)
    dp[1] = 1
    for i in range(1,n):
        temp = 0
        for l,r in LR:
            ll = max(i+1 - r - 1, 0)
            rr = max(i+1 - l, 0)
            temp+=dp[rr]-dp[ll]
        dp[i+1] = (dp[i] + temp)%MOD
    
    print((dp[n]-dp[n-1])%MOD)
main()

Submission status: Accepted

Solution code:
mod = 998244353

class FenwickTree:
    def __init__(self, n, init_list=None):
        self.n = n
        self.data = [0] * n
        if init_list:
            assert n == len(init_list)
            for i in range(n):
                self.add(i, init_list[i])
        
    def add(self, i, val):
        assert 0 <= i < self.n
        i += 1
        while i <= self.n:
            self.data[i - 1] = (val + self.data[i - 1]) % mod
            i += i & -i #LSBを加算して上の層へ
            
    def update(self, i, val):
        self.add(i, val - self.sum(i, i+1))

    def sum(self, l, r): #[l, r)
        assert  0 <= l <= r <= self.n
        if l != 0:
            return (self.sum(0, r) - self.sum(0, l)) % mod
        ret = 0
        while r > 0:
            ret = (ret + self.data[r - 1]) % mod
            r -= r & -r #LSB減算して上の層へ
        return ret

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

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

ft = FenwickTree(n)
ft.add(0, 1)
for i in range(1, n):
    for l, r in s:
        jl = i - l
        jr = max(i - r, 0)
        if jl < 0:
            continue
        ft.add(i, ft.sum(jr, jl+1) % mod)
print(ft.sum(n-1, n) % mod)

Submission status: Accepted

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

MOD = 998244353  # type: int

def debug(N, st):
    print(*[st.query(i, i+1) for i in range(N)], sep=" ")

def solve(N: int, K: int, L: "List[int]", R: "List[int]"):
    add = lambda a,b: (a+b)%MOD
    st = SegmentTreeLazy([0]*N, 0, 0, add, add, add)
    st.update(0, 1, 1)
    #debug(N, st)
    for i in range(N):
        #debug(N, st)
        v = st.query(i, i+1)
        for l, r in zip(L, R):
            ll, rr = l + i, min(r + i + 1, N)
            if ll >= N:
                continue
            st.update(ll, rr, v)
    return st.query(N-1, N)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    L = [int()] * (K)  # type: "List[int]"
    R = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    print(solve(N, K, L, R))

class SegmentTreeLazy():
    def __init__(self, arr, ti, ei, func, op, merge):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.func = func
        self.op = op
        self.merge = merge
        self.ti = ti
        self.ei = ei
        self.val = [ti for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.val[self.n + i] = arr[i]
        for i in range(1, self.n)[::-1]:
            self.val[i] = self.func(self.val[2 * i], self.val[2 * i + 1])
        self.laz = [ei for _ in range(2 * self.n)]

    def reflect(self, k):
        if self.laz[k] == self.ei:
            return self.val[k]
        return self.op(self.val[k], self.laz[k])

    def propagate(self, k):
        if self.laz[k] == self.ei: return
        self.laz[2 * k] = self.merge(self.laz[2 * k], self.laz[k])
        self.laz[2 * k + 1] = self.merge(self.laz[2 * k + 1], self.laz[k])
        self.val[k] = self.reflect(k)
        self.laz[k] = self.ei

    def thrust(self, k):
        for i in range(1, self.h + 1)[::-1]:
            self.propagate(k >> i)

    def recalc(self, k):
        while k:
            k >>= 1
            self.val[k] = self.func(self.reflect(2 * k), self.reflect(2 * k + 1))

    def update(self, lt, rt, x):
        lt += self.n
        rt += self.n
        vl = lt
        vr = rt
        self.thrust(lt)
        self.thrust(rt - 1)
        while rt - lt > 0:
            if lt & 1:
                self.laz[lt] = self.merge(self.laz[lt], x)
                lt += 1
            if rt & 1:
                rt -= 1
                self.laz[rt] = self.merge(self.laz[rt], x)
            lt >>= 1
            rt >>= 1
        self.recalc(vl)
        self.recalc(vr - 1)

    def query(self, lt, rt):
        lt += self.n
        rt += self.n
        self.thrust(lt)
        self.thrust(rt - 1)
        vl = vr = self.ti
        while rt - lt > 0:
            if lt & 1:
                vl = self.func(vl, self.reflect(lt))
                lt += 1
            if rt & 1:
                rt -= 1
                vr = self.func(self.reflect(rt), vr)
            lt >>= 1
            rt >>= 1
        return self.func(vl, vr)
    

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
n,k = map(int,raw_input().split())
jis = [map(int, raw_input().split()) for _ in range(k)]
jis.sort()

dp = [0 for _ in xrange(n)]
dp[0] = 1
pre = [0 for _ in xrange(n)]
pre[0] = 1
mod = 998244353
for i in range(1,n):
	flag = True
	for u,v in jis:
		uu,vv = i - v, i - u
		
		if vv >= 0:
			dp[i] += pre[vv] - (pre[uu - 1] if uu - 1 >= 0 else 0)
			dp[i] %= mod
	pre[i] += dp[i] + pre[i-1]
	pre[i] %= mod

print dp[n-1]

Submission status: Accepted

Solution code:
MOD = 998244353
n, k = map(int, input().split())
cumulative_sum = [0 for _ in range(n+1)]
table = [0 for i in range(n)]
pair_list = []
for i in range(k):
    l, r = map(int, input().split())
    pair_list.append((l,r))

table[0] = 1
cumulative_sum[1] = 1
for i in range(1,n):
    root = 0
    for l, r in pair_list:
        l = max(i-l+1, 0)
        r = max(i-r,0)
        root += cumulative_sum[l]- cumulative_sum[r]
        root %= MOD
    table[i]= root % MOD
    cumulative_sum[i+1] = (cumulative_sum[i]+root)%MOD
    #print("step{}\n table:{}\n  cum:{}".format(i,table, cumulative_sum))

print(table[-1])

Submission status: Accepted

Solution code:
import sys

def solve():
      input = sys.stdin.readline
      N, K = map(int, input().split())
      L = [[int(i) for i in input().split()] for _ in range(K)]
      L.sort()
      mod = 998244353
      D = [0] * (N + 1)
      D[0] = 1
      D[1] = -1
      for i in range(N):
            if i > 0:
                  D[i] += D[i-1]
                  D[i] %= mod
            for l, r in L:
                  if i + l <= N:
                        D[i + l] += D[i]
                        D[i + l] %= mod
                  if i + r + 1 <= N:
                        D[i + r + 1] -= D[i]
                        D[i + r + 1] = (mod + D[i + r + 1]) % mod
      print(D[N-1])

      return 0

if __name__ == "__main__":
      solve()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=[0,1]
a=[1]
kl=[]
mod=998244353
for i in range(k):
    kl.append(list(map(int,input().split())))
for i in range(1,n):
    ans=0
    for li,re in kl:
        ans-=l[max(i-re,0)]
        ans+=l[max(i-li+1,0)]
        ans%=mod
    a.append(ans)
    l.append((l[-1]+ans)%mod)

#print(*a)
#print(*l)
print(a[-1])

Submission status: Accepted

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
from fractions import Fraction
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
INF = float("inf")
MOD = 998244353

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

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

for i in range(1,N):
    """
    print(i)
    print(dp)
    print(Sum)
    """
    for j in move:
        l,r = j[0],j[1]
        left = max(0,i-r)
        right = i-l

        if right >= 0:
            #print(i,right+1,left)
            dp[i] += Sum[right+1]-Sum[left]
            dp[i] %= MOD

        Sum[i+1] = Sum[i] + dp[i]
        Sum[i+1] %= MOD
"""
print(dp)
print(Sum)
"""
print(dp[-1])

Submission status: Accepted

Solution code:
MOD = 998244353
N, K = map(int, input().split())
kukan = [list(map(int, input().split())) for _ in range(K)]
step = [0 for _ in range(K)]
ans = [0] * (2 * N)
ans[N] = 1
for i in range(N):
    for k in range(K):
        step[k] += (ans[N + i - kukan[k][0]] - ans[N + i - kukan[k][1] - 1])
    ans[N + i] += sum(step) % MOD
print(ans[-1])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for _ in range(n)]
def LIR(n):
    return [LI() for _ in range(n)]
def SR(n):
    return [S() for _ in range(n)]
def LSR(n):
    return [LS() for _ in range(n)]

sys.setrecursionlimit(1000000)
mod = 998244353

def solve():
    def add(i,x):
        while i < len(dp):
            dp[i] += x
            dp[i] %= mod
            i += i&-i
    def sum(i):
        res = 0
        while i:
            res += dp[i]
            res %= mod
            i -= i&-i
        return res

    n,k = LI()
    p = LIR(k)
    p.sort()
    dp = [0]*(n+2)
    add(1,1)
    add(2,-1)
    for i in range(1,n):
        dpi = sum(i)%mod
        for l,r in p:
            li = i+l
            if li > n:
                break
            ri = min(n,i+r)+1
            add(li,dpi)
            add(ri,-dpi)
    print(sum(n)%mod)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

# ライブラリ参照https://atcoder.jp/contests/practice2/submissions/16580070


class SegmentTree:

    __slots__ = ["func", "e", "original_size", "n", "data"]

    def __init__(self, length_or_list, func=max, e=-10**18):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.original_size = length_or_list
            self.n = 1 << ((length_or_list - 1).bit_length())
            self.data = [self.e] * (self.n*2)
        else:
            self.original_size = len(length_or_list)
            self.n = 1 << ((self.original_size - 1).bit_length())
            self.data = [self.e] * self.n + length_or_list + \
                [self.e] * (self.n - self.original_size)
            for i in range(self.n-1, 0, -1):
                self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def replace(self, index, value):
        index += self.n
        self.data[index] = value
        index //= 2
        while index > 0:
            self.data[index] = self.func(
                self.data[2*index], self.data[2*index+1])
            index //= 2

    def folded(self, l, r):
        left_folded = self.e
        right_folded = self.e
        l += self.n
        r += self.n
        while l < r:
            if l % 2:
                left_folded = self.func(left_folded, self.data[l])
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.func(self.data[r], right_folded)
            l //= 2
            r //= 2
        return self.func(left_folded, right_folded)

    def all_folded(self):
        return self.data[1]

    def __getitem__(self, index):
        return self.data[self.n + index]

    def max_right(self, l, f):
        # assert f(self.e)
        if l >= self.original_size:
            return self.original_size
        l += self.n
        left_folded = self.e
        while True:
            # l //= l & -l
            while l % 2 == 0:
                l //= 2
            if not f(self.func(left_folded, self.data[l])):
                while l < self.n:
                    l *= 2
                    if f(self.func(left_folded, self.data[l])):
                        left_folded = self.func(left_folded, self.data[l])
                        l += 1
                return l - self.n
            left_folded = self.func(left_folded, self.data[l])
            l += 1
            if l == l & -l:
                break
        return self.original_size

    # 未verify
    def min_left(self, r, f):
        # assert f(self.e)
        if r == 0:
            return 0
        r += self.n
        right_folded = self.e
        while True:
            r //= r & -r
            if not f(self.func(self.data[r], right_folded)):
                while r < self.n:
                    r = 2 * r + 1
                    if f(self.func(self.data[r], right_folded)):
                        right_folded = self.func(self.data[r], right_folded)
                        r -= 1
                return r + 1 - self.n
            if r == r & -r:
                break
        return 0


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))
    seg = SegmentTree(n, func=add, e=0)
    seg.replace(0, 1)
    for i in range(1, n):
        wa = 0
        for l, r in lr:
            if i-r >= 0:
                wa+=seg.folded(i-r,i-l+1)
            elif i-l>=0:
                wa+=seg.folded(0,i-l+1)
        wa%=mod
        seg.replace(i,wa)
    print(seg.folded(n-1,n))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def getsum(bit, i):

    s = 0
    i = i + 1

    while i > 0:

        s += bit[i]

        i -= i & (-i)
    return s

def interval_sum(bit, a, b):
    if a == 0:
        return getsum(bit, b)
    else:
        return getsum(bit, b) - getsum(bit, a - 1)

def updatebit(bit , n , i ,v):

    i += 1

    while i <= n:

        bit[i] += v

        i += i & (-i)


def construct(arr, n):

    bit = [0]*(n+1)

    for i in range(n):
        updatebit(bit, n, i, arr[i])

    return bit


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

intervals = []
for _ in range(k):
    a, b = map(int, input().split())
    intervals.append((a, b))
intervals.sort()


data = [0] * n
data[0] = 1
bit = construct(data, n)

mod = 998244353

for i in range(1, n):
    cnt = 0
    for a, b in intervals:
        if i - a < 0:
            break
        cnt += interval_sum(bit, max(i - b, 0), max(i - a, 0))
    cnt %= mod
    updatebit(bit, n, i, cnt)

print(interval_sum(bit, n - 1, n - 1) % mod)

Submission status: Accepted

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

dp = [0]*(n+5)
dp[1] = 1
dp2 = [0]*(n+5)
for i in range(1,n+1):
    dp[i] = (dp[i]+dp2[i]+dp2[i-1])%mod
    dp2[i] = (dp2[i]+dp2[i-1])%mod
    for l,r in K:
        dp2[min(i+l,n+2)] += dp[i]
        dp2[min(i+l,n+2)] %= mod
        dp2[min(i+r+1,n+2)] -= dp[i]
        dp2[min(i+r+1,n+2)] %= mod
print(dp[n]%mod)

Submission status: Accepted

Solution code:
import sys, math, re
from functools import lru_cache
from collections import deque
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

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

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N, K = mi()
    L, R = i2(K)

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

    for i in range(2, N+1):
        dp[i] = dp[i-1]
        for j in range(K):
            if i-L[j] >= 0:
                dp[i] += dp[i-L[j]]
            if i-R[j]-1 >= 0:
                dp[i] -= dp[i-R[j]-1]

        dp[i] %= 998244353

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




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 998244353
EPS = 10**-10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        self.n = n
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            s %= MOD
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            self.tree[i-1] %= MOD
            i += i & -i

    def query(self, l, r):
        """ 区間和の取得 [l, r) """
        return (self.sum(r-1) - self.sum(l-1)) % MOD
    
    def get(self, i):
        """ 一点取得 """
        return self.query(i, i+1)

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

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

dp = BIT(N+1)
dp.add(1, 1)
for i in range(2, N+1):
    for l, r in LR:
        cnt = dp.query(max(i-r, 0), max(i-l+1, 0))
        dp.add(i, cnt)
ans = dp.get(N)
print(ans)