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:
n, k = map(int, input().split())
lr = [list(map(int, input().split())) for i in range(k)]
dp = [0 for i in range(n+1)]
mod = 998244353
lr.sort()
a = [0]*(n+1)
dp[0]=1; a[0]=1
for i in range(1,n+1):
    for l, r in lr:
        if i-l<0: continue
        elif i-l>=0 and i-r-1<0: 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]
    a[i]%=mod
print(dp[n-1]%mod)

Submission status: Accepted

Solution code:
#editorial
n,k=map(int,input().split())
*lr,=[tuple(map(int, input().split())) for _ in range(k)]
res =[0]*(2*n+3)
##############
diff=[0]*(2*n+3)
######
#res[0]=1

diff[0]=1
diff[1]=-1
mod=998244353

for i in range(n+1):
    res[i]=res[i-1]+diff[i]
    res[i]%=mod
    diff[i]%=mod
    for li,ri in lr:
        diff[i+li]+=res[i]
        diff[i+ri+1]-=res[i]
    #print(res[:n+1])
    #print((diff[:n+1]))
print(res[n-1]%mod)
#print(res[:n+1])
#print((diff[:n+1]))

Submission status: Accepted

Solution code:
# 解説見た
n,k = map(int,input().split())
lr = [list(map(int,input().split())) for _ in range(k)]
dp = [0]*(n+1)
sdp = [0]*(n+1)
dp[1],sdp[1] = 1,1
mod = 998244353

for i in range(1,n+1):
    for l,r in lr:
        if i-l<0:
            continue
        else:
            dp[i] += sdp[i-l] - sdp[max(0,i-r-1)]
    sdp[i] = sdp[i-1] + dp[i]
    dp[i] %= mod
    sdp[i] %= mod
    
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
dp = [0]*(N*3+1)
dp[1] = 1
dp[2] = -1
mod = 998244353
LR = [list(mapint()) for _ in range(K)]
for i in range(1, N+1):
    dp[i] = (dp[i]+dp[i-1])%mod
    for l, r in LR:
        dp[i+l] = (dp[i+l]+dp[i])%mod
        dp[i+r+1] = (dp[i+r+1]-dp[i])%mod

print(dp[N])

Submission status: Accepted

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

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

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

for i in range(1,n):
    dpsum[i]=dp[i]+dpsum[i-1]
    for j in range(k):
        l,r=k_list[j]
        li=i+l
        ri=i+r+1
        if li<=n:
            dp[li]+=dpsum[i]
            dp[li]=dp[li]%998244353
        if ri<=n:
            dp[ri]-=dpsum[i]
            dp[ri]=dp[ri]%998244353

print(dp[n])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 998244353
inf = float("INF")
class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        if i < 0:
            return
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 0
        s = 0
        step = 1 << self.size.bit_length()
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                print(self.bit[i + step - 1], i, step)
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

    def __len__(self):
        return self.size
    
    def __str__(self):
        res = [None] * self.size
        for i in range(self.size):
            res[i] = str(self.sum(i) -self.sum(i - 1))
        return ", ".join(res)
#solve
def solve():
    n, k = LI()
    lr = LIR(k)
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = -1
    for i in range(1, n):
        for l, r in lr:
            if i + l <= n:
                dp[i + l] += dp[i]
                if i + r + 1 <= n:
                    dp[i + r + 1] -= dp[i]
        dp[i + 1] = (dp[i+1]+dp[i])%mod
    print(dp[-1])


    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

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

for i in range(0, n):
    if i>0: dp[i] += dp[i-1]
    dp[i] %= 998244353
    for l,r in lr:
        if i+l > n: continue
        dp[i+l] += dp[i]
        dp[min(n, i+r+1)] -= dp[i]

print(dp[-2] % 998244353)

Submission status: Accepted

Solution code:
def mod(val, mod_base):
  if val >= mod_base:
    return val%mod_base
  return val

