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

MOD = 998244353

PAT = []
for _ in range(K):
  l,r = map(int, input().split())
  PAT.append((l,r))
  
IMOS = [0] * (N+10)
IMOS[1] = 1
for i in range(0,N):
  if IMOS[i] == 0:
    continue
  for l,r in PAT:
    if i+l > N+1:
      continue
    IMOS[i+l] += IMOS[i]
    if i+r-1 > N+1:
      continue
    IMOS[i+r+1] -= IMOS[i]
  #print(i, IMOS)
  IMOS[i+1] += IMOS[i]
  IMOS[i+1] %= MOD
  
print((IMOS[N] - IMOS[N-1]) % MOD)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
div = 998244353
S = []
for i in range(k):
  S.append(tuple(map(int, input().split())))
#print(S)###

dp = [0] * (2 * n)
wa = [0] * k

dp[n] = 1
#print(dp)

for i in range(n + 1, 2 * n):
  for j in range(k):
    wa[j] += (dp[i - S[j][0]] - dp[i - S[j][1] - 1])
    dp[i] += wa[j]
  dp[i] %= div
#print(dp)
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 998244353
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,K = IL()
lr = [IL() for i in range(K)]
lr.sort()

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

for i in range(2,N+1):
  tmp = 0
  for l,r in lr:
    if tmp >= r:
      continue
    elif l <= tmp < r:
      l = tmp+1
    if 1 <= i-l:
      dp[i] += data[i-l] - data[max(i-r-1, 0)]
  data[i] = (data[i-1] + dp[i]) %mod
