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:
mod = 998244353
def main():
  n, k =  map(int, input().split())
  query= []
  for i in range(k):
    query.append(list(map(int, input().split())))
  dp = [0]*(n + 1)
  dp[1] = 1
  for i in range(2, n+1):
    dp[i] += dp[i-1]
    for lr in query:
      if i-lr[0] <= 0:
        continue
      else:
        dp[i] += dp[i-lr[0]]-dp[max(0, i-lr[1]-1)]
        dp[i] %= mod
  print((dp[n]-dp[n-1])%mod)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
MOD = 998244353
N, K = map(int, input().split())
L = []
R = []
for k in range(K):
    l, r = map(int, input().split())
    L += [l]
    R += [r]
# memo = [[0 for i in range(N+2)] for k in range(K)]
memo = [0 for i in range(N+2)]
memo[1] = 1
memo[2] = -1
cusum = 0
for i in range(1, N+1):
    cusum = (cusum + memo[i]) % MOD
    # print(cusum)
    for k in range(K):
        l, r = L[k], R[k]
        # for j in range(i+l, min(i+r+1, N+1)):
        #     memo[j] += memo[i]
        memo[min(i+l, N+1)] += cusum
        memo[min(i+r+1, N+1)] -= cusum
    # print(memo)
# for i in range(1, N+1):
#     for k in range(K):
#         memo[k][i+1] += memo[k][i]
print(cusum % MOD)

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

M = 998244353
n,k = ip()
seg = [ip() for i in range(k)]
dp = [0]*(n+1)
pre = [0]*(n+1)

dp[1] = 1
pre[1] = 1
for i in range(2,n+1):
    for l,r in seg:
        a,b = max(i-r,1),i-l
        dp[i] += (pre[b] - pre[a-1])%M
    pre[i] += (pre[i-1]+dp[i])%M
print(dp[n]%M)

Submission status: Accepted

Solution code:
import math
import collections
def main():

    N, K = map(int, input().split())
    mod = 998244353
    d = dict()
    cnt = collections.defaultdict(int)
    for _ in range(K):
        l, r = map(int, input().split())
        d[(1-r, 1-l)] = 0
    cnt[1] = 1

    for i in range(2, N+1):
        temp = dict()
        for p in d:
            if p[1]+1 <= N:
                temp[(p[0]+1, p[1]+1)] = d[p]
                if p[0] in cnt: temp[(p[0]+1, p[1]+1)] -= cnt[p[0]]
                if p[1]+1 in cnt: temp[(p[0]+1, p[1]+1)] += cnt[p[1]+1]
            else:
                temp[(p[0]+1, N)] = d[p]
                if p[0] in cnt: temp[(p[0]+1, p[1]+1)] -= cnt[p[0]]
        d = temp
        # print(d)
        cnt[i] = sum(d[v] for v in d) % mod
        # print(cnt)
    return cnt[N]



if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import sys

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

class SegmentTree:
    def __init__(self, n, segfunc=min, ele=10**10):
        self.ide_ele = ele
        self.num = pow(2, (n-1).bit_length())
        self.seg = [self.ide_ele] * 2 * self.num
        self.segfunc = segfunc

    def init(self, init_val):
        #set_val
        for i in range(len(init_val)):
            self.seg[i+self.num-1] = init_val[i]
        #built
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])

    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])

    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p > 1:
            if p & 1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q & 1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res


dp = SegmentTree(N, segfunc=lambda x, y: x+y%P, ele=0)
dp.update(0, 1)
for i in range(1, N):
    tmp = 0
    for l, r in LR:
        tmp = (tmp + dp.query(max(0, i - r), max(0, i - l + 1)))%P
    dp.update(i, tmp)
print(dp.seg[N - 1 + dp.num - 1])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
import sys
mod=998244353 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
from fractions import Fraction as frac  #frac(a,b)で正確なa/b
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

dp=[0]*(n*2+10)
#dp[0]=1
S=[0]*(n*2+10)
K=[list(map(int,input().split())) for i in range(k)]
for x,y in K:
  S[x]+=1
  S[y+1]-=1
