Problem:


Score : 400 points

Problem Statement

There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.

Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.

You are given an integer K that is less than or equal to 10, and K non-intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K].
Let S be the union of these K segments.
Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.

When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.

To help Tak, find the number of ways to go to Cell N, modulo 998244353.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq K \leq \min(N, 10)

1 \leq L_i \leq R_i \leq N

[L_i, R_i] and [L_j, R_j] do not intersect (i \neq j) 

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
L_1 R_1
L_2 R_2
:
L_K R_K

Output

Print the number of ways for Tak to go from Cell 1 to Cell N, modulo 998244353.

Sample Input 1

5 2
1 1
3 4

Sample Output 1

4

The set S is the union of the segment [1, 1] and the segment [3, 4], therefore S = \{ 1, 3, 4 \} holds.

There are 4 possible ways to get to Cell 5:

1 \to 2 \to 3 \to 4 \to 5,

1 \to 2 \to 5,

1 \to 4 \to 5 and

1 \to 5.

Sample Input 2

5 2
3 3
5 5

Sample Output 2

0

Because S = \{ 3, 5 \} holds, you cannot reach to Cell 5.
Print 0.

Sample Input 3

5 1
1 2

Sample Output 3

5

Sample Input 4

60 3
5 8
1 3
10 15

Sample Output 4

221823067

Note that you have to print the answer modulo 998244353.



Sample input:
5 2
1 1
3 4


Sample output:
4

Submission status: Accepted

Solution code:
import sys


def main():
    N, K = map(int, sys.stdin.readline().rstrip().split())
    L = [0] * 10
    R = [0] * 10
    for i in range(K):
        l, r = map(int, sys.stdin.readline().rstrip().split())
        L[i], R[i] = l, r

    dp = [0] * (N + 1)
    up = [0] * (N + 1)
    up[0] = 1
    up[1] = -1
    for i in range(1, N + 1):
        dp[i] = dp[i - 1] + up[i - 1]
        for j in range(K):
            if i + (L[j] - 1) < N + 1:
                up[i + (L[j] - 1)] += dp[i]
            if i + R[j] < N + 1:
                up[i + R[j]] -= dp[i]
        dp[i] %= 998244353

    print(dp[N])


main()

Submission status: Accepted

Solution code:

def main():
    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)
    dpsum = [0] * (N + 1)
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2,N+1):
        for j in range(K):
            l = i - R[j]
            r = i - L[j]
            if r <= 0:
                continue
            l = max(1,l)
            dp[i] += dpsum[r] - dpsum[l-1]
            dp[i] %= MOD
        dpsum[i] = dpsum[i-1] + dp[i]
        dpsum[i] %= MOD

    print(dp[N])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#dpで素直にやるとO(N^2)だから、累積和で高速化しO(KN)にする

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

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

cnt = [0]*n
cnt[0] = 1
sum = [0]*n
sum[0] = 1
for i in range(1,n):
  for j in range(k):
    if i > s[j][1]:
      cnt[i] += sum[i-s[j][0]] - sum[i-s[j][1]-1]
    elif i >= s[j][0]:
      cnt[i] += sum[i-s[j][0]]
    cnt[i] %= mod
    sum[i] = (sum[i-1] + cnt[i]) % mod

print(cnt[-1])

Submission status: Accepted

Solution code:
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+5)
dp[1] = 1

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

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  field=[LI() for _ in range(k)]

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

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

# main()
print(main())

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from sys import exit

import sys
sys.setrecursionlimit(1000000000)
mod = 998244353

#############
# Main Code #
#############

N, K = getNM()
que = [getList() for i in range(K)]

dp = [0] * (N + 1) # dp[i] iの時の通りの数
imos = [0] * (N + 1) # imos[i]: dp[1] ~ dp[i]までの累計
dp[1] = 1
imos[1] = 1

# 貰うdp
# dp += dp[l] - dp[r]

for i in range(2, N + 1):
    for l, r in que:
        if i - l >= 0:
            dp[i] += imos[i - l] - imos[max((i - r - 1), 0)]
            dp[i] %= mod
    imos[i] = dp[i]
    imos[i] += imos[i - 1]
    imos[i] %= mod