print(dp[N] %mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = [tuple(map(int, line.split())) for line in sys.stdin.buffer.readlines()]
A.sort()
mod = 998244353

acc = [0]*(N+5)
acc[0] = 1
for i in range(1, N+1):
    cum = 0
    for l, r in A:
        if i-l < 0:
            break
        p, q = max(0, i-r), max(0, i-l)
        cum += acc[q]-acc[p-1]
    acc[i] = (cum+acc[i-1]) % mod

print((acc[N-1]-acc[N-2]) % mod)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
#R = 10**9 + 7
R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
l = []
r = []
for i in range(k):
    ll,rr = inm()
    l.append(ll)
    r.append(rr)
a = [0]*n
c = [0]*(n+1)
a[0] = c[0] = 1
for i in range(1,n):
    for j in range(k):
        if i-l[j]>=0:
            a[i] = (a[i]+c[i-l[j]]-c[max(0,i-r[j])-1])%R
    c[i] = (c[i-1]+a[i])%R
print(a[n-1])

Submission status: Accepted

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

Q = 998244353
L, R = [], []

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

P = [0] * N
P[0] = 1

C = [0] * N
C[0] = 1
S = 1

for i in range(1, N):
    for l, r in zip(L, R):
        if l > i:
            break
        
        if r >= i:
            P[i] += C[i-l]
        else:
            s = C[i-l] - C[i-r-1]
            if s < 0:
                s += Q
            P[i] += s

        P[i] = P[i] % Q
    S += P[i]
    S %= Q
    C[i] = S


print(P[-1])

Submission status: Accepted

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

    dp = [0]*(n*2 + 100)
    dp[1] = 1
    dp[2] = -1
    for i in range(1,n + 1):
        dp[i] = (dp[i] + dp[i - 1])%mod
        for l,r in LR:
            if i + l > n:
                continue
            dp[l + i] = (dp[l+i] + dp[i])%mod
            dp[r + i + 1] = dp[r+i+1] - dp[i]  if dp[r+i+1] - dp[i] > 0 else dp[r+i+1] - dp[i] + 998244353
    print(dp[n]%998244353) 
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

mod = 998244353

class BinaryIndexedTree() :
  def __init__(self, n, mod) :
    self.n = n
    self.mod = mod
    self.tree = [0] * (n + 1)
      
  def sum(self, i) :
    s = 0
    while i > 0 :
      s += self.tree[i]
      i -= i & -i
    return s
      
  def add(self, i, x) :
    while i <= self.n :
      self.tree[i] += x
      self.tree[i] %= mod
      i += i & -i
      
BIT = BinaryIndexedTree(N * 2, mod)
BIT.add(1, 1)
BIT.add(2, -1)
for i in range(1, N) :
  for l, r in LR :
    x = BIT.sum(i)
    BIT.add(i + l, x)
    BIT.add(i + r + 1, -x)

print(BIT.sum(N) % mod)

Submission status: Accepted

Solution code:
n,k= list(map(int, input().split()))
INF=998244353
s=[]
for i in range(k):
    j,jj=map(int,input().split())
    s.append([l for l in range(j,jj+1)])
pattern=[0 for i in range(n)]
pattern[0]=1
ls=len(s)
memo=[0 for i in range(k)]
s.sort()
for i in range(1,n):
    tmp=0
    for index,j in enumerate(s):
        if i-j[0]<0:
            break
        elif i-j[-1]>0:
            memo[index]+=pattern[i-j[0]]
            memo[index]-=pattern[i-j[-1]-1]
            if memo[index]<0:
                memo[index]+=INF
        else:
            memo[index]+=pattern[i-j[0]]

        #tmp+=sum(pattern[max(i-j[-1],0):i-j[0]+1])
        memo[index]%=INF
    pattern[i]=(sum(memo)%INF)
print(pattern[-1])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 998244353
#main code here!
    n,k=MI()
    area=[LI() for i in range(k)]
    #ソース　https://juppy.hatenablog.com/entry/2018/11/17/蟻本_python_Binary_Indexed_Tree_競技プログラミング
    #A1 ... AnのBIT(1-indexed)
    m=2*n
    BIT = [0]*(2*n+1)
    #idxの一番下のbit
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]%mod
            idx -= idx&(-idx)
        return res_sum%mod
    
    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= m:
            BIT[idx] += x%mod
            idx += idx&(-idx)
        return
    BIT_update(n+1,1)
    #print(BIT)
    for i in range(n+2,2*n+1):
        ans=0
        for j in range(k):
            l,r=area[j]
            #print(l,r)
            #print(BIT_query(i-r-1),BIT_query(i-l))
            ans=(ans+BIT_query(i-l)-BIT_query(i-r-1))%mod
        #print(ans)
        BIT_update(i,ans%mod)
        #print(BIT)
    #print(BIT)
    print((BIT_query(2*n)-BIT_query(2*n-1))%mod)
            

    
        
        
        
        
    
        
                    
            
        



        
        
        
        
        
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

N, K = map(int, input().split())
S = set()
for _ in range(K):
    l, r = map(int, input().split())
    S.add((l, r))

mod = 998244353
dp = [0 for _ in range(N+1)]
dp[1] = 1
acc = [0 for _ in range(N+1)]
acc[1] = 1
for i in range(1, N+1):
    for (l, r) in S:
        left = max(i - r - 1, 0)
        right = max(i - l, 0)
        # print("left", left, "right", right)
        dp[i] += acc[right] - acc[left]
        dp[i] %= mod
    acc[i] = acc[i-1] + dp[i]
    acc[i] %= mod

# print(acc)
print(dp[N])

Submission status: Accepted

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

mod = 998244353

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

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

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

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

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

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

b = BitImos(n)
b.add(0,1,1)

for i in range(n):
    tmp = b.get(i)
    tmp %= mod
    for l1,r1 in lr:
        if i + l1 < n:
            b.add(i+l1, min(i+r1+1, n), tmp)

print(b.get(n-1) % mod)

Submission status: Accepted

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

mod = 998244353
        
table = [0]*N
table[0] = 1
TABLE = [0]*N
TABLE[0] = 1