# 配るDP
def resolve():
  base = 998244353
  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)
  dp[1] = 1

  for i in range(1, N):
    dp[i] += dp[i-1]

    for lr in LRs:
      left = i + lr[0]
      right = i + lr[1] + 1
      if left <= N:
        dp[left] += dp[i]
        dp[left] = mod(dp[left], base)
      if right <= N:
        dp[right] -= dp[i]
        dp[right] = mod(dp[right], base)
  print(mod(dp[-1], base))

if __name__ == "__main__":
  resolve()

Submission status: Accepted

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

dp=[0]*(2*n+10)
dp[0]=1
dp[1]=-1
for i in range(n):
    for l,r in lst:
        dp[i+l]+=dp[i]
        dp[i+r+1]-=dp[i]
    
    dp[i+1]+=dp[i]
    dp[i+1]%=mod


print(dp[n-1])

Submission status: Accepted

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


dp=[1]
imos=[0]*(2*n+10)
imos[0]=1
imos[1]=-1
for i in range(n):
    for l,r in lst:
        imos[i+l]+=dp[-1]
        imos[i+r+1]-=dp[-1]
    dp.append((dp[-1]+imos[i+1])%mod)


print(dp[n-1])

Submission status: Accepted

Solution code:
import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n, k = read_ints()
    mod = 998244353
    dp = [0] * (n + 1)
    dp[0] = 1
    s = 1
    query = [read_int_list() for _ in range(k)]
    
    for i in range(1, n + 1):
        s += dp[i]
        for l, r in query:
            if l + i <= n:
                dp[i + l] = (dp[i + l] + s) % mod
            if r + i + 1 <= n:
                dp[i + r + 1] = (dp[i + r + 1] - s) % mod
    print(dp[n])

if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
def mod(val, mod_base):
  if val >= mod_base:
    return val%mod_base
  return val

# 配るDP
def resolve():
  base = 998244353
  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)
  dp_sum = [0] * (N+1)
  dp[1] = 1
  dp_sum[1] = 1

  for i in range(1, N):
    dp_sum[i] = dp[i] + dp_sum[i-1]

    for lr in LRs:
      left = i + lr[0]
      right = i + lr[1] + 1
      if left <= N:
        dp[left] += dp_sum[i]
        dp[left] = mod(dp[left], base)
      if right <= N:
        dp[right] -= dp_sum[i]
        dp[right] = mod(dp[right], base)
  print(mod(dp[-1], base))

if __name__ == "__main__":
  resolve()

Submission status: Accepted

Solution code:
n, k = [int(_) for _ in input().split()]
s = []
for i in range(k):
    s.append([int(_) for _ in input().split()])
dp = [0 for i in range(n)]
dp[0] = 1
dp_s = [0 for i in range(n+1)]
dp_s[1] = 1
for i in range(1, n):
    for j in range(len(s)):
        r, l = s[j]
        if i-r >= 0:
            if i-l >= 0:
                dp[i] += dp_s[i-r+1] - dp_s[i-l]
            else:
                dp[i] += dp_s[i-r+1] - dp_s[0]
    dp[i] = dp[i] % 998244353
    dp_s[i+1] += dp_s[i] + dp[i]
    dp_s[i+1] = dp_s[i+1] % 998244353
print(dp[-1])

Submission status: Accepted

Solution code:
n, k = [int(_) for _ in input().split()]
s = []
for i in range(k):
    s.append([int(_) for _ in input().split()])
# print(s)
dp = [0 for i in range(n)]
dp[0] = 1
dp_s = [0 for i in range(n+1)]
dp_s[1] = 1
# print(dp)
# print(dp_s)
# print('*****************')
for i in range(1, n):
    for j in range(len(s)):
        r, l = s[j]
        if i-r >= 0:
            if i-l >= 0:
                dp[i] += dp_s[i-r+1] - dp_s[i-l]
            else:
                dp[i] += dp_s[i-r+1] - dp_s[0]
    dp[i] = dp[i] % 998244353
    # print(dp)
    dp_s[i+1] += dp_s[i] + dp[i]
    dp_s[i+1] = dp_s[i+1] % 998244353
    # print(dp_s)
    # print('*****************')
