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
def input(): return sys.stdin.readline().rstrip()

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

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

L.sort()

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

for i in range(2,N+1):
    count = 0
    for l,r in L:
        if l >= i:
            break
        elif l < i and i - r > 1:
            count += dp[i-l] - dp[i-r-1]
        else:
            count += dp[i-l]
    dp[i] = (dp[i-1] + count) % mod

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

Submission status: Accepted

Solution code:
mod = 998244353
N, K = map(int,input().split())
S = []
for _ in range(K):
    S.append(list(map(int,input().split())))
L = [1]
SUM = [1]
for i in range(1, N):
    tmp = 0
    for j in range(K):
        if i - S[j][0] >= 0:
            tmp += SUM[i - S[j][0]]
        if i - S[j][1] - 1 >= 0:
            tmp -= SUM[i - S[j][1] - 1]
    L.append(tmp % mod)
    SUM.append((L[-1] + SUM[-1]) % mod)

print(L[-1])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
span = []
mod = 998244353
for i in range(k):
    span.append(list(map(int, input().split())))
dp = [0 for i in range(n+1)]
acc = [0 for i in range(n + 1)]
dp[0] = 1
for i in range(n+1):
    acc[i] += acc[i-1]
    acc[i] %= mod
    dp[i] += acc[i]
    for j in range(k):
        l, r = span[j]
        if l + i < n + 1:
            acc[l + i] += dp[i]
        if r + 1 + i < n + 1:
            acc[r+1 + i] -= dp[i]
    dp[i] %= mod
print(dp[-2] % mod)

Submission status: Accepted

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

L=sorted(L)

def add(a,b):
    return a+b

class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    # k: index , x: value
    def update(self, k: int, x):
        k += self.N0 - 1
        ############################
        self.data[k] = x
        ###########################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    # rightは開区間  l<=x<r
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ##########################
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        ##########################
        return res




dp=[0]*N
dp[0]=1
lis=[0]*N
lis[0]=1
seg=SegmentTree(lis, add, 0)
acc=1
#print(L)
for i in range(1,N):
    now=i+1
    temp=0
    for l in L:
        left, right=l
        Left=max(now-right-1,0)
        Right= max(now-left,0)
        temp+=seg.query(Left,Right)
        #print(left, right)
    temp%=p

    dp[i]=temp


    
    if dp[i]!=0:
        seg.update(i,temp)

print(dp[-1])

Submission status: Accepted

Solution code:
#import math
#import itertools
import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
MOD = 998244353
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,k=INTM()
    lrs=[]
    for i in range(k):
        lrs.append(LIST())
    pt=np.array([0]*((2*n)+1))
    rui=np.array([0]*((2*n)+1))
    pt[n-1]=1
    rui[n-1]=1
    for i in range(n):
        nt=n-1+i
        for l,r in lrs:
            pt[nt]=(pt[nt]-rui[nt-r-1]+rui[nt-l])%MOD
        rui[nt]=(rui[nt-1]+pt[nt])%MOD
    print(pt[2*n-2]%MOD)
    #print(pt)
    #print(rui)

    
    #print(pt[n-1]%MOD)


if __name__=='__main__':
    do()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
dp=[0]*(N)
dp[0]=1
mod=998244353
L=list()
for i in range(K):
  a,b=map(int,input().split())
  L.append([a,b])
R=[0,1]
for i in range(1,N):
  for j in range(K):
    a,b=L[j]
    if i>=b:
      dp[i]+=R[i-a+1]-R[i-b]
    elif i>=a:
      dp[i]+=R[i-a+1]
    dp[i]%=mod
  R.append(R[-1]+dp[i])
print(dp[-1])

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
L = 998244353
LR = [0] * K
# 累積和をとっていく。累積和の表を予め作っておき、どんどん足しておく
for i in range(K):
    l,r = map(int,input().split())
    LR[i] = [l,r]

AS = [0] * (N+2)
#for l,r in LR:
#    AS[l] += 1
#    AS[r+1] -= 1

A = [0] * (N+2)
A[1] = 1
A[2] = -1
for i in range(1,N+1):
    AS[i] = (AS[i-1] + A[i])%L
    rest = AS[i]
    for l,r in LR:
        if i+l>N:
            continue
        right = min(N+1,i+r+1)
        A[i+l] += rest
        A[right] += -rest

