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 .

Solution (Python):

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.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])
        

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

Solution (Python):
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:
        
        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)

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
def getsum(BITTree, i):
    s = 0  

    
    i = i + 1

    
    while i > 0:
        
        s += BITTree[i]

        
        i -= i & (-i)
    return s





def updatebit(BITTree, n, i, v):
    
    i += 1

    
    while i <= n:
        
        BITTree[i] += v

        
        i += i & (-i)

    



def construct(arr, n):
    
    BITTree = [0] * (n + 1)

    
    for i in range(n):
        updatebit(BITTree, n, i, arr[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
                
                
                a[i]+=z
                updatebit(BITTree, len(a), i, z)
                


print(a[n]%mod)

Solution (Python):
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)

Solution (Python):
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])
    
    
if __name__=='__main__':
    main()

Solution (Python):
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)]



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

Solution (Python):
class BIT:
    """
    Binary Index Tree
    

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

    
    """

    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 

        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): 
                k-=self.L[res+i]
                res+=i
            
            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)

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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):
    
    
    for j in range(K):
        l = i+lr[j][0]
        r = i+lr[j][1]
        
        if l < N:
            ans[l] = ans[l] + ans[i]
        if r + 1 < N:
            ans[r + 1] = ans[r + 1] - ans[i]
    
    ans[0]=0
    if i<N-1:
        ans[i+1]=(ans[i+1]+ans[i])%p
    
    
print(ans[N-1])

Solution (Python):
import sys, math
import io, os

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

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


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

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

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

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

L.sort()

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

for i in range(2,N+1):
    count = 0
    for l,r in L:
        if l >= i:
            break
        elif l < i and i - r > 1:
            count += dp[i-l] - dp[i-r-1]
        else:
            count += dp[i-l]
    dp[i] = (dp[i-1] + count) % mod

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

Solution (Python):
mod = 998244353
N, K = map(int,input().split())
S = []
for _ in range(K):
    S.append(list(map(int,input().split())))
L = [1]
SUM = [1]
for i in range(1, N):
    tmp = 0
    for j in range(K):
        if i - S[j][0] >= 0:
            tmp += SUM[i - S[j][0]]
        if i - S[j][1] - 1 >= 0:
            tmp -= SUM[i - S[j][1] - 1]
    L.append(tmp % mod)
    SUM.append((L[-1] + SUM[-1]) % mod)

print(L[-1])

Solution (Python):
n, k = map(int, input().split())
span = []
mod = 998244353
for i in range(k):
    span.append(list(map(int, input().split())))
dp = [0 for i in range(n+1)]
acc = [0 for i in range(n + 1)]
dp[0] = 1
for i in range(n+1):
    acc[i] += acc[i-1]
    acc[i] %= mod
    dp[i] += acc[i]
    for j in range(k):
        l, r = span[j]
        if l + i < n + 1:
            acc[l + i] += dp[i]
        if r + 1 + i < n + 1:
            acc[r+1 + i] -= dp[i]
    dp[i] %= mod
print(dp[-2] % mod)

Solution (Python):
import bisect
N,K=map(int, input().split())
p=998244353
L=[]
for i in range(K):
    l,r=map(int, input().split())
    L.append([l,r])

L=sorted(L)

def add(a,b):
    return a+b

class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    
    def update(self, k: int, x):
        k += self.N0 - 1
        
        self.data[k] = x
        
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        
        return res




dp=[0]*N
dp[0]=1
lis=[0]*N
lis[0]=1
seg=SegmentTree(lis, add, 0)
acc=1

for i in range(1,N):
    now=i+1
    temp=0
    for l in L:
        left, right=l
        Left=max(now-right-1,0)
        Right= max(now-left,0)
        temp+=seg.query(Left,Right)
        
    temp%=p

    dp[i]=temp


    
    if dp[i]!=0:
        seg.update(i,temp)

print(dp[-1])

Solution (Python):


import numpy as np