#print(S)
for i in range(1,n):
    dp[i]= (dp[i-1]+S[i])%mod
    if dp[i]==0:continue
    for x,y in K:
        S[i+x]+= dp[i] % mod
        S[i+y+1]-= dp[i] % mod
#print(K,dp)
print(dp[n-1]%mod)

Submission status: Accepted

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

dp = [0] * (2*n+1)
dp_cumsum = [0] * (2*n+1)
mod = 998244353

dp[n+1] = 1
dp_cumsum[n+1] = 1

for idx in range(n+2, 2*n+1):
    for l, r in period:
        # dp[idx - r] 〜dp[idx - l]までの和
        dp[idx] += dp_cumsum[idx - l] - dp_cumsum[idx - r - 1]

    dp[idx] %= mod
    dp_cumsum[idx] = (dp_cumsum[idx-1] + dp[idx]) % mod

print(dp[n+n])
# print(dp)
# print(dp_cumsum)

Submission status: Accepted

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

MOD = 998244353
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
            self.tree[i] %= MOD
            i += i & -i

def main():
    n, k = map(int, input().split())
    lr = [list(map(int, input().split())) for _ in range(k)]
    bit = Bit(n + 1)
    bit.add(1, 1)
    for i in range(2, n + 2):
        for l, r in lr:
            plus = bit.sum(i - l) - bit.sum(i - r - 1)
            bit.add(i, plus)
    
    print((bit.sum(n) - bit.sum(n - 1)) % MOD)
    
main()

Submission status: Accepted

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


mod=998244353
# dp[i]:i番目のマスへの行き方
dp=[0]*(n+6)

for j in range(k):
    l = a[j][0]
    r = a[j][1]
    dp[l+1] += 1
    dp[r+2] -= 1


for i in range(1,n+1):
    dp[i+1]+=dp[i]
    dp[i+1]%=mod
    x=dp[i+1]
    for j in range(k):
        l=a[j][0]
        r=a[j][1]
        if l+i<=n:
            dp[i + l + 1] += x
        if r+i<=n:
            dp[i + 2 + r] -= x



print(dp[n]%mod)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=[list(map(int,input().split())) for i in range(k)]
x=[0]*(n+1)
x[0]=1
l.sort()
t=0
for i in range(1,n+1):
    for j in range(k):
        if i-l[j][1]>0:
            t+=x[i-l[j][0]]-x[i-l[j][1]-1]
        elif i-l[j][0]>=0:
            t+=x[i-l[j][0]]
        t=t%998244353
        x[i]=t
print(x[n-1])

Submission status: Accepted

Solution code:
# https://ikatakos.com/pot/programming_algorithm/data_structure/binary_indexed_tree

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

class RangeUpdate:
    def __init__(self, n):
        self.p = Bit(n + 1)
        self.q = Bit(n + 1)

    def add(self, s, t, x):
        t += 1
        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):
        t += 1
        return (self.p.sum(t) + self.q.sum(t) * t - \
               self.p.sum(s) - self.q.sum(s) * s) % mod


mod = 998244353

N, K, *LR = map(int, open(0).read().split())

LR = list(zip(*[iter(LR)] * 2))

dp = RangeUpdate(N)
dp.add(1, 1, 1)
for i in range(1, N + 1):
    for l, r in LR:
        dp.add(i + l, i + r, dp.sum(i, i))

print(dp.sum(N, N))

Submission status: Accepted

Solution code:
import sys
N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]
MOD = 998244353

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

def add(k, x):
    while k <= N:
        dp[k] += x
        dp[k] %= MOD
        k += k & -k


def get(k):
    s = 0
    while k:
        s += dp[k]
        k -= k & -k
    return s

for i in range(1, N + 1):
    for l, r in X:
        add(i + l, get(i))
        add(i + r + 1, -get(i))

print(get(N) % MOD)

Submission status: Accepted

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


def read():
    N, K = map(int, input().strip().split())
    LR = []
    for i in range(K):
        l, r = map(int, input().strip().split())
        LR.append((l, r))
    return N, K, LR


