Problem:


Score : 400 points

Problem Statement

There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.

Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.

You are given an integer K that is less than or equal to 10, and K non-intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K].
Let S be the union of these K segments.
Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.

When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.

To help Tak, find the number of ways to go to Cell N, modulo 998244353.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq K \leq \min(N, 10)

1 \leq L_i \leq R_i \leq N

[L_i, R_i] and [L_j, R_j] do not intersect (i \neq j) 

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
L_1 R_1
L_2 R_2
:
L_K R_K

Output

Print the number of ways for Tak to go from Cell 1 to Cell N, modulo 998244353.

Sample Input 1

5 2
1 1
3 4

Sample Output 1

4

The set S is the union of the segment [1, 1] and the segment [3, 4], therefore S = \{ 1, 3, 4 \} holds.

There are 4 possible ways to get to Cell 5:

1 \to 2 \to 3 \to 4 \to 5,

1 \to 2 \to 5,

1 \to 4 \to 5 and

1 \to 5.

Sample Input 2

5 2
3 3
5 5

Sample Output 2

0

Because S = \{ 3, 5 \} holds, you cannot reach to Cell 5.
Print 0.

Sample Input 3

5 1
1 2

Sample Output 3

5

Sample Input 4

60 3
5 8
1 3
10 15

Sample Output 4

221823067

Note that you have to print the answer modulo 998244353.



Sample input:
5 2
1 1
3 4


Sample output:
4

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=998244353
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,K=map(int,input().split())
L,R=[0]*K,[0]*K
for i in range(K):
    L[i],R[i]=map(int,input().split())
    R[i]+=1

class RangeBIT:
    def __init__(self,n):
        self.p=self.BIT(n+1)
        self.q=self.BIT(n+1)
    
    def add(self,s,t,x):
        self.p.add(s,-x*s)
        self.p.add(t,x*t)
        self.q.add(s,x)
        self.q.add(t,-x)
    
    def sum(self,s,t):
        return self.p.sum(t)+self.q.sum(t)*t-self.p.sum(s)-self.q.sum(s)*s
    
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s

b=RangeBIT(N)
b.add(0,1,1)
for i in range(N):
    res=b.sum(i,i+1)%MOD
    for l,r in zip(L,R):
        if i+l<N:
            b.add(i+l,min(i+r,N),res)
print(b.sum(N-1,N)%MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from math import gcd
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]




class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def interval_sum(self, i, j): # i <= x < j の区間
        return self.sum(j - 1) - self.sum(i - 1) if i else self.sum(j - 1)


mod=998244353
n,k=LI()
lr=LIR(k)
bit=BIT(n+1)
bit.add(0,1)
for i in range(n):
    ret=0
    for j in range(k):
        l,r=lr[j]
        if i-l+1>0:
            ret+=bit.interval_sum(max(i-r,0),i-l+1)
    bit.add(i,ret%mod)
    ans=ret%mod

print(ans)

Submission status: Accepted

Solution code:


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

D = []

for i in range(K):
    l,r = list(map(int,input().split()))
    D.append((l,"l"))
    D.append((r,"r"))

D.sort(key=lambda x:x[0])
mod = 998244353

DP = [0]*N

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

def max(a,b):
    if a>b:
        return a
    else:
        return b

def S(x,y):
    return DPP[max(y,0)] - DPP[max(x-1,0)]


for i in range(N-1):
    a = 0
    for j in range(len(D)//2):
        a += S(i+2 - D[2*j+1][0], i+2 - D[2*j][0])
        a %= mod
    DP[i+1] = a
    DPP[i+2] = (a + DPP[i+1])%mod

print(DP[-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

class BIT:
    #n:要素数
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    #i番目(0-indexed)の値にxを足す
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] = (x+self.bit[i])%MOD
            i += i&(-i)

    #sum[0:i)
    def acc(self, i):
        s = 0
        
        while i>0:
            s = (s+self.bit[i])%MOD
            i -= i&(-i)
        
        return s

N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(K)]
MOD = 998244353
bit = BIT(N)
bit.add(0, 1)
bit.add(1, -1)

for i in range(N):
    now = bit.acc(i+1)
    #print(i, now)
    
    for L, R in LR:
        if i+L<N:
            bit.add(i+L, now)
        
        if i+R<N:
            bit.add(i+R+1, -now)

print(bit.acc(N))

Submission status: Accepted

Solution code:
# >>> numba compile >>>
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)
# <<< numba compile <<<

