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:
from operator import add


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

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

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

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

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

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

Submission status: Accepted

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

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

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

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

now = 0

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
input=sys.stdin.readline

mod=998244353

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

Submission status: Accepted

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

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

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

for i in range(1, n):
    for l, r in lr:
        if 0 <= i-r and i-l < i:
            dp[i] += acc[i-l]-acc[i-r-1]
        elif i-r < 0 and i-l < i:
            dp[i] += acc[i-l]
        elif i-r < 0 and i <= i-l:
            dp[i] += acc[i-1]
        elif 0 < i-r and i <= i-l:
            dp[i] += acc[i-1]-acc[i-r-1]
    acc[i] = acc[i-1]+dp[i]%mod

print(dp[-1]%mod)

Submission status: Accepted

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

dp = [0] * (N+1)
dp[1] = 1
s = 0
for i in range(1, N):
    s += dp[i]
    for j in range(K):
        if (i + lr[j][0]) <= N:
            dp[i + lr[j][0]] = (dp[i + lr[j][0]] + s) % mod
        if (i + lr[j][1]) <= N:
            dp[i + lr[j][1]] = (dp[i + lr[j][1]] - s) % mod
        

print(dp[N])

Submission status: Accepted

Solution code:
N,k=map(int,input().split())
L=[0 for i in range(2)]

K=[]
for i in range(k):
    l,r=map(int,input().split())
    K.append([l,r])
mod=998244353
L[1]=1
R=[0,1]
for i in range(2,N+1):
    cnt=0
    for l,r in K:
        cnt+=R[max(0,i-l)]
        cnt-=R[max(0,i-(r+1))]
    cnt%=mod
    L.append(cnt)
    R.append(R[-1]+cnt)
print(L[-1]%mod)
#print(R)

Submission status: Accepted

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

Submission status: Accepted

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

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):
    for l, r in lr:
        if i - l >= 0:
            acc += dp[i - l]
            acc %= mod
        if i - r - 1 >= 0:
            acc -= dp[i - r - 1]
            acc %= mod
        dp[i] = acc

print(dp[-1])

Submission status: Accepted

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

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

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

for i in range(1,n):
    for l,r in kukan:
        l = i - l
        r = i - r
        l,r = r,l
        if r < 0:
            continue
        elif l >= 0:
            dp[i] += (ruiseki[r] - ruiseki[l])%mod
        else:
            dp[i] += (ruiseki[r])%mod
    ruiseki[i+1] = (ruiseki[i] + dp[i])

print(dp[-1]%mod)

Submission status: Accepted

Solution code:
def readinput():
    n,k=map(int,input().split())
    lr=[]
    for _ in range(k):
        l,r=map(int,input().split())
        lr.append((l,r))
    return n,k,lr

def main(n,k,lr):
    lrs=sorted(lr,key=lambda x:x[0])
    MOD=998244353
    dp=[0]*(n+1)
    dp[1]=1
    for i in range(1,n):
        #print(i)
        if dp[i]==0:
            continue
        skip=False
        for l,r in lrs:
            for j in range(l,r+1):
                #print('i+j: {}'.format(i+j))
                if i+j>n:
                    skip=True
                    break
                dp[i+j]=(dp[i+j]+dp[i])%MOD
                #print(dp)
            if skip:
                break
    return dp[n]

def main2(n,k,lr):
    lrs=sorted(lr,key=lambda x:x[0])
    MOD=998244353
    dp=[0]*(n+1)
    ruiseki=[0]*(n+1)
    dp[1]=1
    ruiseki[1]=1
    for i in range(2,n+1):
        for l,r in lrs:
            if i-l<1:
                break
            dp[i]+=ruiseki[i-l]-ruiseki[max(1,i-r)-1]
        dp[i]=dp[i]%MOD
        ruiseki[i]=(ruiseki[i-1]+dp[i])%MOD
    return dp[n]

if __name__=='__main__':
    n,k,lr=readinput()
    ans=main2(n,k,lr)
    print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