for i in range(1, N):
    TABLE[i] = TABLE[i-1]
    for L, R in S:
        l = i-L
        r = i-R-1
        if r >= 0:
            table[i] += TABLE[l] - TABLE[r]
            table[i] %= mod
            TABLE[i] += TABLE[l] - TABLE[r]
            TABLE[i] %= mod
        elif l >= 0 and r < 0:
            table[i] += TABLE[l]
            table[i] %= mod
            TABLE[i] += TABLE[l]
            TABLE[i] %= mod
            
print(table[N-1]%mod)

Submission status: Accepted

Solution code:
mod = 998244353

N, K = list(map(int, input().split()))
S = [list(map(int, input().split())) for _ in range(K)]
dp = [0]*(2*N+10)
dp[0] = 1
tmp = 0
for i in range(N):
    tmp += dp[i]
    tmp %= mod
    for L, R in S:
        dp[i+L] += tmp
        dp[i+R+1] -= tmp
print(dp[N-1]%mod)

Submission status: Accepted

Solution code:
n,k=map(int, input().split())
lr=[list(map(int,input().split())) for _ in range(k)]
mod=998244353
dp2=[0]*n
dp2[0]=1
for i in range(1,n):
    dp2[i]+=dp2[i-1]
    for l,r in lr:
        if i-l>=0:
            dp2[i]+=dp2[i-l]
        elif i-l<0 and i-r>=0:
            dp2[i]+=dp2[0]
        if i-r-1>=0:
            dp2[i]-=dp2[i-r-1]
    dp2[i]%=mod
print((dp2[-1]-dp2[-2])%mod)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
lr = [tuple(map(int, input().split())) for _ in range(k)]
lr.sort()
dp = [0]*(n)
cum = [0]*(n)
dp[0] = 1
cum[0] = 1
vals = [0] * k
M = 998244353
for i in range(1,n):
    for j,(l,r) in enumerate(lr):
#         vals[j] = cum[r] - cum[l-1]
        if i-l>=0:
            tmp = cum[max(i-l,0)]
            if i-r-1>=0:
                tmp -= cum[max(0, i-r-1)]
            vals[j] = tmp
            vals[j] %= M
    dp[i] = sum(vals)
    dp[i] %= M    
    cum[i] = cum[i-1] + dp[i]
    cum[i] %= M
ans = dp[n-1]%M
print(ans%M)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 998244353


def main():
    N, K = map(int, input().split())
    dp = [0] * (N + 1)
    LR = [list(map(int, input().split())) for _ in range(K)]
    dp[1] = 1
    for i in range(1, N):
        for j in range(K):
            if i + LR[j][0] <= N:
                dp[i + LR[j][0]] += dp[i]
                dp[i + LR[j][0]] %= m
            if i + LR[j][1] < N:
                dp[i + LR[j][1]+1] -= dp[i]
                dp[i + LR[j][1]+1] %= m
        # print(dp)
        if i < N-1:
            dp[i + 2] += dp[i+1]
            dp[i + 2] %= m
    print(dp[N])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

MOD = 998244353

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

class SegmentTreeDual():
    def __init__(self, arr, op=lambda x, y: y if y != -1 else x, ie=-1):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.op = op
        self.val = [ie for _ in range(self.n)]
        self.laz = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.val[i] = arr[i]

    def propagate(self, k):
        if self.laz[k] == self.ie: return
        if self.n <= k:
            self.val[k - self.n] = self.op(self.val[k - self.n], self.laz[k])
        else:
            self.laz[2 * k] = self.op(self.laz[2 * k], self.laz[k])
            self.laz[2 * k + 1] = self.op(self.laz[2 * k + 1], self.laz[k])
        self.laz[k] = self.ie

    def update(self, lt, rt, x):
        lt += self.n
        rt += self.n
        while rt - lt > 0:
            if lt & 1:
                self.laz[lt] = self.op(self.laz[lt], x)
                self.laz[lt] %= MOD
                lt += 1
            if rt & 1:
                rt -= 1
                self.laz[rt] = self.op(self.laz[rt], x)
                self.laz[rt] %= MOD
            lt >>= 1
            rt >>= 1

    def get(self, idx):
        res = self.val[idx]
        idx += self.n
        while idx:
            res = self.op(res, self.laz[idx])
            res %= MOD
            idx >>= 1
        return res