MOD = 998244353



INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,k=INTM()
    lrs=[]
    for i in range(k):
        lrs.append(LIST())
    pt=np.array([0]*((2*n)+1))
    rui=np.array([0]*((2*n)+1))
    pt[n-1]=1
    rui[n-1]=1
    for i in range(n):
        nt=n-1+i
        for l,r in lrs:
            pt[nt]=(pt[nt]-rui[nt-r-1]+rui[nt-l])%MOD
        rui[nt]=(rui[nt-1]+pt[nt])%MOD
    print(pt[2*n-2]%MOD)
    
    

    
    


if __name__=='__main__':
    do()

Solution (Python):
N,K=map(int,input().split())
dp=[0]*(N)
dp[0]=1
mod=998244353
L=list()
for i in range(K):
  a,b=map(int,input().split())
  L.append([a,b])
R=[0,1]
for i in range(1,N):
  for j in range(K):
    a,b=L[j]
    if i>=b:
      dp[i]+=R[i-a+1]-R[i-b]
    elif i>=a:
      dp[i]+=R[i-a+1]
    dp[i]%=mod
  R.append(R[-1]+dp[i])
print(dp[-1])

Solution (Python):
N,K = map(int,input().split())
L = 998244353
LR = [0] * K

for i in range(K):
    l,r = map(int,input().split())
    LR[i] = [l,r]

AS = [0] * (N+2)




A = [0] * (N+2)
A[1] = 1
A[2] = -1
for i in range(1,N+1):
    AS[i] = (AS[i-1] + A[i])%L
    rest = AS[i]
    for l,r in LR:
        if i+l>N:
            continue
        right = min(N+1,i+r+1)
        A[i+l] += rest
        A[right] += -rest

print(sum(A[1:N+1])%L)

Solution (Python):
def d_leaping_tak(MOD=998244353):
    from bisect import bisect_left, bisect_right
    N, K = [int(i) for i in input().split()]
    Ranges = sorted([[int(i) for i in input().split()] for j in range(K)])

    dp = [0] * (N + 1)  
    dp[1] = 1
    cumsum_dp = dp[:]
    for i in range(2, N + 1):
        for l, r in Ranges:
            if i - l < 0:
                continue
            if i - r < 0:
                r = i

            dp[i] += cumsum_dp[i - l] - cumsum_dp[i - r - 1]
        dp[i] %= MOD
        cumsum_dp[i] = cumsum_dp[i - 1] + dp[i]
    
    
    return dp[N]

print(d_leaping_tak())

Solution (Python):
class SegmentTree:
    def __init__(self, n, op, e):
        self.n = 1 << (n - 1).bit_length()
        self.op = op
        self.e = e
        self.data = [e] * (2 * self.n)

    def update(self, k, v):
        k += self.n
        self.data[k] = v
        while k > 0:
            k >>= 1
            self.data[k] = self.op(self.data[2 * k], self.data[2 * k + 1])

    def query(self, left, right):
        left += self.n
        right += self.n
        l_res = self.e
        r_res = self.e
        while left < right:
            if left & 1:
                l_res = self.op(l_res, self.data[left])
                left += 1
            left >>= 1
            if right & 1:
                right -= 1
                r_res = self.op(self.data[right], r_res)
            right >>= 1
        return self.op(l_res, r_res)


MOD = 998244353
N, K, *LR = map(int, open(0).read().split())
segments = [(l, r) for l, r in zip(*[iter(LR)] * 2)]
st = SegmentTree(N + 1, lambda x, y: (x + y) % MOD, 0)
st.update(0, 1)
for i in range(1, N + 1):
    for l, r in segments:
        if i - l < 0:
            continue
        L = max(i - r, 0)
        R = i - l
        st.update(i, st.query(i, i + 1) + st.query(L, R + 1))