print(dp[-1])

Submission status: Accepted

Solution code:
MOD = 998244353


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )


def solve(N, region):
    dp = [ModInt(0)]*(N+1)
    dp[1] += 1
    dpsum = [ModInt(0)]*(N+1)
    dpsum[1] += 1

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

    return dp[N]


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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]
 
# dpの高速化 => 累積和によって、O(N)で解く
dp = [0] * N
acc = [0]* (N+1)
dp[0], acc[1] = 1, 1
# acc[0] = 0
# acc[1] = dp[0]
# acc[2] = dp[0] + dp[1]
# acc[n] = dp[0] + dp[1] + dp[n-1]

# dp[0] = acc[1] - acc[0]
# dp[1] = acc[2] - acc[1]
# dp[n-1] = acc[n] - acc[n-1]
mod = 998244353
 
for i in range(1, N):
  # acc[i] = dp[0] + ... + dp[i-1] が既知
  # 貰うdp
  for j in range(K):
    r = i - X[j][0]
    l = i - X[j][1]
    if r < 0: continue
    l = max(l, 0)
      
    dp[i] += acc[r+1] - acc[l] # s = dp[L] + ... + dp[R]
    dp[i] %= mod
  acc[i+1] = acc[i] + dp[i] # acc[i+1] = dp[0] + ... + dp[i]

print(dp[N-1])

Submission status: Accepted

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

for i in range(k):
    l,r=map(int,input().split())
    s+=[i for i in range(l,r+1)]
    s2.append([l,r])
s.sort()
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):
        if i-s2[j][0]>=0:
            dp[i]+=(dpsum[i-s2[j][0]]-dpsum[max(i-s2[j][1],1)-1])%mod
            dp[i]%=mod
    dpsum[i]=(dpsum[i-1]+dp[i])%mod
print(dp[n])

Submission status: Accepted

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

s=[0,1]
for i in range(1,n):
  t=0
  for j in range(k):
    t+=s[max(0,i-l[j][0]+1)]-s[max(0,i-l[j][1])]
  s.append((s[-1]+t)%mod)
print(t%mod)

Submission status: Accepted

Solution code:
def li():
    return [int(x) for x in input().split()]


MOD = 998244353
N, K = li()
L, R = [], []
for _ in range(K):
    l, r = li()
    L.append(l)
    R.append(r)

#dp[i]: マスiにいく場合の数

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

for i in range(1, N):
    dp[i+1] += dp[i]
    dp[i+1] %= MOD
    for k in range(K):
        l, r = L[k], R[k]
        dp[i+l] += dp[i]
        dp[i+l] %= MOD
        dp[i+r+1] -= dp[i]
        dp[i+r+1] %= MOD

print(dp[N])

Submission status: Accepted

Solution code:
# DP, 累積和
n, k = list(map(int, input().split()))
s = list()
for i in range(k):
     l, r = list(map(int, input().split()))
     s.append((l, r))

mod = 998244353
i = 1
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 s:
        li = i-r
        ri = i-l
        if ri < 1: continue
        li = max(li, 1)
        dp[i] = (dp[i] + dpsum[ri] - dpsum[li-1]) % mod
    dpsum[i] = (dpsum[i-1] + dp[i]) % mod
    
print(dp[n])

Submission status: Accepted

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

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