from operator import add

arr = [0] * N
arr[0] = 1

S = SegmentTreeDual(arr, add, 0)

for i in range(N - 1):
    s = S.get(i)
    for l, r in I:
        S.update(min(i + l, N), min(i + r + 1, N), s)

print(S.get(N - 1) % MOD)

Submission status: Accepted

Solution code:
class BITRAQ:
    def __init__(self, n, mod):
        self.n = n + 1
        self.mod = mod
        self.bit = [[0]*(self.n) for _ in range(2)]
    
    def add_sub(self, p, i, x):
        while i < self.n:
            self.bit[p][i] += x
            self.bit[p][i] %= self.mod
            i += i & -i
    
    def add(self, l, r, x):
        self.add_sub(0, l, -x * (l - 1))
        self.add_sub(0, r, x * (r - 1))
        self.add_sub(1, l, x)
        self.add_sub(1, r, -x)

    def sum_sub(self, p, i):
        s = 0
        while i > 0:
            s += self.bit[p][i]
            i -= i & -i
        return s
    
    def sum(self, i):
        return self.sum_sub(0, i) + self.sum_sub(1, i) * i

    def get(self, i):
        return self.sum(i) % self.mod - self.sum(i - 1) % self.mod

p = 998244353

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

hop = []

for i in range(K):
    hop.append(tuple(map(int, input().split())))

dp = BITRAQ(N, p)

dp.add(1, 2, 1)

for i in range(N - 1):
    for j in range(K):
        dp.add(i + hop[j][0] + 1, min(N + 1, i + hop[j][1] + 2), dp.get(i + 1) % p)

print(dp.get(N) % p)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 998244353
INF = float("inf")

sys.setrecursionlimit(1000000)

