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

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

dp = [0] * (n+1)
dp[1] = 1
r = [tuple(map(int, input().split())) for _ in range(k)]
s = [0 for _ in range(k)]

for i in range(2, n + 1):
    sums = 0
    for j in range(k):
        s[j] += dp[max(0, i - r[j][0])] - dp[max(0, i - r[j][1] - 1)]
        s[j] %= mod
        sums = (sums + s[j]) % mod
    dp[i] = sums

print(dp[n])

Submission status: Accepted

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

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

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

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

print(dp[n] % mod)

Submission status: Accepted

Solution code:
m = 998244353
def main():
    n,k = map(int,input().split())
    l,r = [],[]
    for _ in range(k):
        l_, r_ = map(int,input().split())
        l.append(l_)
        r.append(r_)

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

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

    print(dp[n]%m)
main()

Submission status: Accepted

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

N,K = map(int,readline().split())
LR = [tuple(map(int,readline().split())) for i in range(K)]
DIV = 998244353
dp = [0] * (N + 1)
dp[1] = 1
sdp = [0] * (N + 1)
sdp[1] = 1

for i in range(2, N + 1):
  for j in range(K):
    l_ind = i - LR[j][1] - 1
    r_ind = i - LR[j][0]
    if r_ind < 0:
      continue
    dp[i] += sdp[r_ind]
    if l_ind >= 0:
      dp[i] -= sdp[l_ind]
    dp[i] %= DIV
  sdp[i] = sdp[i - 1] + dp[i]
  sdp[i] %= DIV
  
print(dp[N])

Submission status: Accepted

Solution code:
class Binary_Indexed_Tree:
    def __init__(self, n):
        """
        :param n: 最大の要素数
        """
        self.n = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1)) - 1
        return s

    def built(self, array):
        """ array を初期値とするBITを構築 """
        for i, a in enumerate(array):
            self.add(i, a)

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j):
        """ 部分区間和 [i, j) """
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """ (a0+a1+...+ai < x となる最大の i, その時の a0+a1+...+ai )
             a0+a1+...+ai <= x としたい場合は equal = True
             二分探索であるため、ai>=0 を満たす必要がある"""
        sum_ = 0
        pos = -1  # 1-indexed の時は pos = 0
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x:  # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        else:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i

        return pos, sum_

    def __getitem__(self, i):
        """ [a0, a1, a2, ...] """
        return self.get(i, i + 1)

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for i in range(self.n):
            yield self.get(i, i + 1)

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))


mod = 998244353
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(k)]
for i in range(k):
    a[i][0] -= 1
b = Binary_Indexed_Tree(n)
dp = [0] * n
dp[0] = 1
b.add(0, 1)
for i in range(1, n):
    for l, r in a:
        dp[i] += b.get(max(0, i - r), max(0, i - l))
    dp[i] %= mod
    b.add(i, dp[i])
print(dp[-1])

Submission status: Accepted

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

rui=[0]*(n+1)
rui[1] = 1
p = 998244353
lr=[]
for i in range(k):
    lr.append(list(map(int, input().split())))

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

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
N,K = map(int,input().split())
MOD = 998244353
dp = [0 for _ in range(N+1)]
dp[1] = 1
R = [tuple(map(int,input().split())) for _ in range(K)]
S = [0 for _ in range(K)]
for i in range(2, N+1):
	s = 0
	for k in range(K):
		S[k] += dp[max(0, i - R[k][0])] - dp[max(0, i - R[k][1] - 1)]
		S[k] %= MOD
		s = (s + S[k]) % MOD
	dp[i] = s
print(dp[N])

Submission status: Accepted

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

dp = [0] * (N + 1)
dpsum = [0] * (N + 1)
"""
dp[i] : iまでの個数
dpsum[i] : iまでのdpの累積和
"""
dp[1] = 1
dpsum[1] = 1
for i in range(2, N + 1):
    for k in range(K):
        r = i - L[k]
        l = i - R[k]
        if r < 0:
            continue
        l = max(1, l)
        dp[i] += (dpsum[r] - dpsum[l - 1]) % mod
    dpsum[i] = (dpsum[i - 1] + dp[i]) % mod

print(dp[N] % mod)

Submission status: Accepted

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

dp = (3*N)*[0]
dp[0] = 1
dp[1] = -1