dp = [0]*n
dp[0] = 1
a = [0]*(n+1)
a[1] = dp[0]
for i in range(1, n):
    for j in range(k):
        r = i - d[0][j]
        l = i - d[1][j]
        if l < 1:
            l = 1
        if r < 0:
            continue
        dp[i] += a[r] - a[l-1]
        dp[i] %= 998244353
    a[i+1] = (a[i] + dp[i]) % 998244353
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)]
dp = [0] * (n + 1)
dp_sum = [0] * (n + 1)
dp[1] = 1
dp_sum[1] = 1
for i in range(2, n + 1):
    for j in range(k):
        li = max(1, i - lr[j][1])
        ri = i - lr[j][0]
        if ri < 0:
            continue
        dp[i] += dp_sum[ri] - dp_sum[li - 1]
        dp[i] %= mod
    dp_sum[i] = dp_sum[i - 1] + dp[i]
    dp_sum[i] %= mod
print(dp[n])

Submission status: Accepted

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

MOD = 998244353

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

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


for i in range(2, N+1):
    for j in range(len(L_list)):
        if i - R_list[j]-1 < 0:
            R_pos = 0
        else:
            R_pos = i - R_list[j] - 1
        dp[i] += (sdp[i - L_list[j]] - sdp[R_pos])%MOD
        dp[i] %= MOD
    sdp[i] = sdp[i-1] + dp[i]
    sdp[i] %= MOD
    #print(dp)
    #print("s", sdp)
print(dp[N])

Submission status: Accepted

Solution code:
MOD = 998244353
n, k = map(int, input().split())
l, r = [0]*k, [0]*k
for i in range(k):
    _l, _r = map(int, input().split())
    l[i], r[i] = _l, _r
dp, dpsum = [0]*(n+1), [0]*(n+1)
dp[1], dpsum[1] = 1, 1
for i in range(2, n+1):
    for j in range(k):
        li = i - r[j]
        ri = i - l[j]
        if ri<0: continue
        li = max(li, 1)
        dp[i] += dpsum[ri] - dpsum[li-1]
        dp[i] %= MOD
    dpsum[i] = dpsum[i-1] + dp[i]
print(dp[n])

Submission status: Accepted

Solution code:
MOD = 998244353


def solve(lr, dp, n):
    acc_dp = [1] * n
    for i in range(1, n):
        val = 0
        for d in lr:
            a = i - d[0]
            if a < 0:
                continue
            b = i - d[1] - 1
            val += acc_dp[a] - (acc_dp[b] if b >= 0 else 0)
        dp[i] = val % MOD
        acc_dp[i] = (acc_dp[i - 1] + dp[i]) % MOD
    return dp[n - 1]


def main():
    f = open(0)
    n, k = [int(x) for x in f.readline().split()]
    lr = [[int(x) for x in f.readline().split()] for _ in range(k)]
    dp = [0] * n
    dp[0] = 1
    ans = solve(lr, dp, n)
    print(ans)

main()

Submission status: Accepted

Solution code:
def resolve():
  base = 998244353
  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)
  dp_sum = [0] * (N+1)
  dp[1] = 1
  dp_sum[1] = 1

  for i in range(2, N+1):
    for lr in LRs:
      left = max(i - lr[1] - 1, 0)
      right = max(i - lr[0], 0)
      dp[i] += dp_sum[right] - dp_sum[left]
      if dp[i] >= base:
        dp[i] %= base
      dp_sum[i] = dp_sum[i-1] + dp[i]
  print(dp[-1])

if __name__ == "__main__":
  resolve()

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
from numba.types import i8
ni8 = np.int64
MOD = 998244353


@njit((i8[:,::-1], i8[:], i8, i8), cache=True)
def solve(lr, dp, n, k):
    acc_dp = np.ones_like(dp)
    for i in range(1, n):
        val = 0
        for j in range(k):
            a = i - lr[j, 0]
            if a < 0:
                continue
            b = i - lr[j, 1] - 1
            val += acc_dp[a] - (acc_dp[b] if b >= 0 else 0)
        dp[i] = val % MOD
        acc_dp[i] = (acc_dp[i - 1] + dp[i]) % MOD
    return dp[n - 1]