def solve(N, K, LR, MOD=998244353):
    LR.sort()
    q = deque()
    for l, r in LR:
        for a in range(l, r+1):
            q.append(a)
    dp = [0 for i in range(N+1)]
    dp[1] = 1
    sdp = [0 for i in range(N+1)]
    sdp[1] = 1
    for i in range(2, N+1):
        for l, r in LR:
            a = max(1, i-r)
            b = min(i-l, i-1)
            if a <= b:
                dp[i] += sdp[b] - sdp[a-1]
                dp[i] %= MOD
        sdp[i] = sdp[i-1] + dp[i]
        sdp[i] %= MOD
    return dp[N]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

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

array = [0] * (n+1)

array[1] = 1

count = 0
for i in range(1, n+1):
  count += array[i]
  count %= MOD
  for j in range(k):
    if i + l[j] <= n:
      array[i+l[j]] += count
      array[i+l[j]] %= MOD
      
    if i + r[j] + 1 <= n:
      array[i+r[j]+1] -= count
      array[i+r[j]+1] %= MOD
      
print(array[-1])

Submission status: Accepted

Solution code:
def main():
    mod = 998244353
    N, K = map(int, input().split())
    LR = []
    for _ in range(K):
        l, r = map(int, input().split())
        LR.append((l, r))
    LR.sort()
    dp = [0] * N
    dp[0] = 1
    z = 0
    for i in range(1, N):
        for l, r in LR:
            if i - l >= 0:
                z += dp[i - l]
            if i - r - 1 >= 0:
                z -= dp[i - r - 1]
        z %= mod
        dp[i] = z

    return dp[-1]

print(main())

Submission status: Accepted

Solution code:


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

mod = 998244353

dp = [0] * N
dp[0] = 1

LR = [list(map(int, input().split())) for i in range(K)]
X = [0] * K

for i in range(1, N):
  for j in range(K):
    if i - LR[j][0] >= 0:
      X[j] += dp[i - LR[j][0]]
    if i - LR[j][1] > 0:
      X[j] -= dp[i - LR[j][1] - 1]
    X[j] %= mod
  dp[i] = sum(X) % mod
print(dp[-1])

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
# lr = [list(map(int,input().split())) for i in range(k)]
# imos = [0]*(n+1)
lr = [list(map(int,input().split())) for i in range(k)]
# for i in lr:
#     l,r = map(int,input().split())
#     imos[l] += 1
#     imos[r+1] -= 1
# print(imos)
mod = 998244353
temp = 0
dp = [0]*(2*n)
dp[n] = 1
s = [0]*n + [1]*n
# print(dp)
for i in range(n+1,2*n):
    for j in lr:
        dp[i] += (s[i-j[0]]-s[i-j[1]-1]) % mod
    s[i] = (dp[i] + s[i-1]) % mod
#     print("dp",dp)
#     print("ss",s)
# print(s)
print(dp[n*2-1] % mod)

Submission status: Accepted

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

S = []
for i in range(K):
  L, R = map(int, input().split())
  S.append((L, R))
dp = [0 for i in range(N+1)]
sumdp = [0 for i in range(N+1)]
sumdp[1] = 1
dp[1] = 1
for i in range(2,N+1):
  buf = 0
  for L, R in S:
    if i-L < 0:
      continue
    l = max(0, i-R-1)
    r = i-L
    #print(l,r,sumdp[r],sumdp[l])
    buf += sumdp[r]-sumdp[l]
    #print(i, buf)
    buf %= 998244353
  dp[i] = buf
  sumdp[i] = sumdp[i-1] + buf
  
print(dp[N])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
B=[[0]*2 for i in range(k)]
for i in range(k):
  B[i]=list(map(int,input().split()))
mod=998244353
A=[0]*(n+1)
A[0]=1
a=1
for i in range(n):
  for j in range(k):
    A[min(n,i+B[j][0])]=(A[min(n,i+B[j][0])]+a)%mod
    A[min(n,i+B[j][1]+1)]=(A[min(n,i+B[j][1]+1)]-a)%mod
  a=a+A[i+1]