print(st.query(N - 1, N))

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    mod = 998244353

    dp = [0]*(n)

    zone = [tuple(map(int, input().split())) for i in range(k)]
    zone.sort()

    dp[0] = 1
    count = 0
    bit = [0]*k

    for i in range(1, n):
        for j in range(k):
            l, r = zone[j]
            if i-l >= 0:
                bit[j] += dp[i-l]
            if i-r-1 >= 0:
                bit[j] -= dp[i-r-1]
        dp[i] += sum(bit)%mod
        dp[i] %= mod
    ans = dp[n-1]
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
MOD = 998244353
N, K = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(K)]
dp = [0]*(N+1)
dp[1] = 1
dp_rui = [0]*(N+1)
dp_rui[1] = 1
for i in range(2,N+1):
    for l, r in S:
        r2 = i-l
        l2 = i-r
        if l == r:
            if i - l >= 0:
                dp[i] += dp[i-l]
        elif r2 > 0 and l2 >= 0:
            dp[i] += dp_rui[r2]-dp_rui[l2-1]
        elif r2 > 0 and l2 < 0:
            dp[i] += dp_rui[r2]
    dp_rui[i] = dp_rui[i-1]+dp[i] % MOD
    dp[i] %= MOD
print(dp[-1]%MOD)

Solution (Python):
N, K = map(int,input().split())
LR = [tuple(map(int,input().split())) for _ in range(K)]
d = [0]*N
d[0] = 1
MOD = 998244353
for i in range(N-1):
    x = d[i]
    d[0] = 0
    for k in range(K):
        L, R = LR[k]
        if i+L < len(d):
            d[i+L] += x
            d[i+L] %= MOD
        if i+R+1 < len(d):
            d[i+R+1] -= x
            d[i+R+1] %= MOD
    d[i+1] += d[i]
    d[i+1] %= MOD
print(d[-1] % MOD)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        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 += 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):
        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


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


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()

    A = [0] * (N + 1)
    A[1] = 1
    seg = SegTree(A, segfunc=segfunc, ide_ele=0)
    for i in range(2, N + 1):
        for l, r in LR:
            if i - l > 0:
                total = (seg.tree[i + seg.num] + seg.query(max(1, i - r), min(N, i - l + 1)) % M)
                seg.update(i, total)
            else:
                break
    print(seg.tree[seg.num + N] % M)


if __name__ == '__main__':
    main()

Solution (Python):
N, K = [int(x) for x in input().split()]

rngs = [tuple(int(x) for x in input().split()) for _ in range(K)]
rngs.sort()
p = 998244353

dp = [1] + [0] * (N - 1)
imos = [[] for _ in range(N)]
imos[1].append((-1, 0))
for i in range(N - 1):
    for l, r in rngs:
        if i + l < N:
            imos[i + l].append((1, i))
        if i + r + 1 < N:
            imos[i + r + 1].append((-1, i))


for i in range(1, N):
    dp[i] = dp[i - 1]
    for c, j in imos[i]:
        dp[i] += c * dp[j]
        dp[i] %= p

print(dp[N - 1])

Solution (Python):
from sys import stdin
input = stdin.buffer.readline

def main():
    mod = 998244353
    n, k = map(int, input().split())

    lr = [(0, 0)] * k
    for i in range(k):
        l, r = map(int, input().split())
        lr[i] = (l, r+1)

    
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = -1
    for i in range(n):
        dp[i] += dp[i-1]
        dp[i] %= mod
        for l, r in lr:
            if i + l < n:
                dp[i + l] += dp[i]
                dp[i + l] %= mod
                if i + r < n:
                    dp[i + r] -= dp[i]
                    dp[i + r] %= mod

    print(dp[n-1])

main()

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=998244353