mod = 998244353

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

lr = [list(map(int, input().split())) for _ in range(k)]
lr.sort()

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

for i in range(n - 1):
    for l, r in lr:
        if i + l < n:
            a[i + l] += f[i]
            a[i + l] %= mod
        else:
            break
        if i + r + 1 < n:
            a[i + r + 1] -= f[i]
            a[i + r + 1] %= mod
        else:
            break
    f.append((f[i] + a[i + 1]) % mod)
print(f[n - 1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap

MOD = 998244353

class ModInt:
    def __init__(self, x=0):
        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)) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2))
        )

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

    __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)) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2))
        )

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

@mt
def slv(N, K, LR):

    memo = [ModInt(0)] * (N+2)
    memo[1] = 1
    memo[1+1] = -1
    for i in range(1, N+1):
        memo[i] += memo[i-1]
        for l, r in LR:
            ll = min(N+1, i+l)
            rr = min(N+1, i+r+1)
            memo[ll] += memo[i]
            memo[rr] -= memo[i]

    return memo[N]


def main():
    N, K = read_int_n()
    LR = [read_int_n() for _ in range(K)]
    print(slv(N, K, LR))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

dp = [0]*(n+1)
dpsum = [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
        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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class ModInt:
    def __init__(self, x=0, M=10**9+7):
        self.m = M
        self.x = x % self.m

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

    __repr__ = __str__

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

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

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

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

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

    __radd__ = __add__

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

    __rmul__ = __mul__

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

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


@mt
def slv(N, K, LR):
    M = 998244353
    memo = [ModInt(0, M)] * (N+2)
    memo[1] = 1
    memo[1+1] = -1
    for i in range(1, N+1):
        memo[i] += memo[i-1]
        for l, r in LR:
            ll = min(N+1, i+l)
            rr = min(N+1, i+r+1)
            memo[ll] += memo[i]
            memo[rr] -= memo[i]

    return memo[N]


def main():
    N, K = read_int_n()
    LR = [read_int_n() for _ in range(K)]
    print(slv(N, K, LR))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():

    mod = 998244353
    n, k = LI()
    l = [0 for _ in range(k)]
    r = [0 for _ in range(k)]

    for i in range(k):
        l[i], r[i] = LI()

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

    for i in range(2,n+1):
        for el, er in zip(l, r):
            dp[i] += dpsum[max(i-el, 0)] - dpsum[max(i-er-1, 0)]
        dp[i] %= mod
        dpsum[i] = (dpsum[i-1] + dp[i])%mod

    print(dp[n])

main()

Submission status: Accepted

Solution code:
mod=998244353
w=[]
dp=[0]*200005
ds=[0]*200005
dp[1]=1
ds[1]=1
n,k=map(int,input().split())
for i in range(k):
    a,b=map(int,input().split())
    w.append((a,b))

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

print(dp[n])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class LazySegmentTree():
    def __init__(self, op, e, mapping, composition, im, init_array):
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.im = im

        l = len(init_array)

        def ceil_pow2(n):
            x = 0
            while (1 << x) < n:
                x += 1
            return x
        self.log = ceil_pow2(l)
        self.size = 1 << self.log
        self.d = [e() for _ in range(2*self.size)]
        self.lz = [im() for _ in range(self.size)]

        for i, a in enumerate(init_array):
            self.d[i+self.size] = a

        for i in range(self.size-1, 0, -1):
            self.__update(i)

    def set(self, p, x):
        p += self.size

        for i in range(self.log, 0, -1):
            self.__push(p >> i)

        self.d[p] = x

        for i in range(1, self.log+1):
            self.__update(p >> i)

    def __getitem__(self, p):
        p += self.size
        for i in range(self.log, 0, -1):
            self.__push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        if l == r:
            return self.e()

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push(r >> i)

        sml = self.e()
        smr = self.e()

        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1

        return self.op(sml, smr)

    def apply(self, l, r, f):
        if l == r:
            return

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push((r-1) >> i)

        l2, r2 = l, r
        while l < r:
            if l & 1:
                self.__all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.__all_apply(r, f)
            l >>= 1
            r >>= 1
        l, r = l2, r2

        for i in range(1, self.log+1):
            if ((l >> i) << i) != l:
                self.__update(l >> i)
            if ((r >> i) << i) != r:
                self.__update((r-1) >> i)

    def __update(self, k):
        self.d[k] = self.op(self.d[2*k], self.d[2*k+1])

    def __all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def __push(self, k):
        self.__all_apply(2*k, self.lz[k])
        self.__all_apply(2*k+1, self.lz[k])
        self.lz[k] = self.im()


M = 998244353

def e():
    return 0

def op(sl, sr):
    return (sl + sr) % M

def mapping(fl, sr):
    return (fl + sr) % M

def composition(fl, fr):
    return (fl + fr) % M

def im():
    return 0

@mt
def slv(N, K, LR):
    memo = LazySegmentTree(op, e, mapping, composition, im, [0]*(N+1))
    memo.apply(1, 1+1, 1)
    for i in range(1, N+1):
        n = memo[i]
        for l, r in LR:
            ll = min(N+1, i+l)
            rr = min(N+1, i+r+1)
            memo.apply(ll, rr, n)

    return memo[N]


def main():
    N, K = read_int_n()
    LR = [read_int_n() for _ in range(K)]
    print(slv(N, K, LR))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = [tuple(map(int,input().split())) for _ in range(K)]
MOD=998244353
dp=[0]*N
dp[0]=1
for i in range(N-1):
    x = dp[i]
    dp[0]=0
    for k in range(K):
        l,r = S[k]
        if i+l < N:
            dp[i+l]+=x
            dp[i+l]%=MOD
        if i+r+1 < N:
            dp[i+r+1]-=x
            dp[i+r+1]%=MOD
    dp[i+1]+=dp[i]
    dp[i+1]%=MOD
print(dp[-1]%MOD)

Submission status: Accepted

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

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=998244353
    N,K=MI()
    
    dp=[0]*N
    dp[0]=1
    
    L=[0]*K
    R=[0]*K
    for i in range(K):
        L[i],R[i]=MI()
    
    
    for i in range(N-1):
        for k in range(K):
            l= i + L[k]
            r= i + R[k] +1
            if l<N:
                dp[l]+=dp[i]
                dp[l]%=mod
            if r<N:
                dp[r]-=dp[i]
                dp[r]%=mod
        if i!=0:
            dp[i+1]+=dp[i]
        dp[i+1]%=mod
        
                
    print(dp[-1])
            
            

main()

Submission status: Accepted

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

for i in range(1, n + 1):
    s += dp[i]
    for l, r in LR:
        if i + l <= n:
            dp[i + l] = (dp[i + l] + s) % mod
            if i + r + 1 <= n:
                dp[i + r + 1] = (dp[i + r + 1] - s) % mod

print(dp[n])

Submission status: Accepted

Solution code:
def resolve():
    mod=998244353
    n,k=map(int,input().split())
    d=[[],[]]
    for _ in range(k):
        l,r=map(int,input().split())
        d[0].append(l)
        d[1].append(r)
    dp=[0]*(n+1)
    a=[0]*(n+2)
    a[1]=dp[1]=1
    for i in range(2,n+1):
        for j in range(k):
            if i-d[0][j]>0:
                dp[i]=(dp[i]+a[i-d[0][j]]-a[max(i-d[1][j]-1,0)]+mod)%mod
        #print(dp[i])
        a[i]=(a[i-1]+dp[i])%mod
    print(dp[n])
resolve()

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
L = [0]*N
R = [0]*N
DP = [0]*(N+10)
DP[0] = 1
SDP = [0]*(N+10)
SDP[1] = 1
MOD=998244353
for i in range(K):
    L[i],R[i] = map(int, input().split())

for i in range(1,N):
    for j in range(K):
        l = max(0,i-R[j])
        r = max(0,i-L[j]+1)
        DP[i] += SDP[r] - SDP[l]
    SDP[i+1] = (SDP[i] + DP[i])%MOD
print(DP[N-1]%MOD)

Submission status: Accepted

Solution code:
def resolve():
    MOD = 998244353
    N, K = map(int, input().split())
    S = [tuple(map(int, input().split())) for _ in range(K)]
    L = [0] * K
    R = [0] * K
    L, R = zip(*S)

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

    dp_acum = [0] * (N + 1)
    dp_acum[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] += dp_acum[ri] - dp_acum[li - 1]
            dp[i] %= MOD

        dp_acum[i] = dp_acum[i - 1] + dp[i]
        dp_acum[i] %= MOD

    print(dp[N])


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
mod = 998244353
n,k =map(int,input().split())
step =[0]*(n+1)
# step[0]=1
step[1]=1
stepsum=[0]*(n+1)
stepsum[1]=1
l=[0]*k
r=[0]*k
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 = i - r[j]
        ri = i - l[j]
        if ri <= 0:
            continue
        # li = max(1,li)
        step[i] += stepsum[ri] - stepsum[max(0,li-1)]
        # step[i] %= mod
        # print(step)
    stepsum[i] = ( stepsum[i-1] + step[i] )%mod


print(step[n]%mod)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
ll=[list(map(int,input().split())) for _ in range(k)]
dp=[0]*(3*n)
dp[0]=1
dp[1]=-1
for i in range(n):
    for l,r in ll:
        dp[l+i]+=dp[i]
        dp[i+r+1]-=dp[i]
    dp[i+1]=(dp[i]+dp[i+1])%998244353
print(dp[n-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, LR):
    M = 998244353
    memo = [0] *(N+2)
    memo[1] = 1
    memo[1+1] = -1
    for i in range(1, N+1):
        memo[i] += memo[i-1]
        memo[i] %= M
        for l, r in LR:
            ll = min(N+1, i+l)
            rr = min(N+1, i+r+1)
            memo[ll] += memo[i]
            memo[ll] %= M
            memo[rr] -= memo[i]
            memo[rr] %= M

    return memo[N]


def main():
    N, K = read_int_n()
    LR = [read_int_n() for _ in range(K)]
    print(slv(N, K, LR))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def input_int_array():
    return map(int, input().split())


MOD = 998244353


def answer():
    n, k = input_int_array()
    spans = [tuple(input_int_array()) for x in range(k)]

    count = [0] * (n)
    count[0] = 1
    accum = [0] * (n + 1)
    accum[1] = 1

    for i in range(1, n):
        j = i + 1
        for l, r in spans:
            start = max(0, j - r - 1)
            end = max(0, j - l)
            count[i] += accum[end] - accum[start]
        accum[j] = accum[j-1] + count[i] % MOD
    print(count[n-1] % MOD)


answer()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import Counter
import bisect
from collections import defaultdict
import itertools
def main():
    mod = 998244353
    N, K = MI()
    sec = []
    for i in range(K):
        l, r = MI()
        sec.append((l, r))
    dp = [0 for _ in range(N + 1)]
    dpsum = [0 for _ in range(N + 1)]
    dp[0] = 1
    dpsum[0] = 1
    for i in range(1, N):
        for j in range(K):
            li = i - sec[j][1]
            ri = i - sec[j][0]
            if ri < 0:
                continue
            li = max(li, 0)
            dp[i] += (dpsum[ri] - dpsum[li - 1]) % mod
            dp[i] %= mod
        dpsum[i] = (dpsum[i - 1] + dp[i]) % mod
    print(dp[N - 1])
if __name__ == "__main__":
    main()

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)
dp[1] = 1
sm = 0
for i in range(2, n + 1):
    for l, r in lr:
        if i - r - 1 >= 1:
            sm -= dp[i-r-1]
        if i - l >= 1:
            sm += dp[i-l]

        sm %= mod

    dp[i] = sm

ans = dp[n]
print(ans)