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: Time Limit Exceeded

Solution code:
# BinaryIndexedTree
# O(logN)で累積和取得と値の更新
# add(i,x)...i番目にxを加算
# sum(i,j)...[i,j)の累積和を取得
# sum_sub(i)...[0:i]の累積和を取得
class BinaryIndexedTree:
  def __init__(self, n):
    self.bit = [0] * n

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

  def sum_sub(self, i):
    a = 0
    i += 1
    while i:
      a += self.bit[i-1]
      i -= i & -i
    return a

  def sum(self, i, j):
    a = 0
    if j != 0:
      a += self.sum_sub(j-1)
    if i != 0:
      a -= self.sum_sub(i-1)
    return a
mod=998244353
n,k=map(int,input().split())
lr=[]
for i in range(k):
  l,r=map(int,input().split())
  lr.append((l,r))
bit=BinaryIndexedTree(2*n+7)
bit.add(0,1)
bit.add(1,-1)
for i in range(n-1):
  x=bit.sum_sub(i)%mod
  for l,r in lr:
    bit.add(i+l,x)
    bit.add(i+r+1,-x)
print(bit.sum_sub(n-1)%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

n, k = map(int,input().split())
d = set()
for i in range(k):
    l, r = map(int,input().split())
    for j in range(l, r+1):
        d.add(j)
        
dp = [0]*(n+1)
dp[1] = 1
for i in range(1, n+1):
    for j in d:
        if i+j > n:
            continue
        dp[i+j] += dp[i]
        dp[i+j] %= MOD
print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k= list(map(int, input().strip().split()))
l=[0]*n
r=[0]*n
mod=998244353
for i in range(k):
    l[i],r[i] = list(map(int, input().strip().split()))

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): # 各kにおいてli~riまでの移動量が＋となる場合の和を計算する
        li = i - r[j] # 遷移元のindexの左端を求める
        ri = i - l[j] # 遷移元のindexの右端を求める
        if ri < 0: # riがﾏｲﾅｽの場合はそもそも以降を考えない
            continue
        li = max(li,1) # li がﾏｲﾅｽの場合があるので、そのときのindexはｽﾀｰﾄの"1"と考える
        dp[i] += dpsum[ri] - dpsum[li-1] # li~riの和を足す
    dpsum[i] = (dpsum[i-1]+dp[i])%mod
    
print(dp[n]%mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,K = map(int,input().split())
LR = [tuple(map(int,input().split())) for i in range(K)]
MOD = 998244353

dp = [1]
cumdp = [0,1]
for i in range(1,N):
    tmp = 0
    for l,r in LR:
        if i-l+1 <= 0: continue
        tmp += cumdp[i-l+1] - cumdp[max(0,i-r)]
    tmp %= MOD
    dp.append(tmp)
    cumdp.append((cumdp[-1] + tmp) % MOD)
print(dp[-1])

Submission status: Accepted

Solution code:
inf=998244353


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

SS.sort()

table = [0 for k in range(N)] 
diff = [0 for k in range(N-1)]

table[0]=1
diff[0]=-1

for i in range(N-1):
    if table[i]!=0:
        for s in SS:
            lef=s[0]
            rig=s[1]
            if i+lef-1<N-1:
                diff[i+lef-1]+=table[i]
            if i+rig<N-1:
                diff[i+rig]-=table[i]
    table[i+1]=table[i]+diff[i]
    table[i+1]%=inf

print(table[N-1])

Submission status: Accepted

Solution code:

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

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

for i in range(1, N):
    for l, r in X:
        dp[i] += sdp[max(0, i - l + 1)] - sdp[max(0, i - r)]
        dp[i] %= MOD
    sdp[i + 1] = sdp[i] + dp[i]
    sdp[i + 1] %= MOD

print(dp[-1])

Submission status: Accepted

Solution code:
MOD = 998244353
N, K = map(int, input().split()) #Nはマス目の数、Kは区間の数(Kは10以下)
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:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 998244353
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    LR = [LI() for _ in range(K)]

    dp = [0] * (N + 1)
    dp[0] = 1
    a = [0] * (N + 1)
    a[0] = 1
    a[1] = -1
    for i in range(N):
        for l, r in LR:
            left = min(i + l, N)
            right = min(i + r + 1, N)
            a[left] += dp[i]
            a[right] -= dp[i]
        dp[i+1] += dp[i] + a[i+1]
        dp[i+1] %= MOD
        # print(a)
        # print(dp)

    print(dp[-2])

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
mod = 998244353
dp = [0]*(n+10)
dpsum = [0]*(n+10)
dp[1] = dpsum[1] = 1
L = [0]*k
R = [0]*k
for i in range(k):
    l,r = map(int,input().split())
    L[i],R[i] = l,r
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]
        dp[i] %= mod
    dpsum[i] = dpsum[i-1]+dp[i]
    dpsum[i] %= mod