for n in range(N):
  for L,R in LR:
    dp[L+n]+=dp[n]
    dp[n+R+1]-=dp[n]
  dp[n+1] = (dp[n]+dp[n+1])%998244353

print(dp[N-1])

Submission status: Accepted

Solution code:

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

for i in range(2,N+1):
    for j in range(K):
        Li=i-R[j]
        Ri=i-L[j]

        if Ri<0:
            continue
        else:
            Li=max(Li,1)
            dp[i]=(dp[i]+dpsum[Ri]-dpsum[Li-1])%MOD
    
    dpsum[i]=dpsum[i-1]+dp[i]

print(dp[N])

Submission status: Accepted

Solution code:

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

    v = []
    for _ in range(K):
        L, R = map(int,input().split())
        # for d in range(L, R+1):
        #     moves.append(d)
        v.append((L, R))
    v.sort()

    dp = [0] * N        # マスi-1に到達するまでの操作列の個数
    sdp = [0] * (N + 1) # dp[i]までの累積和 
    dp[0] = 1
    sdp[1] = 1

    for n in range(1, N):
        for p in v:
            left = max(0, n - p[1])
            right = max(0, n - p[0]+1)
            dp[n] += (sdp[right] - sdp[left]) % mod
        sdp[n+1] = (sdp[n] + dp[n]) % mod

    print(dp[-1] % mod)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N, K = MI()
    S = []
    mod = 998244353
    for i in range(K):
        l, r = MI()
        S.append((l, r))
    dp = [0] * (N+1)
    dp[1] = 1
    C = [0] * (N+1)
    C[1] = 1
    for i in range(2, N+1):
        for s in S:
            l = max(1, i - s[1])
            r = i - s[0]
            if r < 1:
                continue
            dp[i] += (C[r] - C[l-1]) % mod
        C[i] += (dp[i] + C[i-1]) % mod
    print(dp[N] % mod)
            
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

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

MOD = 998244353
for i in range(2,n+1):
    # print('------',i)
    for l,r in lrs:
        dr = sdp[i-l] if i-l >= 0 else 0
        dl = sdp[i-r-1] if i-r-1 >= 0 else 0
        # print(dl,dr,'--')
        dp[i] += (dr-dl)
        dp[i] %= MOD        
    sdp[i] = sdp[i-1] + dp[i]
    sdp[i]%=MOD

# print(dp)
print(dp[n])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])

Submission status: Accepted

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

dp = [0] * N
dp[1] = 1
prefix = [1] * N

for i in range(1, N):
    cur = 0
    for L, R in K:
        a = i - R
        b = i - L
        if b < 0:
            continue
        cur += prefix[b] - (prefix[a - 1] if a - 1 >= 0 else 0)
    dp[i] = cur % M
    prefix[i] = prefix[i - 1] + dp[i]
    prefix[i] %= M
print(dp[N - 1])

Submission status: Accepted

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

mod = 998244353

dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)

print(dp[n-1])

Submission status: Accepted

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

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

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if LL <= RR:
            t = sum_list[RR] - sum_list[LL-1]
            dp[i] += t
            dp[i] %= MOD
    sum_list[i] = (sum_list[i-1] + dp[i]) % MOD

print(dp[N])

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n, k = map(int,input().split())
    mod = 998244353
    LR = [tuple(map(int,input().split())) for i in range(k)]
    LR.sort()
    DP = [0] * (n + 1)#i(0-)番目まで行く方法f_iについて、f_i-f_(i-1)
    DP[1] = 1
    DP[2] = -1
    f = 0
    for i in range(1, n + 1):
        f = (f + DP[i])%mod
        for l, r in LR:
            if i + l > n:
                break
            DP[i + l] = (DP[i + l] + f)%mod
            if i + r + 1 > n:
                break
            DP[i + r + 1] = (DP[i + r + 1] - f)%mod
    print(f%mod)

        





if __name__=='__main__':
    main()

Submission status: Accepted

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

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

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if LL <= RR:
            t = sum_list[RR] - sum_list[LL-1]
            dp[i] += t
    sum_list[i] = (sum_list[i-1] + dp[i]) % MOD
    dp[i] %= MOD

print(dp[N])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
MOD = 998244353
LR = []
for _ in range(K):
    L, R = map(int, input().split())
    LR.append((L, R))