def main():
    N, K = LI()
    LR = LIR(K)
    cumsum = [0] * (N+2)

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

    for i in range(N-1, 0, -1):
        for l, r in LR:
            dp[i] = (dp[i] + cumsum[min(i + l, N+1)] - cumsum[min(i + r + 1, N+1)]) % MOD

        cumsum[i] = (cumsum[i] + dp[i] + cumsum[i+1]) % MOD

    print(dp[1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
MOD=998244353
S=[]
for _ in range(K):
    L,R=map(int,input().split())
    S.append((L,R))
S.sort()
dp=[0]*(N+1)
dp[1]=1
ans=[0]*(K+1)
for i in range(2,N+1):
    for j in range(K):
        L,R=S[j][0],S[j][1]
        if L>=i:
            break
        l=max(0,i-R)
        r=min(i-1,i-L)
        ans[j]+=dp[r]-dp[l-1]
    dp[i]+=sum(ans)
    dp[i]%=MOD
print(dp[N]%MOD)

Submission status: Accepted

Solution code:
MOD = 998244353
n, k = (int(x) for x in input().split())
LR = [tuple(int(x) for x in input().split()) for _ in range(k)]
LR.sort()
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = -1
for i in range(1, n + 1):
    dp[i] += dp[i - 1] % MOD
    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[n] % MOD)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod = 998244353
INF = 10**18
eps = 10**-7

n,k = map(int,readline().split())
LR = [list(map(int,readline().split())) for i in range(k)]



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

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

print(dp[n])

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


class Bit:

    def __init__(self, a):
        if hasattr(a, "__iter__"):
            le = len(a)
            self.n = 1 << le.bit_length()
            self.values = values = [0] * (self.n + 1)
            values[1:le + 1] = a[:]
            for i in range(1, self.n):
                values[i + (i & -i)] += values[i]
        elif isinstance(a, int):
            self.n = 1 << a.bit_length()
            self.values = [0] * (self.n + 1)
        else:
            raise TypeError

    # A[i] += val
    def add(self, i, val):
        n, values = self.n, self.values
        while i <= n:
            values[i] += val
            i += i & -i

    # A[1, i]の累積和
    def sum(self, i):
        values = self.values
        res = 0
        while i > 0:
            res += values[i]
            i -= i & -i
        return res

    # A[1, i]の累積和 が v 以上になる最小の i
    def bisect_left(self, v):
        n, values = self.n, self.values
        if v > values[n]:
            return None
        i, step = 0, n >> 1
        while step:
            if values[i + step] < v:
                i += step
                v -= values[i]
            step >>= 1
        return i + 1


def main():

    N, K = in_nn()
    LR = []
    for i in range(K):
        l, r = in_nn()
        LR.append((l, r))

    init_dp = [0] * N
    init_dp[0] = 1
    init_dp[1] = -1
    bit = Bit(init_dp)

    mod = 998244353
    for i in range(1, N + 1):
        for k in range(K):
            l, r = LR[k]
            now = bit.sum(i) % mod
            bit.add(i + l, now)
            bit.add(i + r + 1, -now)

    print(bit.sum(N) % mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.bit[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.bit[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i-1)

mod = 998244353
N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(K)]
A.sort()
dp = BIT(N)
dp.add(1,1)
for i in range(2,N+1):
  for l,r in A:
    if i-l<=0:
      continue
    if i-r>0:
      dp.add(i,dp.get(i-r,i-l)%mod)
    else:
      dp.add(i,dp.sum(i-l)%mod)
print(dp.el[-1]%mod)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
mod = 998244353
lr = []
s = set()
for i in range(k):
  l,r = map(int, input().split())
  for j in range(l,r+1):
    s.add(j)
  lr.append([l,r])

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

for i in range(1,n+1):
  for j in range(k):
    l,r = lr[j][0],lr[j][1]
    if i-l < 1:
      continue
    tot[j] += dp[i-l]
    if i-r > 1:
      tot[j] -= dp[i-r-1]
    dp[i] += tot[j]
    dp[i] %= mod
print (dp[n])

Submission status: Accepted

Solution code:
z=[]
inp=list(map(int,input().split()))
n=inp[0]
k=inp[1]
for i in range(k):
    inp=list(map(int,input().split()))
    z.append(inp)
z.sort()
cum=[0]*(n+1)
cum[1]=1
for i in range(2,n+1):
    ans=0
    for j in range(len(z)):
        if i-z[j][1]>=1:
            ans+=cum[i-z[j][0]]-cum[i-z[j][1]-1]
        elif i-z[j][0]>=1 and i-z[j][1]<1:
            ans+=cum[i-z[j][0]]
        else:
            break
    cum[i]=cum[i-1]+ans
    cum[i]=cum[i]%998244353
print ((cum[-1]-cum[-2])%998244353)

Submission status: Accepted

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

MOD = 998244353

PAT = []
for _ in range(K):
  l,r = map(int, input().split())
  PAT.append((l,r))
  
IMOS = [0] * (N+10)
IMOS[1] = 1
for i in range(0,N):
  if IMOS[i] == 0:
    continue
  for l,r in PAT:
    if i+l > N+1:
      continue
    IMOS[i+l] += IMOS[i]
    if i+r-1 > N+1:
      continue
    IMOS[i+r+1] -= IMOS[i]
  #print(i, IMOS)
  IMOS[i+1] += IMOS[i]
  IMOS[i+1] %= MOD
  
print((IMOS[N] - IMOS[N-1]) % MOD)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=[]
p=998244353
for i in range(k):
    l,r=map(int,input().split())
    s.append([l,r])
k=len(s)
dp=[0]*(3*n)
dp[1]=1
dp[2]=-1
for i in range(1,n):
    dp[i]=(dp[i-1]+dp[i])%p
    for j in range(k):
        l,r=s[j][0],s[j][1]
        dp[i+l]=(dp[i+l]+dp[i])%p
        dp[i+r+1]=(dp[i+r+1]-dp[i])%p

dp[n]=dp[n-1]+dp[n]

print(dp[n]%p)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
# N: 処理する区間の長さ

data0 = [0]*(N+1)
data1 = [0]*(N+1)
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def _get(data, k):
    s = 0
    while k:
        s += data[k]
        s %= MOD
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

MOD = 998244353


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

dp = [0] * (N+10)
add(1, 2, 1)
for i in range(1, N+1):
    dp[i] = query(i, i+1) % MOD
    for l, r in lr:
        if i+l > N+1: continue
        add(l+i, min(i+r+1, N+1), dp[i])
    

print(dp[N])

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
 
    def to_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= (i & -i)
        return s
 
    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)
 
    def get(self, i, j):
        return self.to_sum(j)-self.to_sum(i-1)

N,K = map(int,input().split());MOD = 998244353
S = []
for i in range(K):
  temp = list(map(int,input().split()))
  S.append(temp)
#print(S)
Tree = BIT(N) #1index
Tree.add(1,1) #最初
for i in range(1,N+1):
  for l,r in S:
    #print(i-r,i-l)
    if i-r >= 1:
      temp = Tree.get(i-r,i-l)
    elif i-l >= 1:
      temp = Tree.get(1,i-l)
    else:
      temp = 0
    Tree.add(i,temp%MOD)
ans = Tree.get(N,N)%MOD
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, k = map(int,input().split())
    listS = []
    M = 998244353
    for i in range(k):
        l,r = map(int,input().split())
        # s.append(l)
        # s.append(r)
        listS.append((l,r))
    # listS = list(set(s))
    dp = [0] * n
    dp[0] = 1
    sm = 0
    for i in range(n):
        sm += dp[i] % M
        for lr in listS:
            if lr[0] + i < n:
                dp[i+lr[0]] += sm
            if i + lr[1] + 1 < n :
                dp[i+lr[1]+1] -= sm
            # else:
            #     dp[-1] -= dp[i]

        # print(dp)
    ans = dp[-1]%M
    if ans < 0:ans=0

    print(ans)
    # print(ans%M)
    # print(dp)

if __name__=='__main__':
    main()

Submission status: Accepted

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

kMod = 998244353

counts = [0] * N
counts[0] = 1
window_sums = [0] * K

for i in range(1, N):
    for k in range(K):
        l, r = LR[k]
        leave, enter = i-r-1, i-l
        if leave >= 0:
            window_sums[k] -= counts[leave]
        if enter >= 0:
            window_sums[k] += counts[enter]
        window_sums[k] %= kMod
    counts[i] = sum(window_sums) % kMod
print(counts[-1])

Submission status: Accepted

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

dp = [0 for i in range(N)]
imos = [0 for i in range(N)]
imos[0] = 1
dp[0] = 1

for i in range(1,N):
    for l,r in move:
        L = i-r
        R = i-l
        if R<0:
            continue
        L = max(L,0)
        if L>=1:
            dp[i] += imos[R]- imos[L-1]
        else:
            dp[i] += imos[R]
        dp[i] %= mod
    imos[i] = dp[i] + imos[i-1]
    imos[i] %= mod

print(dp[N-1])

Submission status: Accepted

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

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

dp = [0]*N
dp[0] = 1
if D[0][0]<N:
    dp[D[0][0]] = 1

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

Submission status: Accepted

Solution code:
from sys import stdin,stdout
def ws(pos,win):
    l,r=win
    l1=pos-r
    r1=pos-l
    l=max(l1,0)
    r=max(r1,0)
    # print(pos,l,r)
    sm=ps[r]-(ps[l-1] if l>=1 else 0)
    return (sm+M)%M
n,k=list(map(int,stdin.readline().split()));w=[];s=[];M=998244353
for _ in range(k):
    x,y=list(map(int,stdin.readline().split()))
    w+=[[x,y]]
dp=[0]*(n+1);dp[1]=1;ps=[0,1]
for i in range(2,n+1):
    for win in w:
        ans=ws(i,win)
        dp[i]=(dp[i]+ans)%M
    ps+=[ps[-1]+dp[i]]
# print(dp)
# print(ps)
print(dp[n])