import sys
import numpy as np

mod = 998244353
def solve(N, K, LR):
    dp = np.zeros(N+1, dtype=np.int64)
    cum = np.zeros(N+1, dtype=np.int64)
    dp[1] = 1
    cum[1] = 1
    for i in range(2, N+1):
        d = 0
        for idx_LR in range(K):
            l, r = LR[idx_LR]
            ll = max(0, i - l)
            rr = max(0, i - r - 1)
            d += cum[ll] - cum[rr]
        d %= mod
        dp[i] = d
        cum[i] = (cum[i-1] + d) % mod
    return dp[N]

numba_compile([
    [solve, "i8(i8,i8,i8[:,:])"],
])

def main():
    N, K = map(int, sys.stdin.buffer.readline().split())
    LR = np.array(sys.stdin.buffer.read().split(), dtype=np.int64).reshape(K, 2)
    ans = solve(N, K, LR)
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 998244353


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.step = pow(2, n.bit_length() - 1)

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

    def get_sum(self, i):
        i += 1
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i & -i
        return x

    # Return sum for [l, r)
    def get_sum_range(self, l, r):
        return self.get_sum(r - 1) - self.get_sum(l - 1)


def main():
    N, K, *LR = map(int, read().split())

    interval = [(l, r) for l, r in zip(*[iter(LR)] * 2)]

    bit = BIT(N + 2)
    bit.add(1, 1)
    bit.add(2, -1)

    for i in range(N):
        cur = bit.get_sum(i) % MOD
        for l, r in interval:
            bit.add(i + l, cur)
            bit.add(i + r + 1, -cur)

    print(bit.get_sum(N) % MOD)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ruiseki=[0]*n
ruiseki[0]=1

for i in range(1,n):
    ruiseki[i]=ruiseki[i-1]
    for j in range(k):
        if(i<idou[j][0]):
            continue
        hiku=0
        if(i>idou[j][1]):
            hiku=ruiseki[i-idou[j][1]-1]
        #print(i,hiku,ruiseki)
        ruiseki[i]+=(p+ruiseki[i-idou[j][0]]-hiku)%p
        ruiseki[i]%=p

#print(ruiseki)

print((p+ruiseki[-1]-ruiseki[-2])%p)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


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

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

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

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

Submission status: Accepted

Solution code:
# by the authority of GOD     author: manhar singh sachdev #

import os,sys
from io import BytesIO, IOBase

def main():
    mod = 998244353
    n,k = map(int,input().split())
    su = [0,1]
    dp = [0]+[1]+[0]*(n-1)
    ra = []
    for _ in range(k):
        ra.append(tuple(map(int,input().split())))
    for i in range(2,n+1):
        for y in ra:
            if y[0]>i:
                continue
            aa,bb = i-y[0],max(i-y[1],1)
            dp[i] += (su[aa]-su[bb-1])%mod
            dp[i] %= mod
        su.append((su[-1]+dp[i])%mod)
    print(dp[-1])


    
#Fast IO Region
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
l=input().split()
n=int(l[0])
k=int(l[1])
tot=[]
for i in range(k):
    l=input().split()
    li=[int(i) for i in l]
    tot.append(li)
dp=[0 for i in range(n)]
pref=[1]
dp[0]=1
sumi=1
for i in range(1,n):
    for j in range(k):
        r=tot[j][1]
        l=tot[j][0]
        if(i-l>=0):
            dp[i]+=pref[i-l]
        if(i-r-1>=0):
            dp[i]-=pref[i-r-1]
    dp[i]%=998244353
    sumi+=dp[i]
    sumi%=998244353
    pref.append(sumi)