# print(f'{LR=}')

DP = [0] * (N + 1)
DP[1] = 1
S = [0] * (N + 1)

for i in range(1, len(DP)):
    for L, R in LR:
        v = S[max(i - L, 0)] - S[max(i - R - 1, 0)]
        DP[i] += v
    DP[i] %= MOD
    S[i] = (S[i - 1] + DP[i]) % MOD

# print(f'{DP=}')
# print(f'{S=}')
print(DP[-1])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
# n, k = (2*10**5, 10)


ranges = []
for i in range(k):
    l, r = map(int, input().split())
    # f = (2 * 10 ** 5) // k
    # l, r = (f * i, f*(i+1))
    ranges.append((l, r))

mod = 998244353
counts = [0]*(n+1)
sum_dp = [0]*(n+2)
counts[0] = 1
sum_dp[1] = 1
for i in range(1, n+1):
    for r in ranges:
        left = max(0, i - r[1])
        right = max(0, i - r[0] + 1)
        counts[i] += (sum_dp[right] - sum_dp[left])
        counts[i] = counts[i] % mod
    sum_dp[i+1] = sum_dp[i] + counts[i]


print(counts[n-1] % mod)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
x=998244353
dp=[0 for i in range(N)]
sdp=[0 for i in range(N)]
L=[]
R=[]
dp[0]=1
sdp[0]=1
for i in range(K):
    l,r=map(int,input().split())
    L.append(l)
    R.append(r) 
for i in range(1,N):
    for j in range(K):
        dp[i]+=(sdp[max(i-L[j],-1)]-sdp[max(i-R[j]-1,-1)])
        dp[i]%=x
    sdp[i]=(sdp[i-1]+dp[i])%x
print(dp[-1]%x)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
ans=[0 for _ in range(n*3)]
ans[1]=1

idou=[]

for _ in range(k):
  a=list(map(int,input().split()))
  idou.append(a)
  
    
mod=998244353

rui=[0 for _ in range(n+1)]
rui[1]=1
  
for i in range(2,n+1):
  for g in idou:
    x,y=g
    left=max(0,i-y-1)
    right=max(0,i-x)
    ans[i]+=(rui[right]-rui[left])%mod

    
  rui[i]+=((rui[i-1]+ans[i]))%mod

    
    

print(ans[n]%mod)

Submission status: Accepted

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

li = [0]*(n+2)
lis = []
lr=[]
lis2 =[0]*(3*n)
lis2[1]=1
lis2[2]=-1

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

for i in range(1,n+1):
    lis2[i]+=lis2[i-1]
    lis2[i]%=998244353

    for j,k in lr:
        lis2[i+j]+=lis2[i]
        lis2[i+k+1]-=lis2[i]

print(lis2[n]%998244353)

Submission status: Accepted

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


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_right(self, p, v):  # apply operator from the right side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_left(self, p, v):  # apply operator from the left side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


st = SegmentTree([0] + [1] + [0] * N, lambda x, y: x + y, 0)
for i in range(2, N + 1):
    v = 0
    for l, r in LR:
        il = max(0, i - r)
        ir = max(0, i - l + 1)
        v += st.query(il, ir)
        v %= mod
    st.update(i, v)
ans = st.query(N, N + 1)
print(ans)

Submission status: Accepted

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

dp = [0 for _ in range(n)]
dpsum = [0 for _ in range(n)]
dp[0] = 1
dpsum[0] = 1
for i in range(1, n):
    for l, r in index_list:
        l_index = max(i - r - 1, -1)
        r_index = i - l
        if r_index >= 0:
            dp[i] += dpsum[r_index]
            if (r_index > l_index) & (l_index >= 0):
                dp[i] -= dpsum[l_index]
    dp[i] = dp[i] % mod
    dpsum[i] = (dp[i] + dpsum[i - 1]) % mod
print(dp[-1])

Submission status: Accepted

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

dp = [1]
acc = [0, 1]

for i in range(1, n):
  new = 0
  for l, r in LR:
    if i < l:
      continue
    r = min(r, i)
    new += acc[i-l+1] - acc[i-r]
    new %= mod
  dp.append(new)
  acc.append((acc[-1]+new) % mod)

print(dp[-1])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
LRs = [list(map(lambda x:int(x), input().split())) for _ in range(K)]

mod = 998244353
#%%
options = []