print(dp[n])

Submission status: Accepted

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

mod=998244353

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

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

print(dp[n-1])

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
MOD = 998244353
t = []
for _ in range(K):
    l, r = map(int, input().split())
    t.append((l, r))
dp = [0]*(N+1)
dp[1] = 1
dps = [0]*(N+1)
dps[1] = 1
for i in range(2, N+1):
    for j in range(K):
        li = i-t[j][0]
        ri = i-t[j][1]
        if li < 0:
            continue
        ri = max(ri, 1)
        dp[i] += dps[li]-dps[ri-1]
        dp[i] %= MOD
    dps[i] = dps[i-1]+dp[i]
    dps[i] %= MOD
print(dp[N])

Submission status: Accepted

Solution code:
N, K = (int(i) for i in input().split())
l, r = [0]*K, [0]*K
for k in range(K):
    l[k], r[k] = (int(x) for x in input().split())

# dp : マスiまで移動する方法のパターン数
# TLE
'''
import numpy as np
dp = [0]*N
dp[0] = 1
for i in range(N):
    for k in range(K):
        for j in range(l[k], r[k]+1):
            if (i+j < N):
                dp[i+j] = dp[i+j] + dp[i]
            if j == r[k]:
                print(i, (l[k], r[k]), dp, np.diff(dp))
print(dp[-1]%998244353)
'''

# dp : マスiまで移動する方法のパターン数
# dps : dp[i] と dp[i+1] の 差
dp = [0]*N
dps = [0]*(N-1)
dp[0] = 1
dps[0] = -1
for i in range(N-1):
    for k in range(K):
        if i + l[k] - 1 < (N - 1):
            dps[i + l[k] - 1] += dp[i]
        if i + r[k] < (N - 1):
            dps[i + r[k]    ] -= dp[i]
        #print(i, (l[k], r[k]), dp, dps)
    dp[i+1] = (dps[i] + dp[i])%998244353
print(dp[-1]%998244353)

Submission status: Accepted

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

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

dp[1] = 1
dp_rui[1] = 1

for i in range(2,n+1):
    for j in range(k):
        lft = i - lr[j][1]
        rht = i - lr[j][0]
        #print(i,lft,rht)
        if rht <= 0:
            continue
        lft = max(1,lft)
        dp[i] += dp_rui[rht] - dp_rui[lft-1]
        #print(dp_rui[rht],dp_rui[lft-1])
        dp[i] %= mod
        #print(dp)
        #print(dp_rui)
    dp_rui[i] = dp_rui[i-1] + dp[i]
    dp_rui[i] %= mod

print(dp[n]%mod)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
Range = [None] * K

for i in range(K):
    Range[i] = list(map(int, input().split()))

sweep = {1: 1}
M = 998244353

value = 0
for cell in range(1, N+1):
    value += sweep.get(cell, 0)
    value = (value + M) % M
    for r in range(K):
        sweep[cell + Range[r][0]] = (sweep.get(cell + Range[r][0], 0) + value + M) % M
        sweep[cell + Range[r][1] + 1] = (sweep.get(cell + Range[r][1] + 1, 0) - value + M) % M

print(sweep.get(N, 0))

Submission status: Accepted

Solution code:
# coding:UTF-8
import sys
from math import factorial