#print(dp)
#print(pref)
print(dp[-1])

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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 998244353
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

N,K = IL()
data = ILL(K)
data.sort()

class SegmentTree:
  def __init__(self, n, e):
    self.n = n
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
 
  def get(self, i):
    i += self.size
    ret = self.node[i]
    while i > 1:
      i >>= 1
      ret += self.node[i]
    return ret
 
  def add(self, l, r, val):
    l, r = l + self.size, r + self.size
    while l < r:
      if l & 1:
        self.node[l] += val
        self.node[l] %= MOD
        l += 1
      if r & 1:
        r -= 1
        self.node[r] += val
        self.node[r] %= MOD
      l, r = l >> 1, r >> 1
      
ST = SegmentTree(N+10,0)
ST.add(1,2,1)

for i in range(1,N):
  for k in range(K):
    l,r = data[k]
    if i+l <= N:
      ST.add(i+l,min(i+r+1,N+1),ST.get(i))

print(ST.get(N)%MOD)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

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

MOD = 998_244_353

@njit((i8, i8[:]), cache=True)
def main(N, LR):
    L, R = LR[::2], LR[1::2]
    K = len(L)
    F = np.zeros(N + 10, np.int64)
    F[0] = 1
    for n in range(1, N + 10):
        F[n] += F[n - 1]
        for k in range(K):
            l, r = L[k], R[k] + 1
            if n - l >= 0:
                F[n] += F[n - l]
            if n - r >= 0:
                F[n] -= F[n - r]
        F[n] %= MOD
    ans = F[N - 1] - F[N - 2]
    return ans % MOD

N, K = map(int, readline().split())
LR = np.array(read().split(), np.int64)

print(main(N, LR))

Submission status: Accepted

Solution code:
import sys
import re
import random
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def solve():
    MOD = 998244353
    n, k = getList()
    imos = [0] * (n + 10)
    imos[2] = -1
    kukan = [getList() for i in range(k)]

    ans = 1
    for i in range(1, n+1):
        ans += imos[i]
        for l, r in kukan:
            l, r = min(i+l, n+2), min(i+r, n+2)
            imos[l] += ans
            imos[r+1] -= ans
        ans %= MOD
    
    print(ans % MOD)


def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
MOD = 998244353
N, K = map(int, input().split())
LRs = []
sums = []
for _ in range(K):
    l, r = map(int, input().split())
    LRs.append([l, r])
    sums.append(1 if l <= 1 <= r else 0)

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

for i in range(2, N+1):
    dp[i] = sum(sums) % MOD
    for k in range(K):
        l, r = LRs[k]
        sums[k] = (sums[k] + dp[i-l+1] - dp[i-r]) % MOD
print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
lr = []
for _ in range(k):
  lr.append(list(map(int,input().split())))
#print(lr)
imos = [0 for _ in range(n)]
imos[0] = 1
imos[1] = -1
now = 0
mod = 998244353
for i in range(n):
    now += imos[i]
    now %= mod
    #print(now)
    for j in range(k):
        try:
            imos[i+lr[j][0]] += now
            imos[i+lr[j][0]] %= mod
        except:
            pass
        try:
            imos[i+lr[j][1]+1] -= now
            imos[i+lr[j][1]+1] %= mod
        except:
            pass
    #print(imos)
print(now)

Submission status: Accepted

Solution code:
n,k=[int(i) for i in raw_input().split()]
l=[[int(i) for i in raw_input().split()]for j in range(k)]
dp=[0 for i in range(n+1)]
dp[1]=1
dp1=[0 for i in range(n+1)]
dp1[1]=1
m=998244353
for i in range(2,n+1):
    dp1[i]=dp1[i-1]
    for j in l:
        if(i-j[1]>0):
            dp[i]+=dp1[i-j[0]]-dp1[i-j[1]-1]
        else:
            dp[i]+=dp1[i-j[0]]
    dp1[i]+=dp[i]
    dp1[i]%=m
    dp[i]%=m