for LR in LRs:
    for i in range(LR[0], LR[1]+1):
        options.append(i)

options = sorted(options)

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

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

for i in range(2,N+1):
    for LR in LRs: # L <= R
        smaller, bigger = LR[0], LR[1]
        left = max(0, i-bigger-1)
        right = i - smaller
        add =  rui[right] - rui[left]
        dp[i] = (dp[i] + add) %mod
    rui[i] = rui[i-1] + dp[i]
    
print(dp[N]%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n, k = input_int_list()
    sections = []
    MOD = 998244353
    for _ in range(k):
        li, ri = input_int_list()
        sections.append((li, ri))
    dp = [0] * (n + 1)
    dpsum = [0] * (n + 1)
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2, n + 1):
        for li, ri in sections:
            left = i - ri
            right = i - li
            if right < 0:
                continue
            left = max(1, left)
            dp[i] += dpsum[right] - dpsum[left - 1]
            dp[i] %= MOD
        # 累積和の更新を行う
        dpsum[i] = dpsum[i - 1] + dp[i]
        dpsum[i] %= MOD
    print(dp[n])

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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

L = []
for _ in range(K):
    a, b = map(int, input().split())
    b += 1
    L.append([a, b])

ruiwa = [0] * (N + 1)
dp = [0] * (N + 1)
dp[1] = 1
ruiwa[1] = 1
for i in range(2, N + 1):
    for l, r in L:
        l = i - l
        r = i - r
        l, r = r, l
        if r < 0:
            continue
        elif l >= 0:
            # print(ruiwa, r, l)
            dp[i] += (ruiwa[r] - ruiwa[l]) % mod
        else:
            dp[i] += ruiwa[r] % mod
    ruiwa[i] = (ruiwa[i - 1] + dp[i]) % mod

print(dp[-1] % mod)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
L, R = [], []
MOD = 998244353
for _ in range(k):
    t1, t2 = map(int, input().split())
    L.append(t1)
    R.append(t2)

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

for idx1 in range(2, n+1):
    for idx2 in range(k):
        if idx1 - L[idx2] < 0:
            continue
        dp[idx1] += (acc[idx1-L[idx2]] - acc[max(0, idx1-R[idx2]-1)]) % MOD
        dp[idx1] %= MOD
    acc[idx1] = (acc[idx1-1] + dp[idx1]) % MOD

print(dp[-1])

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    mod = 998244353
    N, K = iim()
    it = map(int, sys.stdin.read().split())
    B = list(zip(it, it))

    N1 = N+1 if N&1 else N
    N2 = 1<<(N.bit_length())
    NN2 = N1 + N2
    A = [0] * NN2

    def add(a, i, j, x):
        i += N2; j += N2
        while i < j:
            if i & 1:
                A[i] = (A[i] + x) % mod
                i += 1
            if not j & 1:
                A[j] = (A[j] + x) % mod
                j -= 1
            i >>= 1; j >>= 1
        if i == j:
            A[i] = (A[i] + x) % mod

    def get(a, i):
        i += N2
        ans = 0
        while i > 0:
            ans = (ans + A[i]) % mod
            i >>= 1
        return ans

    A[N2] = 1

    B.sort()
    for i in range(N-1):
        x = get(A, i)
        for a, b in B:
            a += i; b += i
            if a > N-1: continue
            b = min(b, N-1)
            add(A, a, b, x)

    print(get(A, N-1))


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

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

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

for i in range(2, N+1):
    for l, r in kukan:
        li = max(i - l, 0)
        ri = max(i - r - 1, 0)

        dp[i] += sumdp[li] - sumdp[ri]
        dp[i] %= MOD

    sumdp[i] = sumdp[i-1] + dp[i]

print(dp[N])

Submission status: Accepted

Solution code:
#BITを使ってみる
n, k = map(int, input().split())
lr = []
for _ in range(k):
    l, r = map(int, input().split())
    lr.append((l, r))
mod = 998244353
class BinaryIndexedTree():
    def __init__(self, n, mod=None):
        self.n = n
        self.mod = mod
        self.bit = [0]*n
    
    def add(self, i, w):
        x = i+1
        while x<=self.n:
            self.bit[x-1] += w
            if self.mod is not None:
                self.bit[x-1] %= mod
            x += x & -x
    
    def sum(self, l, r):
        return self._sum(r-1) - self._sum(l-1)

    def _sum(self, i):
        ret = 0
        x = i+1
        while x>0:
            ret += self.bit[x-1]
            if self.mod is not None:
                ret %= self.mod
            x -= x & -x
        return ret
