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:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
lr = []
for _ in range(k):
    l, r = LI()
    lr.append([l, r+1])
dp = [0] * (n+1)
dp[1] = 1
for i in range(1, n):
    dp[i+1] += dp[i]
    dp[i+1] %= mod
    for l, r in lr:
        dp[i+1] += dp[i+1-l] - dp[max(0, i+1-r)]
        dp[i+1] %= mod
print((dp[-1] - dp[-2]) % mod)

Submission status: Accepted

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

dp = [0]*N
dp[0] = 1
if N > 2:
    dp[1] = -1
for i in range(N):
    if N > 2:
        dp[i] += dp[i-1]
    dp[i] %= mod
    for s in S:
        if s[0]+i < N:
            dp[s[0]+i] += dp[i]
            dp[s[0]+i] %= mod
        if s[1]+i+1 < N:
            dp[s[1]+i+1] -= dp[i]
            dp[s[1]+i+1] %= mod
print(dp[-1])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
arr=[]
for _ in range(k):
	arr.append(list(map(int,input().split())))
pref=[0]*(n+1)
dp=[0]*(n+1)
dp[0]=1
pref[0]=1
for i in range(1,n):
	for j in range(k):
		if(arr[j][1]<=i):
			dp[i]=(dp[i]+pref[i-arr[j][0]]-pref[i-arr[j][1]-1])%998244353
		elif(arr[j][0]<=i):
			dp[i]=(dp[i]+pref[i-arr[j][0]])%998244353
	pref[i]=(pref[i-1]+dp[i])%998244353
print(dp[n-1])

Submission status: Accepted

Solution code:
"""
imos方を使えばよさそう
imos[i][0] => iマス目に到達する場合の数
imos[i][1] => imosの累積
imos[i+l][1] += imos[i]
imos[i+r+1][1] -= imos[i]
"""
mod = 998244353
N,K = map(int,input().split())
LR = [list(map(int,input().split())) for _ in range(K)]

imos = [[0]*2 for _ in range(N)]
imos[0][0] = 1

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

Submission status: Accepted

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

for i in range(n):
    if i != 0:
        dp[i] += dp[i-1]
        dp[i] %= mod
    if dp[i] == 0:
        continue
    for L , R in s:
        if i + L < n:
            dp[i+L] += dp[i]
            dp[i+L] %= mod
            if i + R + 1 < n:
                dp[i+R+1] -= dp[i]
print(dp[-1]%mod)

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 998244353; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

def inverse(N, mod):
	return (pow(N, mod - 2, mod))

def main():
	N, K = getlist()
	DP = [0] * (2 * N + 1)
	DP2 = [0] * (2 * N + 1)
	DP[0] = 1
	LR = []
	for i in range(K):
		L, R = getlist()
		LR.append([L, R])

	for i in range(N):
		DP[i] += DP2[i]
		DP[i] %= mod
		for l, r in LR:
			DP2[i + l] += DP[i]
			DP2[i + l] %= mod
			DP2[i + r + 1] -= DP[i]
			DP2[i + r + 1] %= mod
		DP2[i + 1] += DP2[i]
		DP2[i + 1] %= mod

	ans = DP[N - 1]
	print(ans % mod)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n,k=[int(c) for c in input().split()]
MOD = 998244353
segs = []
for _ in range(k):
    a,b=[int(c) for c in input().split()]
    segs.append((a,b))


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

for i in range(n):
    # dp[i] = dp[i] + dp[i-1]
    if dp[i] < 0:
        dp[i]+=MOD
    for a,b in segs:
        if i+a <=n:
            dp[i+a]+=dp[i]
        if i+b+1 <= n:
            dp[i+b+1]-=dp[i]
    dp[i]%=MOD
    if i !=0:
        dp[i+1] = dp[i+1]+dp[i]

print(dp[n-1]%MOD)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,k,*data = list(map(int,read().split()))
mod = 998244353