print dp[n]%m

Submission status: Accepted

Solution code:
def main():
    examD()

def examA():
    S = SI()
    if S[-1]=="s":
        ans = S+"es"
    else:
        ans = S+"s"
    print(ans)
    return

def examB():
    N = I()
    D = [LI()for _ in range(N)]
    current = 0
    for d1,d2 in D:
        if d1==d2:
            current += 1
        else:
            current = 0
        if current==3:
            print("Yes")
            return
    print("No")
    return

def examC():
    N = I()
    cnt = 0
    for i in range(1,N):
        for j in range(1,1+N//i-(N%i==0)):
            cnt += 1
    ans = cnt
    print(ans)
    return

def examD():
    N, K = LI()
    LR = [LI()for _ in range(K)]
    dp = [0]*N
    S = [0]*N
    dp[0] = 1
    S[0] = 1
    for i in range(1,N):
        cur = 0
        for l,r in LR:
            if i<l:
                continue
            cur += S[i-l]
            if i<r+1:
                continue
            cur -= S[i-r-1]
            cur += mod2
            cur %= mod2

        dp[i] = cur
        S[i] = S[i-1] + cur
        S[i] %= mod2

    ans = dp[-1]
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,alphabet_convert,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<31
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    main()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

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

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

step = [0 for _ in range(N)]
step[0] = 1
step[1] = -1
answer = 0

for i in range(N):
  answer = (answer+step[i])%mod
  for L,R in LR:
    if i+L < N:
      step[i+L] += answer
    if i+R+1 < N:
      step[i+R+1] -= answer

print((answer)%mod)

Submission status: Accepted

Solution code:
MOD = 998244353
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

N,K = map(int,input().split())
f = lambda x: (int(x[0]),int(x[1])+1)
lr = [f(input().split()) for _ in range(K)]

dp = [0]*(N+1)

dp[1] = 1

for i in range(2,N+1):
    t = 0
    for l,r in lr:
        if l > i:
            continue
        a = i - l
        b = max2(0, i - r)
        t += dp[a] - dp[b]
    dp[i] = (dp[i-1]+t)%MOD
print((dp[-1]-dp[-2])%MOD)

Submission status: Accepted

Solution code:

mod = 998244353

class BIT():

    __slots__ = ["n", "data"]

    def __init__(self, li):
        self.n = len(li) + 1
        self.data = [1] + li
        for i in range(1, self.n):
            if i + (i & -i) < self.n:
                self.data[i + (i & -i)] += self.data[i]

    def add(self, i, a):
        i += 1
        while i < self.n:
            self.data[i] += a
            self.data[i] %= mod
            i += i & -i
        
    def acc(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            res %= mod
            i -= i & -i
        return res
    
    def fold(self, l, r):
        res = 0
        while l < r:
            res += self.data[r]
            r -= r & -r
            res %= mod
        while r < l:
            res -= self.data[l]
            l -= l & -l
            res %= mod
        return res
        
        
n, k = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(k)]
dp = BIT([0]*n)
dp.add(0, 1)
for i in range(1, n):
    for l, r in LR:
        dp.add(i, dp.fold(max(i-r, 0), max(i-l+1, 0)))
ans = dp.fold(n-1, n)
print(ans)

Submission status: Accepted

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

M = 998244353
T = [0]*N
T[0] = 1
s = 0
for i in range(N):
  s += T[i]
  for j in range(K):
    if i+L[j]<N:
      T[i+L[j]] += s
      T[i+L[j]] %= M
    if i+R[j]<N:
      T[i+R[j]] -= s
      T[i+R[j]] %= M

print(T[-1])

Submission status: Accepted

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


class BinaryIndexedTree:
    """一点加算、区間総和クエリをそれぞれO(logN)で答えるデータ構造。"""
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def build(self, array):
        """arrayを初期値とするBinaryIndexedTreeを構築する。O(N)"""
        for i, val in enumerate(array):
            self.bit[i + 1] = val
        for i in range(1, self.size):
            if i + (i & -i) > self.size:
                continue
            self.bit[i + (i & -i)] += self.bit[i]

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s % MOD

    def add(self, i, val):
        """i番目の要素にvalを加算する。O(logN)"""
        i += 1
        while i <= self.size:
            self.bit[i] += val
            self.bit[i] %= MOD
            i += i & -i

    def sum(self, l, r):
        """区間[l, r)の和を求める。O(logN)"""
        return (self._sum(r) - self._sum(l)) % MOD


n, k = map(int, input().split())
dist = [list(map(int, input().split())) for i in range(k)]
MOD = 998244353


bit = BinaryIndexedTree(n + 1)
bit.add(1, 1)

for i in range(2, n + 1):
    ptn = 0
    for l0, r0 in dist:
        l = i - r0
        r = i - l0 + 1
        l, r = max(l, 0), max(r, 0)
        ptn += bit.sum(l, r)
    bit.add(i, ptn)
    
print(bit.sum(n, n + 1) % MOD)

Submission status: Accepted

Solution code:
MOD = 998244353

def main():
    n, k = map(int, input().split())
    rng = [list(map(int, input().split())) for _ in range(k)]
    dp = [0]*(n+5)
    dp[1] = 1
    for i in range(1, n):
        dp[i] += dp[i-1]
        dp[i] %= MOD
        for l, r in rng:
            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)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