print(dp[N] % mod)

"""
# 配るdp

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

for i in range(1, N + 1):
    dp[i] += dp[i - 1]
    dp[i] %= mod
    for l, r in que:
        if i + l <= N:
            dp[i + l] += dp[i]
        if i + r + 1 <= N:
            dp[i + r + 1] -= dp[i]
print(dp[N] % mod)
"""

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] * (N+1)
dpsum = [0] * (N+1)
dp[1] = 1
dpsum[1] = 1
for i in range(2, N+1):
    for l, r in LR:
        li = i-r
        ri = i-l
        if ri < 0: continue
        li = max(1, li)
        dp[i] += dpsum[ri] - dpsum[li-1]
        dp[i] = dp[i] % mod
    
    dpsum[i] = dpsum[i-1] + dp[i] 
    dpsum[i] = dpsum[i] % mod

print(dp[N])

Submission status: Accepted

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

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

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

for i in range(2, N + 1):
    for L, R in LR:
        l = i - R
        r = i - L
        
        if r < 0:
            continue
        l = max(l, 0)
        
        dp[i] += dpsum[r] - dpsum[l - 1]
        dp[i] %= mod
    dpsum[i] = dpsum[i - 1] + dp[i]

print(dp[N])

Submission status: Accepted

Solution code:
#   ==========     //\\       //||     ||====//||
#       ||        //  \\        ||     ||   // ||
#       ||       //====\\       ||     ||  //  ||
#       ||      //      \\      ||     || //   ||
#   ========== //        \\  ========  ||//====|| 
#  code

def solve():
    MOD = 998244353
    n, k = map(int, input().split())
    segments = []
    for i in range(k):
        l, r = map(int, input().split())
        segments.append([l, r])
    
    dp = [0] * (n)
    dp[0] = 1
    pdp = [1] * (n)
    for i in range(1 , n):
        pdp[i] = pdp[i - 1] + dp[i]
    
    for j in range(n):
        for i in range(k):
            if j <= segments[i][1] and j >= segments[i][0]:
                dp[j] += pdp[j - segments[i][0]]
            elif j > segments[i][1]:
                dp[j] += pdp[j - segments[i][0]] - pdp[j - segments[i][1] - 1]
            dp[j] %= MOD
            # print(i, dp[j])
            if j > 0:
                pdp[j] = pdp[j - 1] + dp[j]
            else:
                pdp[j] = dp[j]
            pdp[j] %= MOD
    print(dp[n - 1])
    return

def main():
    t = 1
    # t = int(input())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
DP = [0]*(N+1)
DPsum=[0]*(N+1)
DP[1]=1
DPsum[1]=1
lr = []
m=998244353
for _ in range(K):
    l,r = map(int,input().split())
    lr.append([l,r])

for i in range(2,N+1):
    for l,r in lr:
        lx = i - r - 1
        rx = i - l
        lx = max(0,lx)
        rx = max(0,rx)
        DP[i]+= DPsum[rx]-DPsum[lx]
    DPsum[i]=(DPsum[i-1]+DP[i])%m
print(DP[N]%m)

Submission status: Accepted

Solution code:
n,k=list(map(int,input().split()))
s=[]
b=[0]*k
for x in range(k):
    
    l,r=list(map(int,input().split()))
    s.append((l,r))
    
d=[0]*n
d[0]=1
for i in range(1,n):
    j=0
    for l,r in s:
        if i-l>=0:
            b[j]+=d[i-l]
        if i-r-1>=0:
            b[j]-=d[i-r-1]
        
        d[i]+=b[j]
        j+=1
    d[i]%=998244353
print(d[-1])

Submission status: Accepted

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

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

dp[1] = 1
s = sorted(s)
counter = 0
for i in range(1, n+1):
    counter += cumsum[i]
    dp[i] += counter
    dp[i] %= mod
    for l, r in s:
        if i+l <= n:
            cumsum[i+l] += dp[i]
        if i+r+1 <= n:
            cumsum[i+r+1] -= dp[i]