MOD = 998244353
INF = 10000000000

def main():
    n, k = list(map(int, input().split()))  # スペース区切り連続数字
    lrList = [list(map(int, input().split())) for _ in range(k)]  # スペース区切り連続数字(行列)

    s = []
    for l, r in lrList:
        for i in range(l, r+1):
            s.append(i)
    s.sort()

    sum = [0] * (n + 1)
    Interm = [0] * (2 * n + 1)
    sum[1] = 1
    for i in range(1, n):
        for j in range(k):
            l, r = lrList[j][0], lrList[j][1]
            Interm[i+l] += sum[i]
            Interm[i+r+1] -= sum[i]
        sum[i+1] = (sum[i] + Interm[i+1]) % MOD

    # result = Interm[n]
    result = (sum[n] - sum[n-1]) % MOD
    # ------ 出力 ------#
    print("{}".format(result))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys
readline = sys.stdin.readline

MOD = 998244353
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%MOD
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % MOD
    return frac, fraci
frac, fraci = frac(1341398)
pr = 3
LS = 20
class NTT:
    def __init__(self):
        self.N0 = 1<<LS
        omega = pow(pr, (MOD-1)//self.N0, MOD)
        omegainv = pow(omega, MOD-2, MOD)
        self.w = [0]*(self.N0//2)
        self.winv = [0]*(self.N0//2)
        self.w[0] = 1
        self.winv[0] = 1
        for i in range(1, self.N0//2):
            self.w[i] = (self.w[i-1]*omega)%MOD
            self.winv[i] = (self.winv[i-1]*omegainv)%MOD
        used = set()
        for i in range(self.N0//2):
            if i in used:
                continue
            j = 0
            for k in range(LS-1):
                j |= (i>>k&1) << (LS-2-k)
            used.add(j)
            self.w[i], self.w[j] = self.w[j], self.w[i]
            self.winv[i], self.winv[j] = self.winv[j], self.winv[i]
        
    def _fft(self, A):
        M = len(A)
        bn = 1
        hbs = M>>1
        while hbs:
            for j in range(hbs):
                A[j], A[j+hbs] = A[j] + A[j+hbs], A[j] - A[j+hbs]
                if A[j] > MOD:
                    A[j] -= MOD
                if A[j+hbs] < 0:
                    A[j+hbs] += MOD
            for bi in range(1, bn):
                wi = self.w[bi]
                for j in range(bi*hbs*2, bi*hbs*2+hbs):
                    A[j], A[j+hbs] = (A[j] + wi*A[j+hbs])%MOD, (A[j] - wi*A[j+hbs])%MOD
            bn <<= 1
            hbs >>= 1

    def _ifft(self, A):
        M = len(A)
        bn = M>>1
        hbs = 1
        while bn:
            for j in range(hbs):
                A[j], A[j+hbs] = A[j] + A[j+hbs], A[j] - A[j+hbs]
                if A[j] > MOD:
                    A[j] -= MOD
                if A[j+hbs] < 0:
                    A[j+hbs] += MOD
            for bi in range(1, bn):
                winvi = self.winv[bi]
                for j in range(bi*hbs*2, bi*hbs*2+hbs):
                    A[j], A[j+hbs] = (A[j] + A[j+hbs])%MOD, winvi*(A[j] - A[j+hbs])%MOD
            bn >>= 1
            hbs <<= 1
    
    def convolve(self, A, B):
        LA = len(A)
        LB = len(B)
        LC = LA+LB-1
        M = 1<<(LC-1).bit_length()
        A += [0]*(M-LA)
        B += [0]*(M-LB)
        self._fft(A)
        self._fft(B)
        C = [0]*M
        for i in range(M):
            C[i] = A[i]*B[i]%MOD
        self._ifft(C)
        minv = pow(M, MOD-2, MOD)
        for i in range(LC):
            C[i] = C[i]*minv%MOD
        return C[:LC]
        
        return C
    
    def inverse(self, A):
        LA = len(A)
        dep = (LA-1).bit_length()
        M = 1<<dep
        A += [0]*(M-LA)
        
        g = [pow(A[0], MOD-2, MOD)]
        for n in range(dep):
            dl = 1<<(n+1)
            f = A[:dl]
            fg = self.convolve(f, g[:])[:dl]
            fgg = self.convolve(fg, g[:])[:dl]
            ng = [None]*dl
            for i in range(dl//2):
                ng[i] = (2*g[i]-fgg[i])%MOD
            for i in range(dl//2, dl):
                ng[i] = MOD-fgg[i]
            g = ng[:]
        return g[:LA]
    
    def integral(self, A):
        A = [1] + [A[i]*fraci[i+2]%MOD for i in range(len(A))]

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

A = [0]*(N+2)
for _ in range(K):
    l, r = map(int, readline().split())
    A[l] += 1
    A[r+1] -= 1

for i in range(1, N+1):
    A[i] += A[i-1]
A = A[:-1]
A[0] -= 1
A = [-a%MOD for a in A]

NN = NTT()
print(NN.inverse(A[:])[N-1]%MOD)

Submission status: Accepted

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n+1)

    def sum(self, i):  # sum in [0, i]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):  # i > 0
        assert i > 0
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


class BitImos:
    """
    ・範囲すべての要素に加算
    ・ひとつの値を取得
    の2種類のクエリをO(logn)で処理
    """
    def __init__(self, n):
        self.bit = Bit(n+1)

    def add(self, s, t, x):
        # [s, t)にxを加算
        self.bit.add(s, x)
        self.bit.add(t, -x)

    def get(self, i):
        return self[i]

    def __getitem__(self, key):
        # 位置iの値を取得
        return self.bit.sum(key)


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

bit = BitImos(N+2)
bit.add(1, 2, 1)

mod = 998244353

for i in range(1, N+1):
    cur = bit.get(i) % mod
    for l, r in LR:
        if i + l > N:
            continue
        bit.add(i+l, min(i + r + 1, N + 2), cur)

print(bit.get(N) % mod)

Submission status: Accepted

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

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

Submission status: Accepted

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

    mod = 998244353

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

    S.sort()
    #print(S)

    ans = [0]*N
    acc = [0]*N
    ans[0] = 1
    acc[0] = 1

    for i in range (1,N):
        for l,r in S:

            if i-l < 0:
                break
            else:
                ans[i] += acc[i-l]
            if i-r -1 < 0:
                break
            else:
                ans[i] -= acc[i-r-1]

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


    print(ans[N-1])


main()

Submission status: Accepted

Solution code:
def resolve():
    n, k = map(int, input().split())
    S = []
    L, R = [], []
    for _ in range(k):
        l1, r1 = map(int, input().split())
        L.append(l1)
        R.append(r1)

    dp = [0 for i in range(n + 1)]
    dpsum = [0 for i in range(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
            Li = max(1, Li)
            dp[i] += dpsum[Ri] - dpsum[Li - 1]  # dp[Li] ~ dp[Ri]
            dp[i] %=  998244353

        dpsum[i] = (dpsum[i - 1] + dp[i]) % 998244353

    print(dp[n])

resolve()

Submission status: Accepted

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

l = [0] * K
r = [0] * K

for i in range(K):
	l[i], r[i] = map(int, input().split())
	
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 li <= 0:
			dp[i] = dp[i] + dpsum[ri]
			dp[i] %= MOD
		else:
			dp[i] = dpsum[ri] - dpsum[li-1] + dp[i]
			dp[i] %= MOD
			
			
	dpsum[i] = dp[i] + dpsum[i-1]
	dpsum[i] %= MOD
	
print(dp[N] % MOD)

Submission status: Accepted

Solution code:
#もらうDPで考える
N, K = map(int, input().split())

l = []
r = []

MOD = 998244353

for i in range(K):
    a,b = map(int, input().split())
    l.append(a)
    r.append(b)

dp = [0] * (N+1)
#スタート地点が1なので、dp[1]を1とする
dp[1] = 1

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

for i in range(2, N+1):
    for j in range(K):
        #[l[i], r[i]]
        li = i - r[j]
        ri = i - l[j]
        if ri < 0: continue
        # l1が負になるケースをハンドリング
        li = max(1, li)
        dp[i] += (dpsum[ri] - dpsum[li-1])%MOD #dp[li] ~ dp[ri]の和を足す
    dpsum[i] = (dpsum[i-1] + dp[i])%MOD

print(dp[N]%MOD)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
sys.setrecursionlimit(10**7)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, K = list(map(int, _in[0].split(' ')))  # type:list(int)
    L_R_arr = []
    for i in range(K):
        _ = list(map(int, _in[i+1].split(' ')))  # type:list(int)
        L_R_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    dp = [0] * N
    sdp = [0] * (N+1)
    dp[0] = 1
    for i in range(N):
        for L, R in L_R_arr:
            right = max(0, i-L+1)
            left  = max(0, i-R)
            dp[i] += sdp[right] - sdp[left]
        else:
            sdp[i+1] = (sdp[i] + dp[i]) % 998244353
    ans = dp[-1] % 998244353
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - Leaping Tak
n,k = map(int,input().split())
lr = [tuple(map(int,input().split())) for _ in range(k)]
MOD = 998244353

# 累積和を使ってもらうdpを効率よく実現する。

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

Submission status: Accepted

Solution code:
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineering College

'''
from os import path
import sys
from heapq import heappush,heappop
from functools import cmp_to_key as ctk
from collections import deque,defaultdict as dd 
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input().rstrip()
def mi():return map(int,input().split())
def li():return list(mi())
abc='abcdefghijklmnopqrstuvwxyz'
# mod=1000000007
mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]

def bo(i):
    return ord(i)-ord('a')



    
def solve():

    
    # for _ in range(ii()):

    n,k = mi()

    seg = []

    for i in range(k):
        seg.append(li())

    dp = [0]*(n+1)

    dp[1] = 1
    for i in range(2,n+1):
        dp[i] += dp[i-1]
        dp[i] %= mod
        for j in range(k):
            if seg[j][0] >= i:
                continue


            l = max(1,i - seg[j][1])

            r =  i - seg[j][0]

            dp[i] += dp[r] - dp[l-1]
            dp[i] += mod
            dp[i] %= mod


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


        









        
if __name__ =="__main__":

    
    if path.exists('input.txt'):
        sys.stdin=open('input.txt', 'r')
        sys.stdout=open('output.txt','w')
    else:
        input=sys.stdin.readline
    solve()

Submission status: Accepted

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

f=[0]*(10**6)
f[0]=1
for i in range(N):
  for l, r in S:
    f[i+l] += f[i]
    f[i+l]%=P
    f[i+r+1]-=f[i]
    f[i+r+1]%=P
  if i:
    f[i+1]+=f[i]
  f[i]%=P
print(f[N-1])

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
s_list = []
a_list = [0] * (n + 1)
b_list = [0] * (n + 1)
a_list[1] = 1
b_list[1] = 1
for i in range(k):
    l, r = map(int, input().split())
    s_list.append([l, r + 1])

for i in range(2, n + 1):
    for l, r in s_list:
        t2 = max(0, i - l)
        t1 = max(0, i - r)
        a_list[i] += b_list[t2] - b_list[t1]
    b_list[i] = (b_list[i - 1] + a_list[i]) % 998244353

print(a_list[n] % 998244353)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
lr=[]
for i in range(k):
  l_,r_=map(int,input().split())
  lr.append([l_,r_])
mod=998244353


#dp[i]=0からi-1マスからiのマスへ行く総数
dp=[0]*(n+1)
sumdp=[0]*(n+1)
#初期条件：マス0に最初いるので１通り
dp[1]=1
sumdp[1]=1
#dp漸化式
for i in range(2,n+1):
  for l,r in lr:
    if i>l:
      if i<=r:
        dp[i]=(dp[i]+sumdp[i-l])%mod
      else:
        dp[i]=(dp[i]+sumdp[i-l]-sumdp[i-r-1])%mod
  sumdp[i]=(sumdp[i-1]+dp[i])%mod
  
  
print(dp[n]%mod)

Submission status: Accepted

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

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

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

for i in range(2, N+1):
    for s in S:
        l = i - s[1]
        r = i - s[0]
        if r < 1:continue
        l = max(1, l)

        dp[i] += dpsum[r] - dpsum[l-1]
        dp[i] %= mod

    dpsum[i] = (dpsum[i-1] + dp[i]) % mod

print(dp[-1])

Submission status: Accepted

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

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

mod = 998244353

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(1, li)

    dp[i] += (dpsum[ri] - dpsum[li - 1]) % mod
  
  dpsum[i] = dpsum[i - 1] + dp[i]

print(dp[n] % mod)

Submission status: Accepted

Solution code:
mod = 998244353

# 貰うDP
# Pythonで普通に通った．
# Aのような累積， のようなものを使って復元して高速化するケースはよくあるらしい．
def main(N, S):
    dp = [0 if n != 0 else 1 for n in range(N)]     # dp[i]はマスiに行く通り数． (答えはdp[-1]), dp[0] = 1 (最初にいる場所だから1通り)
    A = [0 if n != 0 else 1 for n in range(N)]      # dp[i] = A[i] - A[i-1] (i >= 1), A[0] = dp[0] = 1 (i = 0) が成り立つような配列を考える． (累積を取っておく配列)

    for i in range(1, N):   # 今いる点 (注目点)
        for l, r in S:  # 選択行動範囲 (l: 始点, r: 終点)
            if i - l < 0:   # 注目点が選択行動範囲の始点より手前の場合 → 注目点に来るために使用することはできない．
                break
            else:           # 注目点に来るために使用することができる場合
                if i - r <= 0:  # lからrの間で，注目点に行くために使用できる点を逆算． そこに行くことができる = 選択行動範囲の値を選択することで注目点に達することができる通り数．
                    dp[i] += A[i-l]
                else:
                    dp[i] += A[i-l] - A[i-r-1]
        dp[i] %= mod
        A[i] = (A[i-1] + dp[i]) % mod
    print(dp[-1])

if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    S = {tuple(map(int, input().split())) for k in range(K)}
    S = sorted(list(S), key = lambda x:x[0])    # 始点でsort (範囲の重複がないため)
    main(N, S)

Submission status: Accepted

Solution code:
mod = 998244353

# 貰うDP
# Pythonで普通に通った．
def main(N, S):
    dp = [0 if n != 0 else 1 for n in range(N)]     # dp[i]はマスiに行く通り数． (答えはdp[-1]), dp[0] = 1 (最初にいる場所だから1通り)
    A = [0 if n != 0 else 1 for n in range(N)]      # dp[i] = A[i] - A[i-1] (i >= 1), A[0] = dp[0] = 1 (i = 0) が成り立つような配列を考える．

    for i in range(1, N):   # 今いる点 (注目点)
        for l, r in S:  # 選択行動範囲 (l: 始点, r: 終点)
            if i - l < 0:   # 注目点が選択行動範囲の始点より手前の場合 → 注目点に来るために使用することはできない．
                break
            else:           # 注目点に来るために使用することができる場合
                if i - r <= 0:  # lからrの間で，注目点に行くために使用できる点を逆算． そこに行くことができる = 選択行動範囲の値を選択することで注目点に達することができる通り数．
                    dp[i] += A[i-l]
                else:
                    dp[i] += A[i-l] - A[i-r-1]
        dp[i] %= mod
        A[i] = (A[i-1] + dp[i]) % mod
    print(dp[-1])

if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    S = {tuple(map(int, input().split())) for k in range(K)}
    S = sorted(list(S), key = lambda x:x[0])    # 始点でsort (範囲の重複がないため)
    main(N, S)

Submission status: Accepted

Solution code:
mod = 998244353

# 貰うDP
def main(N, S):
    dp = [0 if n != 0 else 1 for n in range(N)]     # dp[i]はマスiに行く通り数． (答えはdp[-1]), dp[0] = 1 (最初にいる場所だから1通り)
    A = [0 if n != 0 else 1 for n in range(N)]      # dp[i] = A[i] - A[i-1] (i >= 1), A[0] = dp[0] = 1 (i = 0) が成り立つような配列を考える．

    for i in range(1, N):   # 今いる点 (注目点)
        for l, r in S:  # 選択行動範囲 (l: 始点, r: 終点)
            if i - l < 0:   # 注目点が選択行動範囲の始点より手前の場合 → 注目点に来るために使用することはできない．
                break
            else:           # 注目点に来るために使用することができる場合
                dp[i] += A[i-l] - A[max(i-r, 0)-1]  # lからrの間で，注目点に行くために使用できる点を逆算． そこに行くことができる = 選択行動範囲の値を選択することで注目点に達することができる通り数．
        dp[i] %= mod
        A[i] = (A[i-1] + dp[i]) % mod
    print(dp[-1])

if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    S = {tuple(map(int, input().split())) for k in range(K)}
    S = sorted(list(S), key = lambda x:x[0])    # 始点でsort (範囲の重複がないため)
    main(N, S)

Submission status: Accepted

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

DP=[0 for _ in range(n+1)]
SDP=[0 for _ in range(n+1)]
DP[1]=1
SDP[1]=1

for i in range(2,n+1):
    for l,r in LR:
        DP[i] +=(SDP[max(i-l,0)]-SDP[max(i-r,1)-1])%mod
        DP[i] %=mod
    SDP[i]=(SDP[i-1]+DP[i])%mod
print(DP[n])

Submission status: Accepted

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

dp = [0] * n
dp[0] = 1
acc = 0

for i in range(1, n):
    # 例4のi=13, lr=[[5, 8], [1, 3], [10, 15]]の場合を想像すると書きやすい
    for li, ri in lr:
        if i - li >= 0:
            acc += dp[i - li]
            acc %= mod
        if i - ri - 1 >= 0:
            acc -= dp[i - ri - 1]
            acc %= mod
    dp[i] = acc
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    

def main():
    N, K = MI()
    L = [LI() for i in range(K)]
    D = [0] * N
    D[0] = 1
    D[1] = -1
    num = 0
    mod = 998244353
    for index in range(N):
        num += D[index] % mod
        for l, r in L:
            if index + r + 1 <= N-1:
                D[index+l] += num
                D[index+r+1] -= num
            elif index+l <= N-1:
                D[index+l] += num
                
    print(num % mod)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

NUM=998244353
dp=[0]*(N+1)
dp[1]=1
sums=[0]*(N+1)
sums[1]=1
for i in range(2,N+1):
    for s in S:
        _l,_r=i-s[0],i-s[1]-1
        if _l<0:
            continue
        elif _r<0:
            _r=0
        dp[i]+=sums[_l]-sums[_r]
        dp[i]%=NUM
    sums[i]=dp[i]+sums[i-1]
    sums[i]%=NUM

print(dp[N])

Submission status: Accepted

Solution code:
p = 998244353

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

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

dp[0] = 1
dp[1] = -1

for i in range(n):
    for l, r in num:
        dp[i+l] += dp[i]
        dp[i+r+1] -= dp[i]
    dp[i+1] += dp[i]
    dp[i+1] %= p

print(dp[n-1])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = [] 
mod = 998244353

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

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

for i in range(2,n+1):
    for l, r in s:
        li = max(i-r,1)
        ri = max(i-l,0)
        dp[i] += (dpsum[ri] - dpsum[li-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())
dp = [0] * N
dp[0] = 1
dp_sum = [0] * N
dp_sum[0] = 1
L = [0] * K
R = [0] * K
mod = 998244353

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

for i in range(1, N):
    # マスiにたどり着くためのパターン数を数える
    cnt = 0
    for j in range(K):
        start = max(0, i - R[j])
        end = i - L[j]
        cnt += (dp_sum[end] - dp_sum[start - 1]) % mod
        cnt %= mod
    dp[i] = cnt
    dp_sum[i] = dp_sum[i - 1] + cnt

print(dp[N - 1])