DP=[0]*(4*10**5+100)
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 K:
        DP[i+l]+=DP[i]
        DP[i+l]%=mod
        DP[i+r+1]-=DP[i]
        DP[i+r+1]%=mod
        

    #print(DP[:10])

print(DP[N])

Submission status: Accepted

Solution code:
p = 998244353
n, k = [int(i) for i in input().split(" ")]
n -= 1
a = [[0, 0] for i in range(k)]
for i in range(k):
  a[i] = [int(j) for j in input().split(" ")]
dp = [0] * (n+10)
cum = [0] * (n+10)
dp[0] = 1
cum[0] = 1

for i in range(1, n+1):
  for j in range(k):
    fi = i - a[j][1]
    se = i - a[j][0]
    if se < 0:
      continue
    if fi < 0:
      fi = 0
    if fi == 0:
      dp[i] = (dp[i] + cum[se]) % p
    else:
      dp[i] = (dp[i] + cum[se] - cum[fi-1]) % p
  cum[i] = (cum[i-1] + dp[i]) % p

# print(dp[n] % p)
# print(dp)
# print(cum)
print(dp[n] % p)

Submission status: Accepted

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

MOD = 998244353

dp = [0] * (N + 1)
dp_csum = [0] * (N + 2)
dp[1] = 1
dp_csum[2] = 1
for i in range(2, N + 1):
    for L, R in LRs:
        dp[i] += dp_csum[max(0, i - L + 1)] - dp_csum[max(0, i - R)]
        dp[i] %= MOD
    dp_csum[i + 1] = dp_csum[i] + dp[i]
    dp_csum[i + 1] %= MOD

# print(dp)
# print(dp_csum)

print(dp[N])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,q = map(int, readline().split())
#*a, = map(int, readline().split())

def get(i,l,r):
    a = i-r
    b = i-l
    if b < 0: return 0
    return acc[b] - (acc[a-1] if a-1 >= 0 else 0)



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

dp = [0]*(n)
dp[0] = 1
acc = [1]*(n)


MOD = 998244353
for i in range(1,n):
    v = 0
    for l,r in lr:
        v += get(i,l,r)
    dp[i] = v%MOD
    acc[i] = (acc[i-1] + dp[i])%MOD
    #print(dp,acc)

print(dp[n-1]%MOD)