def main():
	
	n, k = tin()
	
	al = []
	for _ in range(k):
		l,r = tin()
		al.append([l,r])
	
	dd = [0]*(n)
	dd[0] = 1
	
	ruiseki=[0]*(n)
	ruiseki[0]=1
	ruiseki[1]=-1
	rui=0
	for pos, num in enumerate(ruiseki):
		rui += ruiseki[pos]
		rui %= mod
		dd[pos]=rui
		for l,r in al:
			if pos + l < n:
				ruiseki[pos+l] += rui
			if pos + r + 1 < n:
				ruiseki[pos + r + 1] -= rui
		
		
		
	return rui%mod
		
		
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import sys
input = sys.stdin.readline

mod = 998244353
N, K = map(int, input().split())
L, R = zip(*[list(map(int, input().split())) for _ in range(K)])
dp = [0] * (N + 1)
dp[1] = 1
dp[2] = -1
x = 0
for i in range(1, N):
    x = (x + dp[i]) % mod
    for j in range(K):
        if i + L[j] > N:
            continue
        dp[i + L[j]] = (dp[i + L[j]] + x) % mod
        if i + R[j] + 1 <= N:
            dp[i + R[j] + 1] = (dp[i + R[j] + 1] - x) % mod
x = (x + dp[N]) % mod
print(x)

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 998244353


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, SS):
    count = [0] * (N + 10)
    count[0] = 1
    accum = [0] * (N + 10)
    accum[0] = 1

    for pos in range(1, N):
        ret = 0
        for left, right in SS:
            
            
            
            
            
            
            start = max(-1, pos - right - 1)
            end = max(-1, pos - left)
            
            ret += (accum[end] - accum[start])
            ret %= MOD
        
        count[pos] = ret
        accum[pos] = accum[pos - 1] + ret

    
    ret = count[N - 1]
    return ret % MOD


def main():
    
    N, K = map(int, input().split())
    SS = []
    for i in range(K):
        SS.append(tuple(map(int, input().split())))
    print(solve(N, K, SS))



T1 = """
5 2
1 1
3 4
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
4
"""

T2 = """
5 2
3 3
5 5
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
0
"""

T3 = """
5 1
1 2
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
5
"""

T4 = """
60 3
5 8
1 3
10 15
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
221823067
"""

T5 = """
10 1
1 2
"""
TEST_T5 = """
>>> as_input(T5)
>>> main()
55
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    MOD = 998244353

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

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

    acc = [0] * (n + 1)
    acc[1] = 1
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        t = 0
        for l, r in blocks:
            if i - l >= 0:
                t += acc[i - l]
            if i - r - 1 >= 0:
                t -= acc[i - r - 1]
            t %= MOD
        dp[i] = t
        acc[i] = (acc[i - 1] + t) % MOD

    print(dp[-1] % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
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)

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

dp = [0] * (n + 1)

dp[0] = 0; dp[1] = 1

for i in range(2, n+1):
    dp[i] = dp[i-1]
    for x, y in a:
        l = i - y; r = i - x
        l = max(l, 0); r = min(r, i-1)
        dp[i] = (dp[i] + (dp[r] - (dp[l - 1] if l > 0 else 0))) % MOD

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

Solution (Python):
N, K = map(int, input().split())
S = []
for j in range(K):
    S.append(list(map(int, input().split())))

m =  998244353



dp = [0] * N
dp[0] = 1
sum_of_region = [0] * K
for i in range(1, N):
    for j in range(K):
        if i - S[j][0] >= 0:
            sum_of_region[j] += dp[i - S[j][0]]
        if i - S[j][1] - 1 >= 0:
            sum_of_region[j] -= dp[i - S[j][1] - 1]
        dp[i] += sum_of_region[j] % m
        dp[i] %= m
    

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

Solution (Python):
import sys
readline = sys.stdin.readline

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

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


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

Solution (Python):
n,k = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(k)]
imos = [0] * (2 * n + 1)
imos[0] = 1
imos[1] = -1
ans = [1]
  
for i in range(n):
    for x,y in lis:
        imos[i+x] += ans[-1]
        imos[i+y+1] -= ans[-1]
    ans.append((ans[-1]+imos[i+1])%998244353)
  
print(ans[-2])