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 .

Solution (Python):
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])

Solution (Python):
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  
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x:  
                    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:  
                    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])

Solution (Python):
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])

Solution (Python):

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

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):

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

Solution (Python):

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

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







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

Solution (Python):
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):
    
    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
        
        dp[i] += (dr-dl)
        dp[i] %= MOD        
    sdp[i] = sdp[i-1] + dp[i]
    sdp[i]%=MOD


print(dp[n])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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)
    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()

Solution (Python):
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)
    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()

Solution (Python):
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])

Solution (Python):
N, K = map(int, input().split())
MOD = 998244353
LR = []
for _ in range(K):
    L, R = map(int, input().split())
    LR.append((L, R))


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(DP[-1])

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



ranges = []
for i in range(k):
    l, r = map(int, input().split())
    
    
    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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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):  
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  
        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):  
        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):  
        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):  
        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)

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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: 
        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)

Solution (Python):
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])

Solution (Python):
import sys



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

Solution (Python):
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])

Solution (Python):
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:
            
            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)

Solution (Python):
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])

Solution (Python):


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

Solution (Python):
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])

Solution (Python):

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

Solution (Python):
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)

Solution (Python):


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



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
        
        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(dp[-1] % mod)

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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()

Solution (Python):
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

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

Solution (Python):
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)

Solution (Python):
from operator import add


class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c % MOD
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1]) % MOD

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l]) % MOD
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r]) % MOD
            r //= 2
        return self.__dot(vl, vr) % MOD
    

MOD = 998244353
N, K = map(int, input().split())
move = [tuple(map(int, input().split())) for _ in range(K)]
move.sort()

st = SegmentTree([0] * N, add, 0)
st.update(0, 1)
for i in range(1, N):
    cnt = 0
    for l, r in move:
        L = max(0, i - r)
        R = i - l
        if R >= 0:
            cnt += st.get(L, R + 1)
    st.update(i, cnt)

print(st.get(N - 1, N))

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

rui = [0] * (n+1)
cur = [0] * n
rui[1] = 1
cur[0] = 1

for i in range(1,n):
    for j in range(k):
        left = max(0,i-hani[j][0]+1)
        right = max(0,i-hani[j][1])
        
        cur[i] = (cur[i] + MOD + rui[left] - rui[right]) % MOD
        
    rui[i+1] = (rui[i] + cur[i]) % MOD
    
print(cur[n-1])

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

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

now = 0

for i in range(1, N):
    for l, r in LR:
        if i - l >= 0:
            now += dp[i - l]
            now %= mod
        if i - r - 1 >= 0:
            now -= dp[i - r - 1]
            now %= mod
        dp[i] = now
    
print(dp[-1])

Solution (Python):


import sys
input=sys.stdin.readline

mod=998244353

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