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:

#####segfunc#####
def segfunc(x, y):
    return x+y
#################

#####ide_ele　単位元#####
ide_ele = 0
#################



class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

mod=998244353
n,k=map(int,input().split())
Q=[]
for _ in range(k):
    a,b=map(int,input().split())
    Q.append((a,b))

dp=[0 for i in range(n+1)]
dp[1]=1
dp=SegTree(dp,segfunc,ide_ele)
for i in range(2,n+1):
    cnt=0
    for que in Q:
        cnt+=dp.query(max(0,i-que[1]),max(0,i-que[0]+1))%mod
        #print(cnt)
        cnt%=mod
    dp.update(i,cnt)
print(dp.query(n,n+1))

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N,K = MI()
LR = [tuple(MI()) for i in range(K)]
mod = 998244353

dp = [0]*(N+1)  # dp[i] = マス1に行く方法の個数 + マス2に行く方法の個数 + … + マスiに行く方法の個数
dp[1] = 1

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

print((dp[N]-dp[N-1]) % mod)

Submission status: Accepted

Solution code:
MOD = 998244353

N, K = map(int, input().split())
seg = [tuple(map(int, input().split())) for _ in range(K)]
dp = [0] * (N+1)
dp[0] = 1
for i in range(N):
    for s, t in seg:
        if (i+s) <= N:dp[i+s] += dp[i]
        if (i+t+1) <= N:dp[i+t+1] -= dp[i]
    dp[0] = 0
    dp[i+1] += dp[i]
    dp[i+1] %= MOD
    
print(dp[N-1])

Submission status: Accepted

Solution code:
import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    L = [[] for _ in range(K)]
    for t in range(K):
        l, r = map(int, input().split())
        for j in range(l, r + 1):
            L[t].append(j)

    lc = [0] * K
    mod = 998244353

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

        for k in range(K):
            CL = L[k]
            if len(CL) == 1:
                lc[k] = dp[i - CL[0]] % mod
            else:
                if CL[-1] > i:
                    lc[k] = lc[k] % mod + dp[i - L[k][0]] % mod
                else:
                    lc[k] = (lc[k] + dp[i - L[k][0]] - dp[i - L[k][-1] - 1]) % mod
            dp[i] = lc[k] + dp[i] % mod

    print(dp[N - 1] % mod)


if __name__ == "__main__":
    main()

# \n

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
LL = []
RR = []
mod = 998244353
for i in range(K):
    L, R = map(int, input().split())

    LL.append(L)
    RR.append(R + 1)


keep = 0
dp = [0] * 2 * N
dp[N] = 1
for i in range(1, N):
    for j in range(K):

        keep = (keep + dp[N + i - LL[j]] - dp[N + i - RR[j]]) % mod 

    dp[N + i] = (dp[N + i] + keep) % mod
print(dp[2 * N - 1] % mod)

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
dp_cum = [0 for _ in range(n+1)]
dp_cum[1] = 1

mod = 998244353

for i in range(2, n+1):
    for l, r in lr:
        left, right = i - r, i - l
        if left > 0:
            dp[i] += dp_cum[right] - dp_cum[left - 1]
        elif right > 0:
            dp[i] += dp_cum[right]
    
    dp[i] %= mod
    dp_cum[i] = dp[i] + dp_cum[i-1]
    dp_cum[i] %= mod

print(dp[n])

Submission status: Accepted

Solution code:
MOD = 998244353



def dp_range(l, r):
    left = 0 if l-1 < 0 else dp_acc[l-1]
    right = 0 if r < 0 else dp_acc[r]
    return right - left

N, K = map(int, input().split())
segments = [tuple(map(int, input().split())) for _ in range(K)]
dp = [0] * (2 * N + 1)
dp_acc = [0] * (2 * N + 1)

dp[0], dp_acc[0] = 1, 1


for i in range(N):
    for j in range(K):
        dp[i] += dp_range(i - segments[j][1], i - segments[j][0])
        dp[i] %= MOD
        dp_acc[i] = (dp_acc[i - 1] + dp[i]) % MOD