print(sum(A[1:N+1])%L)

Submission status: Accepted

Solution code:
def d_leaping_tak(MOD=998244353):
    from bisect import bisect_left, bisect_right
    N, K = [int(i) for i in input().split()]
    Ranges = sorted([[int(i) for i in input().split()] for j in range(K)])

    dp = [0] * (N + 1)  # dp[i]: マス i への行き方
    dp[1] = 1
    cumsum_dp = dp[:]
    for i in range(2, N + 1):
        for l, r in Ranges:
            if i - l < 0:
                continue
            if i - r < 0:
                r = i

            dp[i] += cumsum_dp[i - l] - cumsum_dp[i - r - 1]
        dp[i] %= MOD
        cumsum_dp[i] = cumsum_dp[i - 1] + dp[i]
    # print(dp)
    # print(cumsum_dp)
    return dp[N]

print(d_leaping_tak())

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, n, op, e):
        self.n = 1 << (n - 1).bit_length()
        self.op = op
        self.e = e
        self.data = [e] * (2 * self.n)

    def update(self, k, v):
        k += self.n
        self.data[k] = v
        while k > 0:
            k >>= 1
            self.data[k] = self.op(self.data[2 * k], self.data[2 * k + 1])

    def query(self, left, right):
        left += self.n
        right += self.n
        l_res = self.e
        r_res = self.e
        while left < right:
            if left & 1:
                l_res = self.op(l_res, self.data[left])
                left += 1
            left >>= 1
            if right & 1:
                right -= 1
                r_res = self.op(self.data[right], r_res)
            right >>= 1
        return self.op(l_res, r_res)


MOD = 998244353
N, K, *LR = map(int, open(0).read().split())
segments = [(l, r) for l, r in zip(*[iter(LR)] * 2)]
st = SegmentTree(N + 1, lambda x, y: (x + y) % MOD, 0)
st.update(0, 1)
for i in range(1, N + 1):
    for l, r in segments:
        if i - l < 0:
            continue
        L = max(i - r, 0)
        R = i - l
        st.update(i, st.query(i, i + 1) + st.query(L, R + 1))
print(st.query(N - 1, N))

Submission status: Accepted

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

def main():
    n, k = map(int, input().split())
    mod = 998244353

    dp = [0]*(n)

    zone = [tuple(map(int, input().split())) for i in range(k)]
    zone.sort()

    dp[0] = 1
    count = 0
    bit = [0]*k

    for i in range(1, n):
        for j in range(k):
            l, r = zone[j]
            if i-l >= 0:
                bit[j] += dp[i-l]
            if i-r-1 >= 0:
                bit[j] -= dp[i-r-1]
        dp[i] += sum(bit)%mod
        dp[i] %= mod
    ans = dp[n-1]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 998244353
N, K = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(K)]
dp = [0]*(N+1)
dp[1] = 1
dp_rui = [0]*(N+1)
dp_rui[1] = 1
for i in range(2,N+1):
    for l, r in S:
        r2 = i-l
        l2 = i-r
        if l == r:
            if i - l >= 0:
                dp[i] += dp[i-l]
        elif r2 > 0 and l2 >= 0:
            dp[i] += dp_rui[r2]-dp_rui[l2-1]
        elif r2 > 0 and l2 < 0:
            dp[i] += dp_rui[r2]
    dp_rui[i] = dp_rui[i-1]+dp[i] % MOD
    dp[i] %= MOD
print(dp[-1]%MOD)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
LR = [tuple(map(int,input().split())) for _ in range(K)]
d = [0]*N
d[0] = 1
MOD = 998244353
for i in range(N-1):
    x = d[i]
    d[0] = 0
    for k in range(K):
        L, R = LR[k]
        if i+L < len(d):
            d[i+L] += x
            d[i+L] %= MOD
        if i+R+1 < len(d):
            d[i+R+1] -= x
            d[i+R+1] %= MOD
    d[i+1] += d[i]
    d[i+1] %= MOD
print(d[-1] % MOD)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