print(dp[n] % mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

MOD=998244353
D=[0]*(N+1)
D[1]=1

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


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

        D[i]+=B[j]
        
    D[i]%=998244353

print(D[N])

Submission status: Accepted

Solution code:
MOD = 998244353
N, K = map(int, input().split())
rl = [list(map(int, input().split())) for _ in range(K)]
dp = [0] * (N + 1)
dp[1] = 1
dp[2] = -1

for i in range(1, N + 1):
    dp[i] += dp[i - 1]
    for j in range(K):
        l, r = rl[j][0], rl[j][1]
        if i + l <= N:
            dp[i + l] += dp[i]
            dp[i + l] %= MOD
        if i + r + 1 <= N:
            dp[i + r + 1] -= dp[i]
            dp[i + r + 1] %= MOD
print(dp[N] % MOD)

Submission status: Accepted

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
# from numba import njit,i8
 
 
# @njit(i8(i8,i8,i8,i8[:,:],i8[:],i8,i8))
def give_dp(N,K,mod,LR,dp,l,r):
    for i in range(N):
        if i > 0:
            dp[i] += dp[i-1]
            dp[i] %= mod
        for k in range(K):
            l = LR[k][0]
            r = LR[k][1]
            if i + l < N:
                dp[i+l] += dp[i]
                dp[i+1] %= mod
            if i + r + 1 < N:
                dp[i+r+1] -= dp[i]
                dp[i+1] %= mod
    return dp[-1]
 
 
def main():
    N,K = map(int,input().split())
    LR = [list(map(int,input().split())) for i in range(K)]
    # LR = np.array(LR)
 
    mod = 998244353
 
    dp = [0 for i in range(N)]
    dp[0] = 1
    dp[1] = -1
    # dp = np.array(dp)
 
    res = give_dp(N,K,mod,LR,dp,0,0)
    res %= mod
 
    print(res)
 
 
 
main()

Submission status: Accepted

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8(i8,i8,i8,i8[:,:],i8[:],i8,i8))
def give_dp(N,K,mod,LR,dp,l,r):
    for i in range(N):
        if i > 0:
            dp[i] += dp[i-1]
            dp[i] %= mod
        for k in range(K):
            l = LR[k][0]
            r = LR[k][1]
            if i + l < N:
                dp[i+l] += dp[i]
                dp[i+1] %= mod
            if i + r < N:
                dp[i+r+1] -= dp[i]
                dp[i+1] %= mod
    return dp[-1]


def main():
    N,K = map(int,input().split())
    LR = [list(map(int,input().split())) for i in range(K)]
    LR = np.array(LR)

    mod = 998244353

    dp = [0 for i in range(N)]
    dp[0] = 1
    dp[1] = -1
    dp = np.array(dp)

    res = give_dp(N,K,mod,LR,dp,0,0)
    res %= mod

    print(res)



main()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
MOD = 998244353
N, K = map(int, input().split())
S = [0] * K
for i in range(K):
    l, r = map(int, input().split())
    S[i] = (l, r)

dp = [0] * (N + 2)
acc = [0] * (N + 2)
dp[1] = 1
acc[1] = 1
for i in range(1, N + 1):
    for j in range(K):
        li = i - S[j][1]
        ri = i - S[j][0]
        if ri < 0:
            continue
        li = max(li, 0)
        dp[i] += (acc[ri] - acc[li - 1]) % MOD
    acc[i] = (acc[i - 1] + dp[i]) % MOD
print(dp[N] % MOD)

Submission status: Accepted

Solution code:
# 解説などを参考に作成
"""
N = 10, LR = [2, 4] を例とする.
fi:=マスiまで移動する方法の個数とおく.
便宜上0マスから始めると、
    N:  0 1 2 3 4 5 6 7 8 9 10
    fi: 0 1 0 1 1 2 2 4 5 8 11
となる.(1マス目には最初からいるのでf1 = 1とする.)
ここで、N=5,6の時で考えると、LR=[2,4]から
    f5 = f1 + f2 + f3  (∵2～4マス前からしか遷移がないので)
    f6 =      f2 + f3 + f4
よってf5とf6の差はf1とf4によって求めることができる.
    f6 = f5 - f1 + f4
一般化すると、
    fi = fi-1 - fi-1-R + fi-L
LRが複数ある場合でも区間が重複しないので、各区間に対して - fi-1-R + fi-L 部分を計算して fi を求めることができる.
計算量はO(KN) (K:=重複しない区間LRの個数)
"""


# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, K, LR):
    mod = 998244353
    dp = [0] * (N + 1)
    dp[1] = 1
    # dp[0] は基本0として扱ってよいが, dp[2]の計算時のみ,dp[0]とdp[1]の差分=0となる必要がある.
    # => この時のみ、dp[0]を1として計算しないと fi = fi-1 - fi-1-R + fi-L のルールに合わなくなる.
    # 他の人の解答(#16897281, #16895566)見ると階差数列？敵なのを持つことで解決できそうだったけど,
    # 内容が理解できなかったのでdp[2]までは手動実装することにした.
    dp[2] = 1 if 1 in [lr[0] for lr in LR] else 0
    for i in range(3, N + 1):
        x = 0
        for l, r in LR:
            x += dp[max(i - l, 0)] - dp[max(i - 1 - r, 0)]
        dp[i] = (dp[i - 1] + x) % mod
    print(dp[N])


if __name__ == '__main__':
    N, K = map(int, input().split())
    LR = [[int(i) for i in input().split()] for _ in range(K)]
    solve(N, K, LR)

    # # test
    # from random import randint
    # from func import random_str
    # N, K = 2 * 10 ** 5, 1
    # LR = [[1, N]]
    # solve(N, K, LR)

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
s = []
for i in range(k):
    a, b = list(map(int, input().split()))
    s.append((a, b))
dp = [0]*(n+1)
v = 0
mod = 998244353
for i in range(1, n+1):
    if i == 1:
        for l, r in s:
            if i+l <= n:
                dp[i+l] += 1
            if i+r+1 <= n:
                dp[i+r+1] -= 1
    else:
        v += dp[i]
        v %= mod
        for l, r in s:
            if i+l <= n:
                dp[i+l] += v
            if i+r+1 <= n:
                dp[i+r+1] -= v