print(dp[N-1])

Submission status: Accepted

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

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

from sys import exit

import sys
sys.setrecursionlimit(1000000000)
mod = 998244353

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

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

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

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

Submission status: Accepted

Solution code:
import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    L = [[] for _ in range(K)]
    for t in range(K):
        l, r = map(int, input().split())
        for j in range(l, r + 1):
            L[t].append(j)

    lc = [0] * K
    mod = 998244353

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

        for k in range(K):
            CL =L[k]
            if len(CL)==1:
                lc[k]=dp[i-CL[0]] %mod
            else:
                if CL[-1] > i:
                    lc[k] = lc[k] %mod +dp[i-L[k][0]] %mod
                else:
                    lc[k] =( lc[k] + dp[i - L[k][0]] - dp[i - L[k][-1]-1] )%mod
            dp[i] += lc[k]



    print(dp[N - 1]%mod)


if __name__ == "__main__":
    main()

# \n

Submission status: Accepted

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

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

class SegTree:
  #init(init_val, ide_ele): 配列init_valで初期化 O(N)
  def __init__(self, init_val, segfunc, ide_ele):
    #init_val: 配列の初期値
    #segfunc: 区間にしたい操作
    #ide_ele: 単位元
    #n: 要素数
    #num: n以上の最小の2のべき乗
    #tree: セグメント木(1-index)
    n = len(init_val)
    self.segfunc = segfunc
    self.ide_ele = ide_ele
    self.num = 1 << (n - 1).bit_length()
    self.tree = [ide_ele] * 2 * self.num
    # 配列の値を葉にセット
    for i in range(n):
      self.tree[self.num + i] = init_val[i]
    # 構築していく
    for i in range(self.num - 1, 0, -1):
      self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

  #update(k, x): k番目の値をxに更新 O(logN)
  def update(self, k, x):
    #k番目の値をxに更新
    #k: index(0-index)
    #x: update value
    k += self.num
    self.tree[k] = x
    while k > 1:
      self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
      k >>= 1

  #query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
  def query(self, l, r):
    #[l, r)のsegfuncしたものを得る
    #l: index(0-index)
    #r: index(0-index)
    res = self.ide_ele
    l += self.num
    r += self.num
    while l < r:
      if l & 1:
        res = self.segfunc(res, self.tree[l])
        l += 1
      if r & 1:
        res = self.segfunc(res, self.tree[r - 1])
      l >>= 1
      r >>= 1
    return res
  
#segfunc
def segfunc(x,y):
  return x+y #区間和
#ide_ele
ide_ele=0 #区間和

#初期化
seg=SegTree([0]*(N+1), segfunc, ide_ele)
seg.update(1,1)

for i in range(2,N+1):
  sum_intv=0
  for l,r in lrlist:
    left=i-r
    right=i-l    
    if right<1:
      continue
    elif left<1:
      left=1
      
    sum_intv+=seg.query(left,right+1)
    
  seg.update(i,sum_intv%MOD)
  #print(i,left,right,sum_intv%MOD)
    