print(A[-2]%mod)

Submission status: Accepted

Solution code:
#from bisect import bisect_left as bl                #c++ lowerbound bl(array,element)
#from bisect import bisect_right as br               #c++ upperbound br(array,element)
#from __future__ import print_function, division    #while using python2
# from itertools import accumulate
# from collections import defaultdict, Counter

def modinv(n,p):
    return pow(n,p-2,p)

def main():
    #sys.stdin = open('input.txt', 'r')
    #sys.stdout = open('output.txt', 'w')

    mod = 998244353
    dp = [0] * (200005)
    suffix = [0] * (200005)
    segments = []

    n, k = [int(x) for x in input().split()]
    for i in range(k):
        segments.append([int(x) for x in input().split()])

    segments.sort()

    dp[n] = 1
    suffix[n] = 1
    not_possible = False
    for x in range(n-1, 0, -1):
        for l, r in segments:
            if x + l > n:
                # suffix[x] = suffix[x+1]
                break
            if x + r > n:
                r = n - x
            # dp[x] = dp[x] + max(0, (suffix[x+l] - suffix[x+r+1]))
            # dp[x] %= mod
            # if(suffix[x+l] - suffix[x+r+1] > 0):
            dp[x] = (dp[x] + (suffix[x+l] - suffix[x+r+1])) % mod
            suffix[x] = (dp[x] + suffix[x+1]) % mod

            # print(x)
            # print(l, r)
            # print(dp[:n+1])
            # print(suffix[:n+1])
            # print()
        if suffix[x] == 0:
            suffix[x] = suffix[x+1]

    print(dp[1])

#------------------ Python 2 and 3 footer by Pajenegod and c1729-----------------------------------------
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            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:
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):
  for l,r in lrlist:
    left=i-r
    right=i-l    
    if right<1:
      continue
    elif left<1:
      left=1
    
    current=seg.query(i,i+1)
    sum_intv=seg.query(left,right+1)
    seg.update(i,(current+sum_intv)%MOD)
    #print(i,left,right,current,sum_intv)
    
print(seg.query(N,N+1))

Submission status: Accepted

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

mod = 998244353
dp = [0]*n
dp[0] = 1
s = 0
for i in range(1, n):
    for j in range(k):
        if i-lr[j][0] < 0:
            continue
        elif i-lr[j][1] <= 0:
            s = (s + dp[i-lr[j][0]]) % mod
        elif 0 < i-lr[j][1]:
            s = (s + dp[i-lr[j][0]] - dp[i-lr[j][1]-1]) % mod
    dp[i] = s
print(dp[-1])

Submission status: Accepted

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

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

for i in range(N):
    imos[i] += dp[i]
    if i != 0:
        tmp = imos[i]+tmp
    for k in range(K):
        l, r = lr[k]
        if l+i > N: continue
        dp[l+i] = (dp[l+i]+tmp)%mod
        dp[min(N, r+i+1)] = (dp[min(N, r+i+1)]-tmp)%mod
print(imos[N-1]%mod)

Submission status: Accepted

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


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

for i in range(K_o):
  L,R=map(int,input().split())
  for i in range(L,R+1):
    S.append(i)
  K.append([L,R])

bit=Bit(N+1)
bit.add(1,1)
bit.add(2,-1)
for i in range(N):
  for L,R in K:
    value_i=bit.sum(i)
    value_i%=mod
    bit.add(i+L,value_i)
    bit.add(i+R+1,value_i*-1)