dp = [0] * n
dp[0] = 1
route = 0
for j in range(1,n):
    for i in range(k):
        l,r = data[i*2:i*2+2]
        if(j >= l):
            route += dp[j-l]
        if(j > r):
            route -= dp[j-r-1]
        route %= mod
    dp[j] += route


print(dp[-1])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
T = []
mod = 998244353
for i in range(K):
    L, R = map(int, input().split())
    T.append([L, R])
dp = [0]*(N+1)
dp[1] = 1
Total = [0]*(N+1)
Total[1] = 1
for i in range(2, N+1):
    for j in range(K):
        L, R = T[j]
        dp[i] += Total[max(0, i-L)] - Total[max(0, i-R-1)]
    dp[i] %= mod
    Total[i] = Total[i-1] + dp[i]
    Total[i] %= mod
print(dp[N])

Submission status: Accepted

Solution code:
mod=998244353
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
lr=[]
for i in range(k):
	l,r=map(int,input().split())
	lr.append((l,r))
lr.sort()

cnt=[0]*n
cnt[0]=1
dp=[0]*n
for i in range(n-1):
	cnt[i]+=dp[i]
	for x,y in lr:
		if i+x<n:
			dp[i+x]+=cnt[i]
			dp[i+x]%=mod
		if i+y<n-1:
			dp[i+y+1]-=cnt[i]
			dp[i+y+1]%=mod
	dp[i]%=mod
	cnt[i]%=mod
	dp[i+1]+=dp[i]
print((cnt[-1]+dp[-1])%mod)

Submission status: Accepted

Solution code:
def pointUpdate(BIT,index,val):
    mod = 998244353
    while index < len(BIT):
        BIT[index] += val
        BIT[index] %= mod
        index += index&-index

def pointQuery(BIT,index):
    mod = 998244353
    total = 0
    while index > 0:
        total += BIT[index]
        index -= index&-index
        total %= mod

    return total

def rangeUpdate(BIT,l,r,val):
    pointUpdate(BIT,l,val)
    pointUpdate(BIT,r+1,-val)

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

    segs.sort()

    mod = 998244353
    BIT = [0]*(n+1)
    BIT[1] = 1
    for cell in range(1,n+1):
        curr = pointQuery(BIT,cell)
        if cell == n:
            print(curr)
        for l,r in segs:
            left = min(cell+l,n+1)
            right = min(cell+r,n+1)
            rangeUpdate(BIT,left,right,curr)

main()

Submission status: Accepted

Solution code:
MOD = 998244353
inpl = lambda: tuple(map(int,input().split()))
N, K = inpl()
LR = [inpl() for _ in range(K)]
dp = [0]*N

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

Submission status: Accepted

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

class Binary_Indexed_Tree():
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

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

    def get(self, i):
        return self.sum_range(i, i)

    def sum(self, i):
        i += 1
        ret = 0
        while i:
            ret += self.data[i]
            i &= i-1
        return ret

    def sum_range(self, l, r):
        return self.sum(r)-self.sum(l-1)

BIT = Binary_Indexed_Tree(n)
BIT.add(0, 1)
for i in range(1,n):
    tmp = 0
    for l,r in lr:
        l = i-l
        r = max(i-r, 0)
        if l < 0:
            continue
        tmp += BIT.sum_range(r, l)
    tmp %= mod
    BIT.add(i, tmp)