def segfunc(x, y):
    return x + y


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()

    A = [0] * (N + 1)
    A[1] = 1
    seg = SegTree(A, segfunc=segfunc, ide_ele=0)
    for i in range(2, N + 1):
        for l, r in LR:
            if i - l > 0:
                total = (seg.tree[i + seg.num] + seg.query(max(1, i - r), min(N, i - l + 1)) % M)
                seg.update(i, total)
            else:
                break
    print(seg.tree[seg.num + N] % M)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

dp = [1] + [0] * (N - 1)
imos = [[] for _ in range(N)]
imos[1].append((-1, 0))
for i in range(N - 1):
    for l, r in rngs:
        if i + l < N:
            imos[i + l].append((1, i))
        if i + r + 1 < N:
            imos[i + r + 1].append((-1, i))


for i in range(1, N):
    dp[i] = dp[i - 1]
    for c, j in imos[i]:
        dp[i] += c * dp[j]
        dp[i] %= p

print(dp[N - 1])

Submission status: Accepted

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

def main():
    mod = 998244353
    n, k = map(int, input().split())

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

    # Cumulative Sum
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = -1
    for i in range(n):
        dp[i] += dp[i-1]
        dp[i] %= mod
        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] -= dp[i]
                    dp[i + r] %= mod

    print(dp[n-1])

main()

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=998244353

#+++++

def main():
	# = int(input())
	n, k = tin()
	#s = input()
	al = []
	for _ in range(k):
		l,r = tin()
		al.append([l,r])
	
	dd = [0]*(n)
	dd[0] = 1
	
	ruiseki=[0]*(n)
	ruiseki[0]=1
	ruiseki[1]=-1
	rui=0
	for pos, num in enumerate(ruiseki):
		rui += ruiseki[pos]
		rui %= mod
		dd[pos]=rui
		for l,r in al:
			if pos + l < n:
				ruiseki[pos+l] += rui
			if pos + r + 1 < n:
				ruiseki[pos + r + 1] -= rui
		#pa(dd)
		#pa(ruiseki)
		
	return rui%mod
		
		
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

mod = 998244353
N, K = map(int, input().split())
L, R = zip(*[list(map(int, input().split())) for _ in range(K)])
dp = [0] * (N + 1)
dp[1] = 1
dp[2] = -1
x = 0
for i in range(1, N):
    x = (x + dp[i]) % mod
    for j in range(K):
        if i + L[j] > N:
            continue
        dp[i + L[j]] = (dp[i + L[j]] + x) % mod
        if i + R[j] + 1 <= N:
            dp[i + R[j] + 1] = (dp[i + R[j] + 1] - x) % mod
x = (x + dp[N]) % mod
print(x)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 998244353


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, SS):
    count = [0] * (N + 10)
    count[0] = 1
    accum = [0] * (N + 10)
    accum[0] = 1

    for pos in range(1, N):
        ret = 0
        for left, right in SS:
            # for i in range(left, right + 1):
            #     j = pos - i
            #     if j < 0:
            #         continue
            #     ret += count[j]
            #     ret %= MOD
            start = max(-1, pos - right - 1)
            end = max(-1, pos - left)
            # debug("end, start", end, start)
            ret += (accum[end] - accum[start])
            ret %= MOD
        # debug("pos, ret", pos, ret)
        count[pos] = ret
        accum[pos] = accum[pos - 1] + ret

    # ret = f(N - 1)
    ret = count[N - 1]
    return ret % MOD


def main():
    # parse input
    N, K = map(int, input().split())
    SS = []
    for i in range(K):
        SS.append(tuple(map(int, input().split())))
    print(solve(N, K, SS))


# tests
T1 = """
5 2
1 1
3 4
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
4
"""

T2 = """
5 2
3 3
5 5
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
0
"""

T3 = """
5 1
1 2
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
5
"""

T4 = """
60 3
5 8
1 3
10 15
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
221823067
"""