def main():
    f = open(0)
    n, k = [int(x) for x in f.readline().split()]
    lr = np.fromstring(f.read(), ni8, sep=' ').reshape((-1, 2))
    dp = np.zeros(n, ni8)
    dp[0] = 1
    ans = solve(lr, dp, n, k)
    print(ans)

main()

Submission status: Accepted

Solution code:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
import random
J=998244353
########################################################
n,k=INPUT()
A=[]
for i in range(k):
    x,y=INPUT()
    A.append([x,y])
A.sort()
s,e=-1,-1
S=[]
for i in range(len(A)):
    if i==0:
        S.append([A[i][0],A[i][1]])
    else:
        if A[i][0]>S[-1][1]:
            S.append([A[i][0],A[i][1]])
        else:
            S[-1][1]=A[i][1]
cum=[0]*(n+1)
dp=[0]*(n+1)
dp[1]=1
cum[1]=1
for i in range(2,n+1):
    for ele in S:
        x=ele[0]
        y=ele[1]
        dp[i]=(dp[i]+cum[max(i-x,0)]-cum[max(0,i-y-1)])%J
    cum[i]=(cum[i-1]+dp[i])%J
print(dp[n])

Submission status: Accepted

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

def diff(l):
    tmp = None
    res = []
    for elm in l:
        if tmp is None:
            res.append(elm)
            tmp = elm
        else:
            res.append(elm-tmp)
            tmp = elm

    return res

res_diff = [0] * N
res_diff[1] = -1
res = [1]

for i in range(N-1):
    for l, r in LRs:
        if i+l < N:
            res_diff[i+l] += res[i]
        if i+r+1 < N:
            res_diff[i+r+1] -= res[i]
    
    res_next = (res[-1]+res_diff[i+1])%mod
    res.append(res_next)

print(res[N-1])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
L = []
R = []

mod = 998244353

for i in range(K):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r + 1)

diff = [0] + [1] + [-1] + [0] * (10 ** 5 * 5)
ans = [0] * (10 ** 5 * 5)

for i in range(1, N + 1):
    ans[i] = ans[i-1] + diff[i]
    ans[i] %= mod
    for j in range(K):
        diff[i + L[j]] += ans[i]
        diff[i + R[j]] -= ans[i]
        diff[i + L[j]] %= mod
        diff[i + R[j]] %= mod

print(ans[N])

Submission status: Accepted

Solution code:
#Convolution_998244353

MOD = 998244353
ROOT = 3

sum_e = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 0, 0, 0, 0, 0, 0, 0, 0, 0)
sum_ie = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 0, 0, 0, 0, 0, 0, 0, 0, 0)

def butterfly(arr):
    n = len(arr)
    h = (n - 1).bit_length()
    for ph in range(1, h + 1):
        w = 1 << (ph - 1)
        p = 1 << (h - ph)
        now = 1
        for s in range(w):
            offset = s << (h - ph + 1)
            for i in range(p):
                l = arr[i + offset]
                r = arr[i + offset + p] * now
                arr[i + offset] = (l + r) % MOD
                arr[i + offset + p] = (l - r) % MOD
            now *= sum_e[(~s & -~s).bit_length() - 1]
            now %= MOD

def butterfly_inv(arr):
    n = len(arr)
    h = (n - 1).bit_length()
    for ph in range(1, h + 1)[::-1]:
        w = 1 << (ph - 1)
        p = 1 << (h - ph)
        inow = 1
        for s in range(w):
            offset = s << (h - ph + 1)
            for i in range(p):
                l = arr[i + offset]
                r = arr[i + offset + p]
                arr[i + offset] = (l + r) % MOD
                arr[i + offset + p] = (MOD + l - r) * inow % MOD
            inow *= sum_ie[(~s & -~s).bit_length() - 1]
            inow %= MOD