print(v % mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
# import decimal
# from decimal import Decimal
# decimal.getcontext().prec = 10

# from heapq import heappush, heappop, heapify
# import math
# from math import gcd
# import itertools as it
# import collections
# from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

mod = 998244353

N, K = inpl()
left, right = [0] * K, [0] * K
for i in range(K):
    left[i], right[i] = inpl();

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

for i in range(2, N + 1):
    for k in range(K):
        dp[i] += wa[max(0, i - left[k])] - wa[max(0, i - right[k] - 1)]
        dp[i] %= mod
    wa[i] = (wa[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 + 1)
dpsum = [0] * (N + 1)
dp[1] = 1
dpsum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = max(i - LR[j][1], 1)
        ri = i - LR[j][0]
        if ri < 0:
            continue
        dp[i] += dpsum[ri] - dpsum[li - 1]
        dp[i] %= mod
    dpsum[i] = dpsum[i - 1] + dp[i]

print(dp[N])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
# import decimal
# from decimal import Decimal
# decimal.getcontext().prec = 10

# from heapq import heappush, heappop, heapify
# import math
# from math import gcd
# import itertools as it
# import collections
# from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

mod = 998244353

N, K = inpl()
left, right = [0] * K, [0] * K
for i in range(K):
    left[i], right[i] = inpl();

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

for i in range(2, N + 1):
    for k in range(K):
        if i - left[k] >= 0:
            dp[i] += wa[i - left[k]] - wa[max(0, i - right[k] - 1)]
        dp[i] %= mod
        wa[i] = (wa[i-1] +  dp[i]) % mod
print(dp[N])

Submission status: Accepted

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

MOD = 998244353

interval = []
for i in range(K):
    intv = [int(x) for x in input().split()]
    interval.append(intv)

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

for i in range(N-1):
    for L,R in interval:
        if L <= N-1 - i:
            diff[i+L-1] += dp[i]
        if R+1 <= N-1 - i:
            diff[i+R] -= dp[i]
    dp[i+1] = dp[i] + diff[i]
    dp[i+1] %= MOD

print(dp[N-1])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
dp=[0 for i in range(n+1)]
dp[1]=1
accum=[0 for i in range(n+1)]
accum[1]=1
s=[]
for i in range(k):
    x,y=map(int,input().split())
    s.append([x,y])
for i in range(2,n+1):
    for j in s:
        l,r=j
        tmpl=i-r
        tmpr=i-l
        if(tmpl<1):
            tmpl=1
        if(tmpr>=i):
            tmpr=i-1
        if(tmpr<0):
            continue
        dp[i]+=accum[tmpr]-accum[tmpl-1]
        dp[i]%=998244353
    accum[i]=dp[i]+accum[i-1]
    accum[i]%=998244353
print(dp[n]%998244353)

Submission status: Accepted

Solution code:
N,K = [int(i) for i in input().split()]
mod = 998244353
LR = []
S = []
dp = [0]*(N+1)
dps = [0]*(N+1)
dps[1] = 1
dp[1] = 1
for i in range(K):
  LR.append([int(i) for i in input().split()])

for i in range(1,N+1):
  for l,r in LR:
    l,r = i - r,i - l
    #print(l,r)
    if r < 1:
      continue
    l = max(1,l)
    dp[i] += dps[r] - dps[l-1]
    dp[i] %= mod
    #print(dp[i])
    
  dps[i] = dps[i-1] + dp[i]
  #print(dp, dps)
print(dp[-1])

Submission status: Accepted

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

# 考え方は通常のDPだが、そのままだとO(N^2)となる
# 独立した区間なので、区間の和を求める部分の計算量を落とせば良い(dpsumで累積和を計算)
dp = [0]*(N+1)
dp[1] = 1

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

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

print(dp[N])

Submission status: Accepted

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

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

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

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

print(dp[N])

Submission status: Accepted

Solution code:
# inp.readline()
# int(inp.readline())
# out.write()
# raw_input()
# map(int,raw_input().split())
# map(int,inp.readline().split())
# for _ in xrange(input()):
# print "Case #"+str(_+1)+": "+ 
if __name__ == "__main__":
    from sys import stdin as inp, stdout as out,setrecursionlimit as srl
    from collections import Counter,defaultdict,deque
    from heapq import *
    def upd(idx,v):
      while idx<len(b):
        b[idx]=(b[idx]+v)%mod
        idx+=(idx&-idx)
    def acc(idx):
        s=0
        while idx>0:
            s=(s+b[idx])%mod
            idx-=(idx&-idx)
        return s
    for _ in xrange(1):
        n,k=map(int,inp.readline().split())
        a=[map(int,inp.readline().split()) for i in xrange(k)]
        b=[0]*(n+1)
        mod=998244353
        upd(1,1)
        for i in xrange(2,n+1):
          for l,r in a:
            upd(i,acc(max(0,i-l))-acc(max(0,i-r-1))%mod)
        print (acc(n)-acc(n-1))%mod

Submission status: Accepted

Solution code:
MOD = 998244353

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

s = [0] * (n + 2)
for i in range(k):
    for j in range(l[i], r[i] + 1):
        s[j] = 1

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

Submission status: Accepted

Solution code:
# inp.readline()
# int(inp.readline())
# out.write()
# raw_input()
# map(int,raw_input().split())
# map(int,inp.readline().split())
# for _ in xrange(input()):
# print "Case #"+str(_+1)+": "+ 
if __name__ == "__main__":
    from sys import stdin as inp, stdout as out,setrecursionlimit as srl
    from collections import Counter,defaultdict,deque
    from heapq import *
    for _ in xrange(1):
        n,k=map(int,inp.readline().split())
        a=[map(int,inp.readline().split()) for i in xrange(k)]
        b=[0]*(n+1)
        b[1]=1
        mod=998244353
        for i in xrange(2,n+1):
          b[i]=b[i-1]
          for l,r in a:
            b[i]=(b[i]+b[max(0,i-l)]-b[max(0,i-r-1)])%mod
        print (b[-1]-b[-2])%mod

Submission status: Accepted

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

    S = []
    LR = []
    for i in range(K):
        l, r = map(int, input().split())
        LR.append((l, r))
    
    LR.sort()
    # for (l, r) in LR:
    #     for x in range(l, min(r+1, N)):
    #         S.append(x)

    a = [0] * N
    f = [0] * N
    f[0] = 1
    a[1] = -1

    for i in range(N):
        if i > 0:
            f[i] = (f[i-1] + a[i]) % MOD
        for (l, r) in LR:
            if i+l < N:
                a[i+l] = (a[i+l] + f[i]) % MOD
            if i+r+1 < N:
                a[i+r+1] = (a[i+r+1] - f[i]) % MOD
    # print(f)
    print(f[N-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

for _ in range(K):
  L, R = map(int, input().split())
  move.append((L, R))

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

for i in range(1, N):
  for l, r in move:
    dp[i] += accumdp[max(i-l+1, 0)] - accumdp[max(i-r, 0)]
  dp[i] %= MOD
  accumdp.append((accumdp[-1] + dp[i])%MOD)

print(dp[-1])

Submission status: Accepted

Solution code:
MOD = 998244353
N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(K)]
 
dp = [0] * (N+1)
dp[1] = 1    #ok
for i in range(1, N):
  dp[i] += dp[i-1]   #as min k = 1, so carry this on to the next
  dp[i] %= MOD
  for l, r in LR:
    ll = i + l
    rr = i + r
    if ll <= N:
      dp[ll] += dp[i]    #yes ll is accesible
      dp[ll] %= MOD
    if rr < N:
      dp[rr+1] -= dp[i]    #not accessible and will get cancelled out when we take prefix sum
      dp[rr+1] %= MOD
 
print(dp[-1])

Submission status: Accepted

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

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

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

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

print(dp[N-1])

Submission status: Accepted

Solution code:
import sys
N,K=map(int, sys.stdin.readline().split())
LR=[ map(int, sys.stdin.readline().split()) for _ in range(K) ]

dp=[0]*(N+1)
sum_dp=[0]
mod=998244353

i=1
dp[i]=1
sum_dp.append(sum_dp[-1]+dp[i])

for i in range(2,N+1):
    for l,r in LR:
        dp[i]+=sum_dp[max(0,i-l)]-sum_dp[max(0,i-r-1)]
        dp[i]%=mod
    sum_dp.append( (sum_dp[-1]+dp[i])%mod )

print dp[-1]

Submission status: Accepted

Solution code:
def solve(N, LR):
    mod = 998244353

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

    for i in range(2, N+1):
        for lr in LR:
            left = i - lr[1]
            right = i - lr[0]
            if right < 0:
                continue
            left = max(left, 0)
            dp[i] += (dpsum[right] - dpsum[left-1])
            dp[i] %= mod
        dpsum[i] = dpsum[i-1] + dp[i]
        dpsum[i] %= mod

    return dp[N]


if __name__ == "__main__":
    N, K = map(int, input().split())
    LR = [list(map(int, input().split())) for _ in range(K)]
    print(solve(N, LR))

Submission status: Accepted

Solution code:
#もらうDP + 累積和
n, k = map(int, input().split())
mod = 998244353
li = []
for _ in range(k):
    l, r = map(int, input().split())
    li.append((l, r))
li.sort()
dp = [0]*(2*n+1)
s = [0] * (2*n+1)
dp[1] = 1
s[1] = 1
for i in range(2, n+1):
    for t in li:
        l, r = t
        dp[i] += s[max(i-l, 0)]
        dp[i] -= s[max(i-r-1, 0)]
        dp[i] %= mod
    s[i] = s[i-1] + dp[i]
    s[i] %= mod
print(dp[i]%mod)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

N, K = map(int, input().split())
LR = [list(map(int, input().split())) for i in range(K)]
MOD = 998244353
 
dp = [0] * (N + 1)
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1
 
 
def get(l, r, i):
    return dp_sum[max((i - l), 0)] - dp_sum[max((i - r-1), 0)]
 
 
for i in range(1, N+1):
    for l, r in LR:
        dp[i] += get(l, r, i) % MOD
    dp_sum[i] = (dp_sum[i - 1] + dp[i])%MOD

print(dp[N] % MOD)

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)

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

for i in range(1, N):
  for j in range(K):
    dpd[min(i+L[j],N+1)]+=dp[i]
    dpd[min(i+R[j]+1,N+1)]-=dp[i]
  dp[i+1]=(dp[i]+dpd[i+1])%998244353

print(dp[N])

Submission status: Accepted

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

MOD = 998244353
n, k = map(int, input().split())
s = list()
for i in range(k):
    s.append(tuple(map(int, input().split())))

dp = [0] + [0] * n
diff = [0] + [0] * n
dp[1] = 1
diff[2] = -1
for i in range(1, n):
    for j, k in s:
        if i + j > n:
            continue
        diff[i + j] += dp[i]
        if i + k + 1 > n:
            continue
        diff[i + k + 1] -= dp[i]
    #dp[i] = (dp[i - 1] + diff[i]) % MOD
    dp[i + 1] = (dp[i] + diff[i + 1]) % MOD
print(dp[n])

Submission status: Accepted

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

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

Submission status: Accepted

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

MOD = 998244353
n, k = map(int, input().split())
s = list()
for i in range(k):
    s.append(tuple(map(int, input().split())))

dp = [0] + [0] * n
diff = [0] + [0] * n
dp[1] = 1
for i in range(1, n):
    for j, k in s:
        if i + j > n:
            continue
        diff[i + j] += dp[i]
        if i + k + 1 > n:
            continue
        diff[i + k + 1] -= dp[i]
    dp[i] = (dp[i - 1] + diff[i]) % MOD
    dp[i + 1] = (dp[i] + diff[i + 1]) % 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))