ans = BIT.get(n-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
l=[list(map(int,input().split())) for i in range(k)]
mod=998244353
dp=[0]*n
dp[0]=1
dp2=[0,1]

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

Submission status: Accepted

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

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 998244353
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N,K = LI()
    a = [LI() for _ in range(K)]

    m = [0] * (N+1)
    s = 1

    for i in range(1,N):
        s = (s + m[i]) % MOD
        if s:
            for l,r in a:
                if i + l <= N:
                    m[i+l] = (m[i+l] + s) % MOD
                if i + r + 1 <= N:
                    m[i+r+1] = (m[i+r+1] - s) % MOD
    print(m[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

INF=998244353
dp=[0]*n
dp[0]=1
sum=[0]*(n+1)
sum[0]=0
sum[1]=1

for i in range(1,n):
    temp=0
    for j in range(k):
        l=i-segment[j][1]
        r=i-segment[j][0]
        if r<0:
            continue
        if l<0:
            l=0
        temp=(temp+(sum[r+1]-sum[l]))%INF
    dp[i]=temp
    sum[i+1]=(sum[i]+temp)%INF

print(dp[n-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
dp[0] = 1

newdp = 0

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

print(dp[-1])

Submission status: Accepted

Solution code:
import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# available on Google, not available on Codeforces
# import numpy as np
# import scipy

MOD = 998244353

def solve(k, grid):  # fix inputs here
    console("----- solving ------")
    console(grid)
    ways = [1]
    psum = [0,1]
    ps = 1

    for i in range(1,k):
        cur = 0
        for a,b in grid:
            if a > i:
                continue
            if b > i:
                b = i
            console(i-a+1,i-b,i)
            cur += psum[i-a+1] - psum[i-b]

        console()
        console(i, cur, ways, psum)
        console()
         
        ways.append(cur%MOD)
        ps += cur
        psum.append(ps%MOD)


    # return a string (i.e. not a list or matrix)
    return ways[-1]%MOD


def console(*args):  # the judge will not read these print statement
    # print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return

# fast read all
# sys.stdin.readlines()

for case_num in [1]:
    # read line as a string
    # strr = input()

    # read line as an integer
    # k = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    k, nrows = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    grid = []
    for _ in range(nrows):
        grid.append(list(map(int,input().split())))

    res = solve(k, grid)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 998244353
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    N, K = map(int, readline().split())

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

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

    for i in range(1, N + 1):
        cur += acc[i]
        cur %= MOD
        dp[i] = cur
        dp[i] %= MOD
        for l, r in mat:
            acc[i + l] += dp[i]
            acc[i + l] %= MOD
            acc[i + r + 1] -= dp[i]
            acc[i + r + 1] %= MOD

    print(dp[N] % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 998244353
N = int(1e6)
n, k = map(int, input().split())
seg = []
for i in range(k):
    seg.append(tuple(map(int, input().split())))
pref = [1] + [0] * N
for i in range(1, n):
    pref[i] += pref[i - 1]
    for x, y in seg:
        pref[i] += pref[i - x] - pref[i - y - 1] + mod
    pref[i] %= mod
print((pref[n - 1] - pref[n - 2] + mod) % mod)

Submission status: Accepted

Solution code:
MOD = 998244353

n, k = map(int, input().split())
left=[]
right=[]
for _ in range(k):
    l,r=map(int, input().split())
    left+=[l]
    right+=[r]
pref = [0,1]

for i in range(n-1):
    new = 0
    for j in range(k):
        new += pref[max(0,i+2-left[j])] - pref[max(0,i+1-right[j])]
        #print(pref[max(0,i+2-left[j])], pref[max(0,i+1-right[j])])
    pref.append((pref[-1] + new) % MOD)
print(new % MOD)

Submission status: Accepted

Solution code:
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]

####
MOD = 998244353
YES, NO, IMP = "YES", "NO", "IMPOSSIBLE"
from collections import defaultdict as ddic

def solve(N, K, A):
    dp = [0] * N
    dp[0] = 1
    windows = [0] * K
    for i in xrange(1, N):
        for k, (L, R) in enumerate(A):
            if 0 <= i - L < N:
                windows[k] += dp[i - L]
            if 0 <= i - R - 1 < N:
                windows[k] -= dp[i - R - 1]
            windows[k] %= MOD
        dp[i] += sum(windows)
        dp[i] %= MOD

    return dp[-1] % MOD
    
N, K = rrm()
A = rrmm(K)
print solve(N, K, A) % MOD

Submission status: Accepted

Solution code:
mod = 998244353

N,K = map(int,input().split())
O = []
for i in range(K):
    O.append(tuple(map(int,input().split())))

A = [0] * (N+1)
A[0] = 1
B = [0] * (N+1)
aaa = 0
for i in range(N):
    for L,R in O:
        if i + L < N:
            B[i + L] += A[i]
            if i + R < N:
                B[i + R + 1] -= A[i]
    aaa += B[i + 1]
    A[i+1] = aaa % mod

print(A[N-1])

Submission status: Accepted

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

DP = [0 for _ in range(N+1)]
DP[0] = 1
DP_sum = [0 for _ in range(N+1)]
DP_sum[0] = 1

#print(moves)

for n in range(1,N+1):
  for l,r in moves:
    if n-l >= 0:
      DP[n] += DP_sum[n-l]
      if n-r-1 >= 0:
        DP[n] -= DP_sum[n-r-1]
    DP[n] %= MOD
  DP_sum[n] = (DP_sum[n-1] + DP[n]) % MOD
  #print(DP)
  #print(DP_sum)
  
print(DP[N-1] % MOD)

Submission status: Accepted

Solution code:
MOD = 998244353
N,K = map(int,input().split())
lr = []
for i in range(K):
    lr.append(list(map(int,input().split())))
dp = [0] * (10**6)
dp[0] = 1
dpcum = [0] * (10**6)
dpcum[0] = 1
for i in range(1,N+1):
    for j in range(K):
        dp[i] += dpcum[max(-1,i-lr[j][0])] - dpcum[max(-1,i-lr[j][1]-1)]
        dp[i] %= MOD
    dpcum[i] = (dpcum[i-1] + dp[i]) % MOD
#print(dp)
print(dp[N-1])

Submission status: Accepted

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

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(self.n+1) # 1-indexed

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        # i: 0-indexed
        i += 1 # to 1-indexed
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        # return sum of [i, j)
        # i, j: 0-indexed
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        # return sum of [0, i)
        # i: 0-indexed
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & (-i)
        return res

class RangeAddBIT:
    def __init__(self, n):
        self.n = n
        self.bit1 = BIT(n)
        self.bit2 = BIT(n)

    def init(self, init_val):
        self.bit2.init(init_val)

    def add(self, l, r, x):
        # add x to [l, r)
        # l, r: 0-indexed
        self.bit1.add(l, x)
        self.bit1.add(r, -x)
        self.bit2.add(l, -x*l)
        self.bit2.add(r, x*r)

    def sum(self, l, r):
        # return sum of [l, r)
        # l, r: 0-indexed
        return self._sum(r) - self._sum(l)

    def _sum(self, i):
        # return sum of [0, i)
        # i: 0-indexed
        return self.bit1._sum(i)*i + self.bit2._sum(i)

bit = RangeAddBIT(n+10)
bit.add(1, 2, 1)
for i in range(1, n):
    t = bit.sum(i, i+1)
    t %= mod
    #print(t)
    for j in range(k):
        l, r = LR[j]
        bit.add(i+l, i+r+1, t)
print(bit.sum(n, n+1)%mod)

Submission status: Accepted

Solution code:
# https://raw.githubusercontent.com/cheran-senthil/PyRival/master/pyrival/data_structures/SegmentTree.py


class SegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size : _size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1

        return self._func(res_left, res_right)

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)


N, K = [int(x) for x in input().split()]
LR = [[int(x) for x in input().split()] for i in range(K)]

MOD = 998244353
numWays = SegmentTree([0 for i in range(N + 1)], 0, lambda x, y: x + y)
numWays[1] = 1

for i in range(2, N + 1):
    total = 0
    for l, r in LR:
        if i - l >= 0:
            total += numWays.query(max(0, i - r), i - l + 1)
    numWays[i] = total % MOD


print(numWays[N])

Submission status: Accepted

Solution code:
n,k = list(map(int,input().split()))
arr = []
for i in range(k):
    l = list(map(int,input().split()))
    arr.append(l)
mex = 2*pow(10,5) + 5
mod = 998244353
dp = [0 for i in range(mex)]
suf = [0 for i in range(mex)]
dp[n] = 1
suf[n] = 1
for i in range(n-1,0,-1):
    for j in range(k):
        l = i+arr[j][0]
        r = i+arr[j][1]
        r = min(r,n)
        if l<=r:
            dp[i] = (dp[i]+suf[l]-suf[r+1])%mod
    suf[i] = (dp[i]+suf[i+1])%mod
print(dp[1])

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools
import decimal
import copy
import heapq

# import numpy as np

# sys.setrecursionlimit(10 ** 6)
INF = 10 ** 20
# MOD = 10 ** 9 + 7
MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))
flush = lambda: sys.stdout.flush()


# ===CODE===
def main():
    n, k = ns()
    pos = []
    for _ in range(k):
        l, r = ns()
        pos.append([l, r])

    imos = [0 for _ in range(n + 1)]
    imos[0] = 1
    imos[1] = -1
    total = 0

    for i in range(n):
        total += imos[i]
        total %= MOD
        if total > 0:
            for l, r in pos:
                if i + l <= n:
                    imos[i + l] += total
                    imos[i + l] %= MOD
                if i + r + 1 <= n:
                    imos[i + r + 1] -= total
                    imos[i + r + 1] %= MOD

    print(total % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD=998244353
N,K=map(int,input().split())
LR=[]
for i in range(K):
    l,r=map(int,input().split())
    LR.append((l,r))
LR.sort(key=lambda x:x[0])

#0-indexedにする
dp=[0]*N
imos=[0]*(N+1)
dp[0]=1

for i in range(N):
    dp[i]=(dp[i]+imos[i])%MOD
    for l,r in LR:
        if i+l>=N:
            break
        imos[i+l]=(imos[i+l]+dp[i])%MOD
        R=min(i+r+1,N)
        imos[R]=(imos[R]-dp[i]+MOD)%MOD
    imos[i+1]=(imos[i]+imos[i+1])%MOD
print(dp[N-1])

Submission status: Accepted

Solution code:
def main():
    MOD = 998244353
    N, K = list(map(int, input().split()))
    section_list = [list(map(int, input().split())) for _ in range(K)]
    dp = [0] * N
    dp[0] = 1
    dp[1] = -1
    for n in range(N):
        cnt = dp[n]
        for k in range(K):
            L, R = section_list[k]
            if n + L < N:
                dp[n + L] += cnt
                dp[n + L] %= MOD
            if n + R + 1 < N:
                dp[n + R + 1] -= cnt
                dp[n + R + 1] %= MOD
        if n < N - 1:
            dp[n + 1] += dp[n]
            dp[n + 1] %= MOD
    print(dp[N - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class segtree:
  #セグメント木
  def __init__(s, v, op, e):
    s._n = len(v)
    s.log = s.ceil_pow2(s._n)
    s.size = 1 << s.log
    s.d = [e()] * (2 * s.size)
    s.e = e
    s.op = op
    for i in range(s._n): s.d[s.size + i] = v[i]
    for i in range(s.size - 1, 0, -1): s.update(i)
  
  # 1点更新
  def set(s, p, x):
    p += s.size
    s.d[p] = x
    for i in range(1, s.log + 1): s.update(p >> i)
 
  # 1点取得
  def get(s, p):
    return s.d[p + s.size]
 
  # 区間演算
  def prod(s, l, r):
    sml, smr = s.e(), s.e()
    l += s.size
    r += s.size
    while (l < r):
      if l & 1: 
        sml = s.op(sml, s.d[l])
        l += 1
      if r & 1:
        r -= 1
        smr = s.op(s.d[r], smr)
      l >>= 1
      r >>= 1
    return s.op(sml, smr)
 
  # 全体演算
  def all_prod(s): return s.d[1]
 
  def update(s, k): s.d[k] = s.op(s.d[2 * k], s.d[2 * k + 1])
  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x


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

def e():
  return 0
def op(a, b):
  return (a + b) % MOD

seg = segtree([0] * N, op, e)
seg.set(0, 1)

for i in range(1, N):
  ans = 0
  for l, r in LR:
    r, l = max(0, i - l + 1), max(0, i - r)
    ans = (ans + seg.prod(l, r)) % MOD
  seg.set(i, ans)

print(seg.get(N - 1))

Submission status: Accepted

Solution code:
M=998244353
class BIT:
    def __init__(self,n):
        self.size=n
        self.tree=[0]*-~n
    def sum(self,i):
        s=0
        while i:
            s=(s+self.tree[i])%M
            i-=i&-i
        return s
    def add(self,i,x):
        while i<=self.size:
            self.tree[i]=(self.tree[i]+x)%M
            i+=i&-i
(n,k),*s=[[*map(int,t.split())]for t in open(0)]
bit=BIT(n+5)
bit.add(1,1)
bit.add(2,-1)
for i in range(1,n):
    p=bit.sum(i)
    for l,r in s:
        l+=i
        r+=i
        if l>n:l=n+1
        if r>n:r=n+1
        bit.add(l,p)
        bit.add(r+1,-p)
print(bit.sum(n))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
pr=998244353
ku=[list(map(int, input().split())) for i in range(K)]
l=[0]*(N)
l[0]=1
for i in range(1,N):
    t=0
    for j in ku:
        if i>=j[0]:
            if i>j[1]:
                t+=l[i-j[0]]-l[i-j[1]-1]
            else:
                t+=l[i-j[0]]
    l[i]=(l[i-1]+t)%pr
print((l[-1]-l[-2])%pr)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
mod = 998244353
x = [list(map(int, input().split())) for _ in range(k)]
x.sort()
dp = [0] * (n + 1)
dpsum = [0] * (n + 1)
dp[1], dpsum[1] = 1, 1
for i in range(2, n + 1):
    cnt = 0
    for j in range(k):
        cnt += (dpsum[max(0, i - x[j][0])] - dpsum[max(0, i - x[j][1] - 1)])
        cnt %= mod
        if i - x[j][1] < 0:
            break
    dp[i] = cnt
    dpsum[i] = dp[i] + dpsum[i - 1]
ans = dp[n]
print(ans)

Submission status: Accepted

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

mod = 998244353

S = [0, 1]

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

print(a)

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

Submission status: Accepted

Solution code:
mod = 998244353
n,k = map(int,input().split())
c = [0 for _ in range(n+1)]
cs = [0 for _ in range(n+1)]
c[1] = 1
cs[1] = 1
csi = 1
lr = [(0,0) for _ in range(k)]
for i in range(k):
  li,ri = map(int,input().split())
  lr[i] = (li,ri)
for i in range(2,n+1):
  for lri in lr:
    l,r = lri
    if i-l > 0:
      c[i] = (c[i]+cs[i-l]-cs[max(0,i-r-1)])%mod
  csi = (c[i]+csi)%mod
  cs[i] = csi
print(c[n])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("## ",*x,file=sys.stderr) if LOCAL else 0
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 998244353
 
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(tuple(map(int, input().split())) for i in range(K)) #改行行列

    dp=[0]*N
    dp[0]=1
    acc=[0]*N
    tacc=0
    for i in range(N):
        if i!=0:
            tacc=(tacc+acc[i])%mod
            dp[i]=tacc
        for l,r in S:
            if i+l<N:
                acc[i+l]+=dp[i]
                acc[i+l]%=mod
            if i+r+1<N:
                acc[i+r+1]-=dp[i]
                acc[i+r+1]%=mod
        
    print(dp[-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
I=[0]*K
for m in range(K):
    l,r=map(int,input().split())
    I[m]=(l,r)

Mod=998244353

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

for x in range(2,N+1):
    DP[x]=DP[x-1]
    for (l,r) in I:
        a=max(0,x-r-1)
        b=max(0,x-l)
        DP[x]+=DP[b]-DP[a]
        DP[x]%=Mod
print((DP[N]-DP[N-1])%Mod)