def convolution(a, b):
    n = len(a)
    m = len(b)
    if not n or not m: return []
    if min(n, m) <= 100:
        if n < m:
            n, m = m, n
            a, b = b, a
        res = [0] * (n + m - 1)
        for i in range(n):
            for j in range(m):
                res[i + j] += a[i] * b[j]
                res[i + j] %= MOD
        return res
    z = 1 << (n + m - 2).bit_length()
    a += [0] * (z - n)
    b += [0] * (z - m)
    butterfly(a)
    butterfly(b)
    for i in range(z):
        a[i] *= b[i]
        a[i] %= MOD
    butterfly_inv(a)
    a = a[:n + m - 1]
    iz = pow(z, MOD - 2, MOD)
    for i in range(n + m - 1):
        a[i] *= iz
        a[i] %= MOD
    return a

def autocorrelation(a):
    n = len(a)
    if not n: return []
    if n <= 100:
        res = [0] * (2 * n - 1)
        for i in range(n):
            for j in range(n):
                res[i + j] += a[i] * a[j]
                res[i + j] %= MOD
        return res
    z = 1 << (2 * n - 2).bit_length()
    a += [0] * (z - n)
    butterfly(a)
    for i in range(z):
        a[i] *= a[i]
        a[i] %= MOD
    butterfly_inv(a)
    a = a[:2 * n - 1]
    iz = pow(z, MOD - 2, MOD)
    for i in range(2 * n - 1):
        a[i] *= iz
        a[i] %= MOD
    return a

def resize(a, m):
    n = len(a)
    if n == m: return a
    if n > m: return a[:m]
    else: return a + [0] * (m - n)

def add(a, b):
    return [(va + vb) % MOD for va, vb in zip(a, b)]

def sub(a, b):
    return [(va - vb) % MOD for va, vb in zip(a, b)]

def times(a, k):
    return [v * k % MOD for v in a]

def multiply(a, b):
    return convolution(a.copy(), b.copy())

def square(a):
    return autocorrelation(a.copy())

def inverse(a):
    n = len(a)
    r = pow(a[0], MOD - 2, MOD)
    m = 1
    tmp = [r]
    while m < n:
        tmp += [0] * m
        m *= 2
        tmp = sub(times(tmp, 2), multiply(a[:m], square(tmp.copy())[:m]))
    res = tmp[:n]
    return res

def divide(a, b):
    return multiply(a, inverse(b))

def differentiate(a):
    n = len(a)
    res = [0] * n
    for i in range(1, n):
        res[i - 1] = a[i] * i % MOD
    return res

def integrate(a):
    n = len(a)
    res = [0] * n
    for i in range(n - 1):
        res[i + 1] = a[i] * pow(i + 1, MOD - 2, MOD) % MOD
    return res

def log(a):
    assert a[0] == 1
    n = len(a)
    return integrate(divide(differentiate(a), a)[:n])

def exp(a):
    assert a[0] == 0
    n = len(a)
    res = [1]
    g = [1]
    q = differentiate(a)
    m = 1
    while m < n:
        g = sub(times(g, 2), multiply(res, square(g)[:m]))
        g += [0] * m
        res += [0] * m
        m *= 2
        w = add(q[:m], multiply(g, sub(differentiate(res), multiply(res, q[:m])[:m]))[:m])
        res = add(res, multiply(res, sub(a[:m], integrate(w)))[:m])
    return res[:n]

def power(a, k):
    n = len(a)
    for d, p in enumerate(a):
        if p != 0: break
    else: return [0] * n
    res = [0] * n
    g = a[d:] + [0] * d
    g = exp(times(log(times(g, pow(p, MOD - 2, MOD))), k))
    for i in range(max(n - d * k, 0)):
        res[d * k + i] = g[i]
    res = times(res, pow(p, k, MOD))
    return res