lr.sort()

dp = [0]*(N+1)
dpsum = [0]*(N+1)
dp[1] = 1
dpsum[1] = 1
for i in range(2, N+1):
    for l, r in lr:
        lj = max(1, i-r)
        rj = i-l

        if rj < 1:
            continue

        dp[i] += dpsum[rj]-dpsum[lj-1]
        dp[i] %= MOD
    dpsum[i] = dp[i]+dpsum[i-1]

print(dp[N])

Submission status: Accepted

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

dp = [0]*(n+1)
dp[1] = 1
dpac = [0]*(n+1)
dpac[1] = 1
for i in range(2, n+1):
    for kl, kr in kkn:
        l = i-kr
        r = i-kl
        if r < 0: continue
        l = max(l, 0)
        dp[i] += dpac[r] - dpac[l-1]
        dp[i] %= MOD
    dpac[i] = dpac[i-1] + dp[i]
    dpac[i] %= MOD
print(dp[n])

Submission status: Accepted

Solution code:
n, k = map(int, input().split()); m = 998244353; a = []
for i in range(k): a.append(list(map(int, input().split())))
b = [0]*n; b.append(1); c = [0]*n; c.append(1)
for i in range(1, n):
    d = 0
    for j in range(k): d = (d+c[n+i-a[j][0]]-c[n+i-a[j][1]-1])%m
    b.append(d); c.append(c[-1]+d)
print(b[-1]%m)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
MOD = 998244353
dp = [0]*(N*3)

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

LR.sort()

imos = [0]*(N*3)
dp[1] = 1
imos[1] = 1
for i in range(1, N):
    if i >= 2:
        dp[i+1] += dp[i]

    for l, r in LR:
        dp[i+l] += dp[i]
        dp[i+l] %= MOD
        dp[i+r+1] -= dp[i]
        dp[i+r+1] %= MOD
    
    

print(dp[N]%MOD)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
INF = float("inf")
MOD = 998244353



# 処理内容
def main():
    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())

    dp = [0]*(N*2 + 1)
    a = [0]*(N*2 + 1)
    dp[0] = 1
    a[1] = -1
    for i in range(N):
        for j in range(K):
            a[i+L[j]] += dp[i]
            a[i+R[j]+1] -= dp[i]
        dp[i+1] = (dp[i] + a[i+1]) % MOD
    
    print(dp[N-1])



if __name__ == '__main__':
    main()