print(seg.query(N,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


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__len = _len
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])
        # ep(self.__tree[self.__size:])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

    def max_right(self, l, f):
        # https://atcoder.jp/contests/practice2/submissions/16636885
        assert 0 <= l <= self.__len
        if l == self.__len:
            return self.__len

        l += self.__size
        sm = self.__ie
        while True:
            while l % 2 == 0:
                l >>= 1
            if not f(self.__op(sm, self.__tree[l])):
                while l < self.__size:
                    l = 2*l
                    if f(self.__op(sm, self.__tree[l])):
                        sm = self.__op(sm, self.__tree[l])
                        l += 1
                return l - self.__size
            sm = self.__op(sm, self.__tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self.__len

    def min_left(self, r, f):
        assert 0 <= r <= self.__len
        if r == 0:
            return 0

        r += self.__size
        sm = self.__ie
        while True:
            r -= 1
            while r > 1 and (r % 2):
                r >>= 1
            if not f(self.__op(sm, self.__tree[r])):
                while r < self.__size:
                    r = 2*r + 1
                    if f(self.__op(sm, self.__tree[r])):
                        sm = self.__op(sm, self.__tree[r])
                        r -= 1
                return r + 1 - self.__size
            sm = self.__op(sm, self.__tree[r])

            if (r & -r) == r:
                break

        return 0

    def __getitem__(self, key):
        return self.__tree[key + self.__size]



@mt
def slv(N, K, LR):
    M = 998244353
    memo = SegmentTree([0] * (N+1), add, 0)
    memo.update(1, 1)
    for i in range(2, N+1):
        v = 0
        for l, r in LR:
            v += memo.query(max(0, i-r), max(0, i-l+1))
            v %= M
        memo.update(i, v)

    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 sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

def resolve():
    n, k = map(int, input().split())
    D = [tuple(map(int, input().split())) for _ in range(k)]
    tree = SegmentTree([0] * n, lambda x, y : (x + y) % MOD, 0)
    tree.update(0, 1)

    for i in range(1, n):
        for l, r in D: # [i - r, i - l]
            if i - l >= 0:
                tree.add(i, tree.sum(max(0, i - r), i - l + 1))

    print(tree[n - 1] % MOD)
resolve()

Submission status: Accepted

Solution code:
def resolve():
    n, k = map(int, input().split())
    mod = 998244353
    dp = [0] * (3*n)
    imos = [0] * (3*n)
    lr = []
    for i in range(k):
        l, r = map(int, input().split())
        lr.append((l, r+1))
    for l, r in lr:
        imos[l] += 1
        imos[r] += -1
    for i in range(1, n+1):
        dp[i] = (dp[i-1] + imos[i]) %mod
        for l, r in lr:
            imos[min(i+l, n+2)] += dp[i]
            imos[min(i+r, n+2)] += -1*dp[i]
    print(dp[n-1]%mod)

resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import math
import itertools

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,k = readInts()
lr = [readInts() for i in range(k)]

dp = [-1]*(n+2)
dp[n]=1
dp[n+1]=0
i=n
ruiseki = [0]*(k)
for j in range(k):
	ruiseki[j] = dp[min(i+lr[j][0],n+1)]-dp[min(i+lr[j][1],n+1)]
#print(ruiseki)
ans = 0
for i in range(n-1,0,-1):
	t = 0
	for j in range(k):
		ll = dp[min(i+lr[j][0],n+1)]
		rr = dp[min(i+lr[j][1]+1,n+1)]
		#print(ll,rr)
		ruiseki[j] += ll-rr
	t+=sum(ruiseki)
	dp[i]=t%998244353
	#print(i,ruiseki,dp)

print(dp[1])

Submission status: Accepted

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

S = [ tuple( map(int, input().split()) ) for i in range(K)]
#print(S)

Ans = [0 for i in range(N)]
Ans[0] = 1
a = [0 for i in range(N)]
a[1] = -1
for i in range(1, N):
  for s in S:
    if i-1 + s[0] <= N-1:
      a[i-1 + s[0]] += Ans[i-1]
      a[i-1 + s[0]] %= 998244353
    if i + s[1] <= N-1:
      a[i + s[1]] -= Ans[i-1]
      a[i + s[1]] %= 998244353
  Ans[i] = (Ans[i-1] + a[i]) % 998244353
  
  #print(i, Ans[i])

print(Ans[N-1])

Submission status: Accepted

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

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

#A1～Aiまでの和 O(logN)
def BIT_query(idx):
  res_sum = 0
  while idx > 0:
    res_sum += BIT[idx]
    idx -= idx&(-idx)
  return res_sum
#Ai += x O(logN)
def BIT_update(idx,x):
  while idx <= N:
    BIT[idx] += x
    idx += idx&(-idx)
  return  

#初期化
BIT=[0]*(N+1)
BIT_update(1,1)

for i in range(2,N+1):
  for l,r in lrlist:
    left=i-r
    right=i-l    
    if right<1:
      continue
    elif left<1:
      left=1
    
    sum_intv=BIT_query(right)-BIT_query(left-1)
    BIT_update(i,sum_intv)
    
  nomod=BIT_query(i)-BIT_query(i-1)
  BIT_update(i,nomod%MOD-nomod)
    
print(BIT_query(N)-BIT_query(N-1))

Submission status: Accepted

Solution code:
import sys;input=sys.stdin.readline
class Bit:
    def __init__(self, n):
        self.size = n
        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.size:
            self.tree[i] += x
            i += i & -i

N, K = map(int, input().split())
mod=998244353
X = []
rs = []
for _ in range(K):
    l, r = map(int, input().split())
    rs.append((l, r))
st = Bit(N)
st.add(1, 1)
for i in range(2, N+1):
    t = 0
    for l, r in rs:
        if i-l<1:
            continue
        t += st.sum(i-l) - st.sum(max(i-r-1, 0))
        t%=mod
    st.add(i, t)
print((st.sum(N)-st.sum(N-1))%mod)

Submission status: Accepted

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

region = []
mod = 998244353

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

cnt = [0] * (n + 1)
cnt[0] = 0
imos = [0] * (n + 1)
imos[0] = 1

for i in range(n):

    if i - 1 >= 0:
        cnt[i] = cnt[i - 1] + imos[i]
        cnt[i] %= mod
    for l, r in region:
        if i + l < n:
            imos[i + l] += cnt[i] if i != 0 else 1
            imos[i + l] %= mod

        if i + r + 1 < n:
            imos[i + r + 1] -= cnt[i] if i != 0 else 1
            imos[i + l + 1] %= mod

print(cnt[n - 1] % mod)

Submission status: Accepted

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


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

LR.sort()

memo = [0] * (n + 1)
memo[1] = 1
cummemo = [0] * (n + 1)
cummemo[1] = 1
for i in range(1, n):
    ni = i + 1
    for l, r in LR:
        # print(ni, l, r)
        if ni - l > 0:
            memo[ni] += cummemo[ni - l]
        if ni - (r + 1) > 0:
            memo[ni] -= cummemo[ni - (r + 1)]
    memo[ni] %= mod
    cummemo[ni] = cummemo[ni - 1] + memo[ni]
    cummemo[ni] %= mod
print((cummemo[n] - cummemo[n - 1]) % mod)

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
mod = 998244353
from collections import defaultdict

def solve():
    n,K = map(int,input().split())
    step = [tuple(map(int,inp.split())) for inp in stdin.read().splitlines()]
    dp=defaultdict(int)

    f=0
    dp[1]=1
    for i in range(1,1+n):
        for r,l in step:
            f=(f+-dp[i-1-l]+dp[i-r])%mod
        dp[i]=(dp[i]+f)%mod
    print(dp[n])



if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 998244353

N, K = map(int, input().split())
segments = [tuple(map(int, input().split())) for _ in range(K)]
dp = [0] * (2 * N + 1)
for i in range(N):
    for s, t in segments:
        t += 1
        dp[i + s] += dp[i] if i != 0 else 1
        dp[i + t] -= dp[i] if i != 0 else 1
    dp[i + 1] += dp[i]
    dp[i + 1] %= MOD
print(dp[N - 1])

Submission status: Accepted

Solution code:
def getsum(BITTree, i):
    s = 0  # initialize result

    # index in BITree[] is 1 more than the index in arr[]
    i = i + 1

    # Traverse ancestors of BITree[index]
    while i > 0:
        # Add current element of BITree to sum
        s += BITTree[i]

        # Move index to parent node in getSum View
        i -= i & (-i)
    return s


# Updates a node in Binary Index Tree (BITree) at given index
# in BITree. The given value 'val' is added to BITree[i] and
# all of its ancestors in tree.
def updatebit(BITTree, n, i, v):
    # index in BITree[] is 1 more than the index in arr[]
    i += 1

    # Traverse all ancestors and add 'val'
    while i <= n:
        # Add 'val' to current node of BI Tree
        BITTree[i] += v

        # Update index to that of parent in update View
        i += i & (-i)

    # Constructs and returns a Binary Indexed Tree for given


# array of size n.
def construct(arr, n):
    # Create and initialize BITree[] as 0
    BITTree = [0] * (n + 1)

    # Store the actual values in BITree[] using update()
    for i in range(n):
        updatebit(BITTree, n, i, arr[i])

        # Uncomment below lines to see contents of BITree[]
    # for i in range(1,n+1):
    #     print BITTree[i],
    return BITTree


n,k=map(int,input().split())
c=[]
a=[0]*(n+1)
a[1]=1
BITTree = construct(a,len(a))
mod=998244353
for i in range(k):
    x,y=map(int,input().split())
    c.append([x,y])

for i in range(2,n+1):
    for j in range(len(c)):
        p,q=c[j][0],c[j][1]
        if i-q>0:
            l,r=i-p,i-q

            z=(getsum(BITTree,l)-getsum(BITTree,r-1))%mod

            a[i]+=z
            updatebit(BITTree, len(a), i,z)

        else:
            q=i-1
            if i-q>0 and i-p>0:
                l, r = i - p, i - q

                z = (getsum(BITTree, l) - getsum(BITTree, r - 1))%mod
                ##z= getsum(BITTree, q) - getsum(BITTree, p - 1)
                ##print(z)
                a[i]+=z
                updatebit(BITTree, len(a), i, z)
                ##print(BITTree)

##print(a)
print(a[n]%mod)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
st = []
for i in range(k):
  x,y = map(int,input().split())
  st.append((x,y))
total = [1]
 
for i in range(1,n):
  s = 0
  for (x,y) in st:
    if i > y:
      s = (s + total[i-x] - total[i-y-1]) % 998244353
    elif i >= x:
      s = (s + total[i-x]) % 998244353
  total.append((s+total[-1]) % 998244353)   
  
print((total[-1]-total[-2]) % 998244353)

Submission status: Accepted

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

def main():
    mod=998244353
    n,k=map(int,input().split())
    LR=[list(map(int,input().split())) for _ in range(k)]
    DP=[0]*n
    Acc=[0]*(n+1)
    DP[0]=1
    Acc[1]=1
    for i in range(1,n):
        for l,r in LR:
            if l>i:
                continue
            left=max(0,i-r)
            right=i-l
            DP[i]+=Acc[right+1]-Acc[left]
        DP[i]%=mod
        Acc[i+1]=Acc[i]+DP[i]
    print(DP[-1])
    #print(DP)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
dp=defaultdict(int)
mod1,mod2=10**9+7,998244353
mod=mod2

n,k=map(int,input().split())
f=0
dp[1]=1
ls=[tuple(map(int,input().split())) for i in range(k)]

#   [i-1-l,i-1-r]
#   [ i-l, i-r ]
for i in range(1,1+n):
    for r,l in ls:
        f=(f+-dp[i-1-l]+dp[i-r])%mod
    dp[i]=(dp[i]+f)%mod
print(dp[n])

Submission status: Accepted

Solution code:
class BIT:
    """
    Binary Index Tree
    ###1-origin####

    add :L[i]+=x
    sum: sum(L[:l])
    range_sum : sum(L[l:r])

    #material http://hos.ac/slides/20140319_bit.pdf
    """

    def __init__(self, N, init_val=0):
        self.init_val = init_val
        self.size = N
        self.L = [init_val]*(N+1)

    def sum(self, r):
        """
        sum[,r)
        calc sum from L[0] to L[r-1]
        """
        ret = self.init_val
        while r > 0:
            ret += self.L[r]
            r -= r & (-r)

        return ret

    def range_sum(self, l, r):
        
        """
        idx周りが怪しい?
        sum[l,r)
        calc sum from L[l] to L[r-1]
        """
        return self.sum(r-1)-self.sum(l-1)

    def add(self, i, x):
        """
        L[i] += x
        """
        while i <= self.size:
            self.L[i] += x
            i += i & (-i)

    def bisect(self,k:float)->int:
        """ binary search on BIT
        get index x s.t self.sum(,)>=k

        RETURN:
            res:index of x
        """
        k+=1 #convert k into 1-index

        res=0
        N=1
        while N<self.size:
            N*=2

        i=N//2
        while i>0:
            if(res+i<self.size and self.L[res+i]<k): #move to rignt on tree
                k-=self.L[res+i]
                res+=i
            #else move to left
            i//=2
        return res+1
N,K = map(int,input().split())
MOD=998244353
ranges=[list(map(lambda x:int(x),input().split())) for _ in range(K)]


B=BIT(N+1)
dist=[0]*(N+1)

B.add(1,1)
dist[1]=1

for i in range(2,N+1):
    for l,r in ranges:
        left=min(max(i-l,0),N)
        right=min(max(i-r,0),N)
        dist[i]+=B.range_sum(right,left+1)
    dist[i]%=MOD
    B.add(i,dist[i])


print(dist[-1]%MOD)

Submission status: Accepted

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

s = [0 for _ in range(n + 1)]
s[1] = 1
for i in range(1, n):
    s[i + 1] = s[i]
    for l, r in seg:
        s[i + 1] += (s[max(0, i - l + 1)] - s[max(0, i - r)]) % MOD
        s[i + 1] %= MOD
print((s[n] - s[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

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

ruidp = [0] * (n + 1)
ruidp[1] = 1


for i in range(n):
  for l, r in LR:
    dp[i] += (ruidp[max(i - l + 1, 0)] - ruidp[max(i - r, 0)])
    dp[i] %= MOD
  ruidp[i + 1] = ruidp[i] + dp[i] 
  ruidp[i + 1] %= MOD

print(dp[-1])

Submission status: Accepted

Solution code:
from math import floor,ceil,sqrt
import fractions
from collections import deque
import itertools
import collections
from heapq import *
N,K=map(int,input().split())
lr=[list(map(int,input().split())) for _ in range(K)]
ans=[0]*N
ans[0]=1
p=998244353
  
"""
print(ans)
for j in range(K):
    l = lr[j][0]
    r = lr[j][1]
    if l < N:
        ans[l] = ans[l] + 1
    if r + 1 < N:
        ans[r + 1] = ans[r + 1] - 1
print(ans)
print()
"""
for i in range(N):
    #print(ans)
    #print(i)
    for j in range(K):
        l = i+lr[j][0]
        r = i+lr[j][1]
        #print(l,r)
        if l < N:
            ans[l] = ans[l] + ans[i]
        if r + 1 < N:
            ans[r + 1] = ans[r + 1] - ans[i]
    #print(ans)
    ans[0]=0
    if i<N-1:
        ans[i+1]=(ans[i+1]+ans[i])%p
    #print(ans)
    #print()
print(ans[N-1])

Submission status: Accepted

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
from decimal import Decimal
# from fractions import Fraction
# sys.setrecursionlimit(100000)
mod = 998244353
INF=float('inf')

n,k=mdata()
set1=set()
dp=[0]*(n)
s=[0]*n
lis=sorted([mdata() for i in range(k)],key=lambda x:x[0])
for i,j in lis:
    for m in range(i,j+1):
        set1.add(m)
m=lis[0][0]
for i in range(m,n):
    for j in range(k):
        if lis[j][0]>=i:
            break
        dp[i]+=s[i-lis[j][0]]-s[i-min(lis[j][1],i-1)-1]
    if i in set1:
        dp[i]+=1
    dp[i]%=mod
    s[i]=dp[i]+s[i-1]
out(dp[-1])