def tonelli_shanks(n, p): #n < p
    if n == 0: return 0
    if n == 1: return 1
    if pow(n, (p - 1) // 2, p) != 1: return -1
    q, s = p - 1, 0
    while q % 2 == 0:
        q //= 2
        s += 1
    z = 1
    while pow(z, (p - 1) // 2, p) != p - 1:
        z += 1
    m, c, t, r = s, pow(z, q, p), pow(n, q, p), pow(n, (q + 1) // 2, p)
    while t != 1:
        k = 1
        while pow(t, 2**k, p) != 1:
            k += 1
        x = pow(c, pow(2, m - k - 1, p - 1), p)
        m = k
        c = (x * x) % p
        t = (t * c) % p
        r = (r * x) % p
    if r * r % p != n: return -1
    return r

def sqrt_(a):
    assert a[0] != 0
    n = len(a)
    s = tonelli_shanks(a[0], MOD)
    if s == -1: return
    m = 1
    res = [s]
    minv2 = pow(2, MOD - 2, MOD)
    while m < n:
        res += [0] * m
        m *= 2
        res = times(add(res, divide(a[:m], res)), minv2)
    return res[:n]

def sqrt(a):
    n = len(a)
    for d, p in enumerate(a):
        if p != 0: break
    else: return [0] * n
    if d % 2 == 1: return
    s = tonelli_shanks(p, MOD)
    if s == -1: return
    res = [0] * n
    g = a[d:] + [0] * d
    g = sqrt_(times(g, pow(p, MOD - 2, MOD)))
    if g is None: return
    g = times(g, s)
    for i in range(n - d + 1):
        if d // 2 + i >= n: break
        res[d // 2 + i] = g[i]
    return res

def build_exp(n, b):
    res = [0] * (n + 1)
    res[0] = 1
    for i in range(n):
        res[i + 1] = res[i] * b % MOD
    return res

def build_factorial(n):
    fct = [0] * (n + 1)
    inv = [0] * (n + 1)
    fct[0] = inv[0] = 1
    for i in range(n):
        fct[i + 1] = fct[i] * (i + 1) % MOD
    inv[n] = pow(fct[n], MOD - 2, MOD)
    for i in range(n)[::-1]:
        inv[i] = inv[i + 1] * (i + 1) % MOD
    return fct, inv

def taylor_shift(a, c):
    n = len(a)
    fct, inv = build_factorial(n)
    d = build_exp(n, c)
    p = [0] * (2 * n - 1)
    for i in range(n):
        p[i + n - 1] = a[i] * fct[i] % MOD
    q = [0] * (2 * n - 1)
    for i in range(n):
        q[n - 1 - i] = d[i] * inv[i] % MOD
    r = multiply(p, q)
    res = [0] * n
    for i in range(n):
        res[i] = r[2 * n - 2 + i] * inv[i] % MOD
    return res

def bernoulli(n):
    fct, inv = build_factorial(n + 1)
    e = [0] * n
    e[0] = 1
    expx = [inv[i + 1] for i in range(n)]
    res = [v * fct[i] % MOD for i, v in enumerate(divide(e, expx)[:n])]
    return res

def partition(n):
    res = [0] * n
    for i in range(-n, n + 1):
        k = i * (3 * i - 1) // 2
        if k >= n: continue
        if i % 2 == 0: res[k] = 1
        else: res[k] = MOD - 1
    return inverse(res)

def stirling_first(n):
    res = [1]
    t = 0
    for i in range((n).bit_length())[::-1]:
        a = n >> i
        res = multiply(res, taylor_shift(res, -t))
        t *= 2
        if a & 1:
            res = multiply(res, [-t, 1])
            t += 1
    return res

def stirling_second(n):
    fct, inv = build_factorial(n + 1)
    a = [0] * (n + 1)
    b = [0] * (n + 1)
    for i in range(n + 1):
        a[i] = pow(i, N, MOD) * inv[i] % MOD
        b[i] = inv[i] * (1 - (i & 1) * 2)
    res = multiply(a, b)[:n + 1]
    return res

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
F = [0] * (N + 1)

for _ in range(K):
    l, r = map(int, input().split())
    for i in range(l, r + 1):
        F[i] = 1

I = [1] + [0] * N

print(inverse(sub(I, F))[N - 1])