bit = BinaryIndexedTree(2*n+1, mod)
bit.add(n+1, 1)
for i in range(n+2, 2*n+1):
    for l, r in lr:
        bit.add(i, bit.sum(i-r, i-l+1))
print(bit.bit[2*n])

Submission status: Accepted

Solution code:
mod=998244353
N,K=map(int, input().split())
A=[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 A:
    S[i+1]+=S[max(0,i-l+1)]-S[max(0,i-r)]
  S[i+1]%=mod
print((S[N]-S[N-1])%mod)

Submission status: Accepted

Solution code:
# 配るDP、もらうDP

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

kukan = []
for _ in range(k):
    # 区間の問題は扱いやすいように[ )　の形に直せるなら直す
    l, r = map(int, input().split())
    l -= 1
    kukan.append([l, r])

dp = [0 for i in range(n)]
dp[0] = 1

# 区間のL, Rは数字が大きいため、その差一つ一つを考えると時間がない！
# それゆえにL, Rの端を考えればいいようにするためにそこまでの累和を考える
ruiseki = [0 for i in range(n + 1)]
ruiseki[1] = 1
for i in range(1, n):
    for l, r in kukan:
        l = i - l
        r = i - r
        l, r = r, l
        # print(l, r)
        if r < 0:
            continue
        elif l >= 0:
            dp[i] += (ruiseki[r] - ruiseki[l]) % mod
        else:
            dp[i] += (ruiseki[r]) % mod
    ruiseki[i + 1] = (ruiseki[i] + dp[i])
    # print(ruiseki, dp)

print(dp[-1] % 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)]
lr.sort()

if lr[0][0] == 1:
    f = [1, 1]
else:
    f = [1, 0]

for i in range(2, n):
    next_f = f[i - 1]
    for l, r in lr:
        if i - l >= 0:
            next_f += f[i - l]
        else:
            break
        if i - r - 1 >= 0:
            next_f -= f[i - r - 1]
        else:
            break
    f.append(next_f % mod)


print(f[n - 1])

Submission status: Accepted

Solution code:
M=998244353
f=lambda:[*map(int,input().split())]
n,k=f()
lr=[f() for _ in range(k)]
dp=[0]*n
dp[0]=1
S=[0]
for i in range(1,n):
  S+=[S[-1]+dp[i-1]]
  for l,r in lr:
    dp[i]+=S[max(i-l+1,0)]-S[max(i-r,0)]
  dp[i]%=M
print(dp[-1])

Submission status: Accepted

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

    for i in range(2,N+1):
        for j in range(K):
            if i - L[j] < 0:
                continue
            dp[i] += (acc[i-L[j]] - acc[max(0,i-R[j]-1)]) % MOD
            dp[i] %= MOD
        
        acc[i] = (acc[i-1] + dp[i]) % MOD
    
    print(dp[-1])
if __name__ == '__main__':
    solve()

Submission status: Accepted

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


def main():
	N,K= i_map()
	m = 998244353
	L = []
	R = []
	for i in range(0,K):
		tmpL,tmpR = i_map()
		L.append(tmpL)
		R.append(tmpR)

	a = []
	a.append(0)
	a.append(-1)
	for i in range(2,3*N):
		a.append(0)

	f = []
	f.append(1)

	for i in range(0,N):
		for j in range(0,K):
			a[i+L[j]] += f[i]
			a[i+R[j]+1] += -f[i]
		f.append((f[i]+a[i+1])%m)

	print(f[N-1]%m)

	return

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
mod=998244353
l=[0]*n
r=[0]*n
for i in range(k):
  l[i],r[i]=map(int,input().split())
dp=[0]*(n+10)
dp[0]=1
sumdp=[0]*(n+10)
sumdp[1]=1
for i in range(1,n):
  for j in range(k):
    li=max(0,i-r[j])
    ri=max(0,i-l[j]+1)
    dp[i]+=sumdp[ri]-sumdp[li]
  sumdp[i+1]=(sumdp[i]+dp[i])%mod
print(dp[n-1]%mod)