print(bit.sum(N)%mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 19 20:18:10 2020

@author: liang
"""
#D
N, K = map(int, input().split())
areas = list()
for i in range(K):
    l, r = map(int,input().split())
    areas.append((l,r))
#areas_sum = [0] * N 
tmp = 0
d = [0] * N
#check = [0] * N
#check[0] = 1
d[0] = 1
for i in range(N):
    for j in range(K):
        l, r = areas[j]
        if i-l >= 0:
            #areas_sum[j] += d[i-l]
            tmp += d[i-l]
        if i-r-1 >= 0:
            #areas_sum[j] -= d[i-r-1]
            tmp -= d[i-r-1]
    d[i] += tmp
    #check[i] += tmp
    d[i] %= 998244353 
    tmp  %= 998244353 
    #t.append(tmp)

#print(d)
#print(check)
ans = d[N-1]
print(ans)
#print(tmp)

Submission status: Accepted

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

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

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

for i in range(1, n):
    thisTotal = 0
    for l, r in s:
        indL = i-l
        if indL >= 0:
            indR = max(0, i-r)

            thisTotal += totals[indL] - totals[indR-1]

    dp[i] = (thisTotal%m)
    totals[i] = (totals[i-1] + thisTotal)%m

print(dp[n-1])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
dp = [[0 for j in range(10)] for i in range(2 * 10 ** 5 + 10)]
sumdp = [0 for i in range(2 * 10 ** 5 + 10)]
sumdp[1] = 1
que = []
mod = 998244353

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

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

ans = sum(dp[N][i] for i in range(10))

print(ans % mod)

Submission status: Accepted

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

MOD = 998244353
dp = [0] * (N+1)
dp[1] = 1
for i in range(1,N):
  dp[i]%=MOD
  for l,r in LR:
    if i+l<=N:
      dp[i+l] += dp[i]
    if i+r+1<=N:
      dp[i+r+1] -= dp[i]
      
  if i!=1:
    dp[i+1] += dp[i]
    

print(dp[-1]%MOD)

Submission status: Accepted

Solution code:
#Python Competetive Programming Template

from sys import stdin, stdout
from math import *

testing = True

def tp(s="\n"):
	if testing:
		stdout.write(str(s))

def main():
	prime = 998244353
	n, k = [int(i) for i in stdin.readline().split()]
	llist = []
	rlist = []
	for i in range(k):
		l, r = [int(i) for i in stdin.readline().split()]
		llist.append(l)
		rlist.append(r)
	dp = [0]*(n+1)
	dp[1] = 1
	cumul = [0]*(n+1)
	cumul[1] = 1

	for i in range(2, n+1):
		for j in range(k):
			lower = max(1, i-rlist[j])
			upper = i-llist[j]
			#print(lower)
			#print(upper)
			if upper < 0:
				#print("Continuing")
				continue
			out = (cumul[upper] - cumul[lower - 1] + prime) % prime
			dp[i] += out
			dp[i] %= prime

		cumul[i] = (cumul[i - 1] + dp[i])%prime

	#print(dp)
	#print(cumul)
	stdout.write("{0}\n".format(dp[n]))



main()

Submission status: Accepted

Solution code:
P = 998244353
N, K = map(int, input().split())
X = []
for _ in range(K):
    l, r = map(int, input().split())
    X.append((l-1, r))

A = [1] + [0] * N
S = [0, 1] + [0] * N
for i in range(1, N):
    for l, r in X:
        A[i] += S[max(i-l, 0)] - S[max(i-r, 0)]
        A[i] %= P
    S[i+1] = (S[i] + A[i]) % P

print(A[N-1])

Submission status: Accepted

Solution code:
import bisect
from collections import deque
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
# mod = 10 ** 9 + 7
mod = 998244353

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class BIT:
    def __init__(self, N):
        self.N = N
        self.T = [0] * (N + 1)
 
    def add(self, i, x):
        i += 1
        while i <= self.N:
            self.T[i] += x
            self.T[i] %= mod
            i += i & -i
 
    def _sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.T[i]
            s %= mod
            i -= i & -i
        return s % mod
 
    def sum(self, i, j):
        si = self._sum(i - 1)
        sj = self._sum(j)
        return (sj - si) % mod


def main():
    N, K = read_values()
    F = read_lists(K)

    bit = BIT(N)
    bit.add(0, 1)
    for i in range(1, N):
        s = 0
        for l, r in F:
            if i - l < 0:
                continue
            c = bit.sum(max(0, i - r), i - l)
            # print(i, i - r, i - l, c)
            s += c
        # print(s)
        bit.add(i, s)
        # print([bit.sum(i, i) for i in range(N)]) 
    print(bit.sum(N - 1, N - 1) % mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
mod = 998244353
dp = [0]*(N+1)
dp[1] = 1

Ks = [list(mapint()) for _ in range(K)]
Ks.sort()

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sums(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

bit = Bit(N)
bit.add(1, 1)

for i in range(2, N+1):
    for l, r in Ks:
        if i-l<0:
            break
        dp[i] += bit.sums(i-l) - bit.sums(max(0, i-r-1))
        dp[i] %= mod
    bit.add(i, dp[i])

print(dp[-1])

Submission status: Accepted

Solution code:
mod = 998244353

N, K = map(int, input().split())
L = []
R = []
for i in range(K):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

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

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

for i in range(1, N):
    for k in range(K):
        l = max(0, i-R[k])
        r = i-L[k]
        if r < 0:
            continue
        dp[i] += ruisekiwa[r+1] - ruisekiwa[l]
        # print("p", i, k, l, r, ruisekiwa, dp[i])
        dp[i] %= mod
    ruisekiwa[i+1] = ruisekiwa[i] + dp[i]

# print(dp)
print(dp[-1])

Submission status: Accepted

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

dp[0] = 1
a = 0
for i in range(N):
    a += dp[i]
    a %= mod
    for d in D:
        if i + d[0] > N:
            continue
        dp[i + d[0]] += a
        dp[i + d[0]] %= mod
        if i + d[1] + 1 > N:
            continue

        dp[i + d[1] + 1] -= a
        dp[i + d[1] + 1] %= mod


print(dp[N-1])

Submission status: Accepted

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

dp = [1]
acc = [0, 1]
for i in range(1, N):
    c = 0
    for lk, rk in S:
        if i - lk < 0:
            continue
        c += acc[i - lk + 1] - acc[max(i - rk, 0)]
    c %= MOD
    dp.append(c)
    acc.append((acc[-1] + dp[-1]) % MOD)
print(dp[N - 1])

Submission status: Accepted

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

MOD = 998244353

def f_dp(i):
    if 0 <= i < N:
        return dp[i]
    else:
        return 0

dp = [0] * N
dp[0] = 1
for i in range(1, N):
    temp = 0
    for k in range(K):
#         temp += dp[i - LR[k][0]] - dp[i - LR[k][1]-1]
        temp += f_dp(i - LR[k][0]) - f_dp(i - LR[k][1]-1)
    dp[i] = (temp + dp[i-1]) % MOD

print((dp[-1] - dp[-2]) % MOD)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def main():
    INF = 999999999999999999999999
    MOD = 998244353

    n,k = get_nums_l()

    steps = []
    for _ in range(k):
        l,r = get_nums_l()
        steps.append((l,r))
    
    # log(steps)

    # dp[i] = iマスまで行く方法のパターン数
    dp = [0] * (n)
    ruiseki = [0] * (n+1)

    dp[0] = 1
    ruiseki[1] = 1

    for i in range(1, n):
        for a,b in steps:
            l = max(0, i-b)
            r = i-a
            # log("A", i,l,r)
            if r < 0:
                continue

            add = (ruiseki[r+1] - ruiseki[l])
            dp[i] = (dp[i] + add) % MOD
            # log("  B", add)
        ruiseki[i+1] = (ruiseki[i] + dp[i]) % MOD
        # log(dp, ruiseki)

    print(dp[n-1] % MOD)

main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def main():
    mod = 998244353
    N, K = map(int, input().split())
    jump = []
    for _ in range(K):
        l, r = map(int, input().split())
        jump.append((l, r))

    dp = [0] * (N + 2)
    dp[0] = 1
    for i in range(N - 1):
        for l, r in jump:
            if i + l <= N:
                dp[i + l] = (dp[i + l] + dp[i]) % mod
            if i + r + 1 <= N:
                dp[i + r + 1] = (dp[i + r + 1] - dp[i]) % mod
        if i != 0:
            dp[i + 1] = (dp[i + 1] + dp[i]) % mod
        #print("i={}, dp={}".format(i, dp))
    print(dp[N - 1] % mod)


if __name__ == "__main__":
    main()