T5 = """
10 1
1 2
"""
TEST_T5 = """
>>> as_input(T5)
>>> main()
55
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    MOD = 998244353

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

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

    acc = [0] * (n + 1)
    acc[1] = 1
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        t = 0
        for l, r in blocks:
            if i - l >= 0:
                t += acc[i - l]
            if i - r - 1 >= 0:
                t -= acc[i - r - 1]
            t %= MOD
        dp[i] = t
        acc[i] = (acc[i - 1] + t) % MOD

    print(dp[-1] % MOD)


if __name__ == '__main__':
    main()

# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Accepted

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

for i in range(1,n):
  s = 0
  for (x,y) in st:
    if i > y:
      s = (s + total[i-x] - total[i-y-1]) % 998244353
    elif i >= x:
      s = (s + total[i-x]) % 998244353
  total.append((s+total[-1]) % 998244353)   
  
print((total[-1]-total[-2]) % 998244353)

Submission status: Accepted

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

dp = [0] * (n + 1)

dp[0] = 0; dp[1] = 1

for i in range(2, n+1):
    dp[i] = dp[i-1]
    for x, y in a:
        l = i - y; r = i - x
        l = max(l, 0); r = min(r, i-1)
        dp[i] = (dp[i] + (dp[r] - (dp[l - 1] if l > 0 else 0))) % MOD

print((dp[-1] - dp[-2] + MOD) % MOD)

Submission status: Accepted

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

m =  998244353

# print(S)

dp = [0] * N
dp[0] = 1
sum_of_region = [0] * K
for i in range(1, N):
    for j in range(K):
        if i - S[j][0] >= 0:
            sum_of_region[j] += dp[i - S[j][0]]
        if i - S[j][1] - 1 >= 0:
            sum_of_region[j] -= dp[i - S[j][1] - 1]
        dp[i] += sum_of_region[j] % m
        dp[i] %= m
    # print(i, dp, sum_of_region)

ans = dp[N - 1]
print(ans)

Submission status: Accepted

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

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

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


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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(k)]
imos = [0] * (2 * n + 1)
imos[0] = 1
imos[1] = -1
ans = [1]
  # print(imos)
for i in range(n):
    for x,y in lis:
        imos[i+x] += ans[-1]
        imos[i+y+1] -= ans[-1]
    ans.append((ans[-1]+imos[i+1])%998244353)
  #print(imos)
print(ans[-2])

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.readline
M = 998244353
def solve():
  N, K = map(int, input().split())
  LR = []
  for _ in range(K):
    l, r = map(int, input().split())
    LR.append((l, r))
  Ss = [0] * K
  steps = [0] * (N+1)
  steps[1] = 1
  for n in range(2, N+1):
    for k in range(K):
      l, r = LR[k]
      # +n-l, -n-r-1
      # print(n-l, n-r)
      if n-l >= 0:
        Ss[k] += steps[n-l]
      if n-r-1 >= 0:
        Ss[k] -= steps[n-r-1]
      Ss[k] %= M
    steps[n] = sum(Ss) % M
    #print(n, steps, Ss)
  print(steps[-1])
      
solve()

Submission status: Accepted

Solution code:
"Binary Indexed Tree"
"""
- iが与えられたときa1~aiまでの和を計算する O(log n)
- iとxが与えられたときai += x とする O(log n)
"""
# BIT: Binary Indexed Tree (1-indexed), 0-indexだと困るので。
# A1~Aiまでの和 O(logN)


def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)  # 次に求める区間のindexは今見ているindexから今見ている区間の長さ(これはidx&(-idx)で求めることができる)を引くことでindexを求めることができる
    return res_sum


# Ai += x  O(logN)
def BIT_updata(idx, x):
    while idx <= N:
        BIT[idx] += x
        idx += (idx&(-idx))  # 次に更新すべき区間のindexは今見ているindexに今見ている区間の長さを足すことでindexを求めることができる
    return


# n = 8
# BIT = [0]*(n+1)  # 最初に0で初期化する
# a = [1, 2, 3, 4, 5, 6, 7, 8]
# for i, e in enumerate(a):
#     BIT_updata(i+1, e)
#
#
# # A0~A2の和: 6
# print(BIT_query(3))  # ここのアクセスは1-indexで考えている
# # A3~A6の和: 18
# print(BIT_query(6)-BIT_query(2))  # ここのアクセスは1-indexで考えている
# print(BIT)

# BIT_queryで10~15マス前の和を現在のところに加える
N, K = map(int, input().split())
move = []
for _ in range(K):
    l, r = map(int, input().split())
    move.append([l, r])
MOD = 998244353
BIT = [0]*(N+1)  # スタート地点1~ゴール地点NまでのN個 (1-indexed)
BIT_updata(1, 1)
for i in range(2, N+1):
    for l, r in move:
        # lマス前からrマス前までの区間和を現在のマスに加える
        BIT_updata(i, (BIT_query(i-l)-BIT_query(i-r-1))%MOD)
ans = BIT_query(N) - BIT_query(N-1)
print(ans%MOD)
# BIT_query(N-10) - BIT_query(N-15)を現在のところにタス
# いや，微妙に違う?

Submission status: Accepted

Solution code:
p=998244353

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

LR=[]
for i in range(k):
    Li,Ri=map(int,input().split())
    LR.append([Li,Ri])

U=[0,1]

cnt=[1]
for i in range(1,n):#i:=position
    cnti=0
    for Li,Ri in LR:
        scopeL=i-Ri
        scopeR=i-Li
        if scopeR>=0:
            cnti+=U[scopeR+1]-U[max(0,scopeL)]#sum[max(0,scopeL),scopeR+1]
    cnt.append(cnti%p)
    U.append((U[i]+cnti)%p)

print(cnt[n-1])

Submission status: Accepted

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

dp = [0]*(N+1)
tmp = 1
for i in range(1, N+1):
    tmp += dp[i]
    for s in S:
        l, r = s
        if i+l <= N:
            dp[i+l] += tmp
            dp[i+l] %= P
        if i+r+1 <= N:
            dp[i+r+1] -= tmp
            dp[i+r+1] %= P
print(dp[N])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
MOD = 998244353
ans = [0, 1, -1] + [0]*(N-2)
L, R = [], []
for _ in range(K):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r+1)

temp = 0
for i in range(1, N):
    temp = (temp + (ans[i] % MOD)) % MOD
    for l in L:
        if i + l <= N:
            ans[i+l] = (ans[i+l] + temp) % MOD
    for r in R:
        if i + r <= N:
            ans[i + r] = (ans[i+r] - temp) % MOD
print((temp + ans[N]) % MOD)

Submission status: Accepted

Solution code:

N,K = map(int,input().split())
dp = [0 for _ in range(3*N)]
dp[0] = 1
S_left = []
S_right = []
for i in range(K):
    l,r = map(int,input().split())
    S_left.append(l)
    S_right.append(r)
plus = 0
for j in range(N):
    plus += dp[j]
    for k in range(K):
        dp[S_left[k]+j]+= plus
        dp[S_left[k]+j]%=998244353
        dp[S_right[k]+j+1]-= plus
        dp[S_right[k]+j+1]%=998244353
dp_cum = [1]
print(dp[N-1]%998244353)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# Binary Indexed Tree for Range Add Query
# 1-indexed
#    初期値は a_1 = a_2 = ... = a_n = 0
#    ・add(l,r,x): [l,r) に x を加算する
#    ・sum(i): a_1 + a_2 + ... + a_i を計算する

class BinaryIndexedTree:
    # 初期化処理
    def __init__(self, size):
        self.size = size
        self.dat = [0]*(size+1)
        self.depth = size.bit_length()

    def init(self, a):
        for i, x in enumerate(a):
            self.add(i, x)

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.dat[i] += x
            i += i & -i # 更新すべき位置

    def sum(self, r):
        r += 1
        ret = 0
        while r>0:
            ret += self.dat[r]
            r -= r & -r # 加算すべき位置
        return ret

# sum(i) >= vとなる最小のindex
    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.dat[k] < x:
                sum_ += self.dat[k]
                pos += 1 << i
        return pos  #0-indexed

#### for debug
    def get_original_sequence(self):
        ret = self.get_aggrigate_sequence()
        for i in range(self.size-1, 0, -1):
            ret[i] -= ret[i-1]
        return ret

    def get_aggrigate_sequence(self):
        return [bit.sum(i) for i in range(self.size)]

    def __str__(self):
        seq = self.get_original_sequence()
        ret = 'original :' + ' '.join(map(str, seq))
        ret += '\n'
        seq = self.get_aggrigate_sequence()
        ret += 'aggrigate:' + ' '.join(map(str, seq))
        return ret

class BitRAQ:
    def __init__(self, size):
        self.size = size
        self.bit0 = BinaryIndexedTree(size)
        self.bit1 = BinaryIndexedTree(size)

    def init(self, a):
        self.bit0.init(a)

    def add(self, l, r, x):
        self.bit0.add(l, -x * (l - 1))
        self.bit0.add(r, x * (r - 1))
        self.bit1.add(l, x)
        self.bit1.add(r, -x)

    def sum(self, r):
        return self.bit0.sum(r) + self.bit1.sum(r) * r
##################################
mod = 998244353
n, k = map(int, input().split())
lr = [list(map(int,input().split())) for _ in range(k)]
bit = BitRAQ(2*10**5+100)
bit.bit0.add(1,1)
for i in range(1,n):
    cnt = bit.sum(i) - bit.sum(i-1)
    cnt %= mod
    for l, r in lr:
        bit.add(i+l, i+r+1, cnt)
ret = bit.sum(n) - bit.sum(n-1)
ret %= mod
print(ret)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 998244353

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

total = 0
for i in range(n):
    total += dp[i]
    total %= MOD
    for p, d in delta:
        if i + p >= n:
            continue
        dp[i + p] += total * d
        dp[i + p] %= MOD
print(total % MOD)

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):
    for l, r in lr:
        dp[i+l] += now
        dp[i+r+1] -= now
    now += dp[i+1]
    now %= mod
ans = 0
for i in range(n):
    ans += dp[i]
    ans %= mod
print(ans)

Submission status: Accepted

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

class FenwickTree:
    def __init__(self, size):
        self.bit = [0] * (size + 1)
        self.size = size

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.bit[i]
            s %= mod
            i -= i & -i
        return s

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

mod = 998244353
N, K = map(int, input().split())
L, R = zip(*[list(map(int, input().split())) for _ in range(K)])
dp = FenwickTree(N + 1)
dp.add(1, 1)
dp.add(2, -1)
for i in range(1, N):
    x = dp.sum(i)
    for j in range(K):
        dp.add(i + L[j], x)
        if i + R[j] + 1 <= N:
            dp.add(i + R[j] + 1, -x)
print(dp.sum(N))

Submission status: Accepted

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

mod = 998244353

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

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

for i in range(n):
    p = i + 1
    temp = 0
    for j in range(k):
        s, t = move[j]
        r = max(0, p - s)
        l = max(0, p - t - 1)
        temp += ruiseki[r] - ruiseki[l]
    dp[p] += temp % mod
    ruiseki[p] = ruiseki[p - 1] + dp[p]

print(dp[n])

Submission status: Accepted

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

nums = []

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


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

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

print(dp[-1] % MOD)
# print(dp)
# print(cumsum)

Submission status: Accepted

Solution code:
import math
import collections
import bisect
from collections import deque
from copy import copy, deepcopy
import time

import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
from numba import jit

mod = 998244353


def main():
    N,K = map(int,input().split())
    R = []
    L = []
    ans = [0 for i in range(N+1)]
    cumsum = [0 for i in range(N+1)]
    ans[1]=1
    ans[2]=-1
    cumsum[1]=1
    for i in range(K):
        r,l = map(int,input().split())
        R.append(r)
        L.append(l)
    for i in range(1,N+1):
        #print(i)
        #print("ans",ans)
        #print("cumsum",cumsum)
        for j in range(K):
            if i+R[j]<=N:
                ans[i+R[j]]+=cumsum[i]
                ans[i+R[j]]%=mod
            if i+L[j]+1<=N:
                ans[i+L[j]+1]-=cumsum[i]
                ans[i+L[j]+1]%=mod
        if i<N:
            cumsum[i+1]=cumsum[i]+ans[i+1]
            cumsum[i+1]%=mod
        
    print(cumsum[N]%mod)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 998244353
N, K = map(int, input().split())
kukan = [None] * K
sums = [0] * (N+2)
path = [0] * (N+1)

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


path[1] = 1
sums[0] = 0
sums[1] = 1
for i in range(2, N+1):
  total = 0
  for j in range(K):
    l, r = kukan[j]
    if l >= i:
      continue
    if r >= i:
      r = i-1
    total = (total + sums[i - l] - sums[i - r - 1] + MOD) % MOD
  path[i] = total
  sums[i] = (sums[i-1] + total) % MOD

print(path[N])