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: Time Limit Exceeded

Solution code:
import sys
import re
import queue
import collections
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []


def main():
	N,K= i_map()
	L = []
	R = []
	for i in range(0,K):
		tmpL,tmpR = i_map()
		L.append(tmpL)
		R.append(tmpR)

	a = []
	a.append(0)
	a.append(-1)
	for i in range(2,3*N):
		a.append(0)

	f = []
	f.append(1)

	for i in range(0,N):
		for j in range(0,K):
			a[i+L[j]] += f[i]
			a[i+R[j]+1] += -f[i]
		f.append(f[i]+a[i+1])

	print(f[N-1]%998244353)

	return

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# TLE

n, k = map(int, input().split())
L = [0 for _ in range(k)]
R = [0 for _ in range(k)]
for i in range(k):
    L[i], R[i] = map(int, input().split())
mod = 998244353

dp = [0 for _ in range(n+1)]
dp[0] = 0 
dp[1] = 1 

def cont(x, y): 
    ret = []
    for i in range(x, y+1):
        ret.append(i)
    return ret 

s = []
for i in range(k):
    s += cont(L[i], R[i])

for i in range(2, n+1):
    for j in range(len(s)):
        if i-s[j] > 0:
            dp[i] += (dp[i-s[j]])%mod

print(dp[n]%mod)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
lr= [map(int, input().split()) for _ in range(K)]
l,r= [list(i) for i in zip(*lr)]

mod=998244353

dp=[0]*N
dp[0]=1
dpsum=[0]*(N+1)
dpsum[0]=1
for i in range(1,N):
    for j in range(K):
        li=i-r[j]
        ri=i-l[j]
        if ri<0:
            continue
        li=max(li,0)
        if li-1<0:
            dpsum[li-1]=0
        dp[i]+=dpsum[ri]-dpsum[li-1]
    dpsum[i]=(dpsum[i-1]+dp[i])


print(dp[N-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

n, k = map(int, input().split())
L = [0 for _ in range(k)]
R = [0 for _ in range(k)]
for i in range(k):
    L[i], R[i] = map(int, input().split())
mod = 998244353

dp = [0 for _ in range(n+1)]
dp[0] = 0 
dp[1] = 1 

def cont(x, y): 
    ret = []
    for i in range(x, y+1):
        ret.append(i)
    return ret 

s = []
for i in range(k):
    s += cont(L[i], R[i])

for i in range(2, n+1):
    for j in range(len(s)):
        if i-s[j] > 0:
            dp[i] += (dp[i-s[j]])%mod

print(dp[n]%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools
from math import *
from bisect import *
from heapq import *
from collections import *
import queue

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

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N, K = In.ints()
segments = []

for _ in range(K):
    l,r = In.ints()
    segments.append((l,r))

segments.sort(key=lambda x: x[0])
MOD = 998244353

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

for i in range(2, N+1):
    for j in range(K):
        if i-segments[j][0]<=0:
            break

        for k in range(segments[j][0], segments[j][1]+1):
            if i-k<=0:
                break
            dp[i] += dp[i-k]
            dp[i] %= MOD

Out.int(dp[N])

######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Time Limit Exceeded

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

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

acc = [0]*n
acc[0] = 1

for i in range(1, n):
    for l, r in lr:
        if 0 <= i-r and i-l < i:
            dp[i] += acc[i-l]-acc[i-r-1]
        elif i-r < 0 and i-l < i:
            dp[i] += acc[i-l]
        elif i-r < 0 and i <= i-l:
            dp[i] += acc[i-1]
        elif 0 < i-r and i <= i-l:
            dp[i] += acc[i-1]-acc[i-r-1]
    acc[i] = acc[i-1]+dp[i]

print(dp[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    lr = []
    for _ in range(k):
        lr.append(tuple(map(int, input().split())))
    mod = 998244353
    
    dp = [0]*n
    dp[0] = 1
    
    acc = [0]*n
    acc[0] = 1
    
    for i in range(1, n):
        for l, r in lr:
            if 0 <= i-r and i-l < i:
                dp[i] += acc[i-l]-acc[i-r-1]
            elif i-r < 0 and i-l < i:
                dp[i] += acc[i-l]
            elif i-r < 0 and i <= i-l:
                dp[i] += acc[i-1]
            elif 0 < i-r and i <= i-l:
                dp[i] += acc[i-1]-acc[i-r-1]
        acc[i] = acc[i-1]+dp[i]
    
    print(dp[-1]%mod)


main()

Submission status: Time Limit Exceeded

Solution code:
# 配るDP

mod = 998244353

def main(N, S):
    dp = [0 if n != 0 else 1 for n in range(N)] # 初期値
    lst_S = sorted(list(S))

    for i in range(N):
        if dp[i] == 0:  # 計算時間削減のため， 時間さえ間に合えば不要かも．
            continue
        for j in lst_S:
            if i + j > N - 1:
                break
            else:
                dp[i+j] = (dp[i+j] + dp[i]) % mod
    print(dp[-1])


if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    S = set()
    for k in range(K):
        L, R = list(map(int, input().split()))
        S = S | {i for i in range(L, R+1)}
    main(N, S)

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split()))
s = set()
o = []
for i in range(k):
    n1 = list(map(int, input().split()))
    o.append(n1)
l=[0]*(n+1)
ll = []
o.sort()
for i in o:
    for j in range(i[0],i[1]+1):
        ll.append(j)
l[0] = 1
"""
for i in range(n):
    for j in o:
        for k in range(j[0],j[1]+1):
            l[i+k] = (l[i+k]+l[i])%998244353
print(l[n-1]%998244353)
"""
lll = len(ll)
for i in range(n):
    tmp = 0
    while ll[tmp]-1 < i:
        l[i] =  l[i] + l[i-ll[tmp]]
        tmp += 1
        if lll == tmp:
            break
    l[i]=l[i]%998244353
print(l[n-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split()))
s = set()
o = []
for i in range(k):
    n1 = list(map(int, input().split()))
    o.append(n1)
l=[0]*(n+1)
ll = []
for i in o:
    for j in range(i[0],i[1]+1):
        ll.append(j)
l[0] = 1
"""
for i in range(n):
    for j in o:
        for k in range(j[0],j[1]+1):
            l[i+k] = (l[i+k]+l[i])%998244353
print(l[n-1]%998244353)
"""
ll.sort()
lll = len(ll)
for i in range(n):
    tmp = 0
    while ll[tmp]-1 < i:
        l[i] =  l[i] + l[i-ll[tmp]]
        tmp += 1
        if lll == tmp:
            break
    l[i]=l[i]%998244353
print(l[n-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class LazySegmentTree():
    def __init__(self, op, e, mapping, composition, im, init_array):
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.im = im

        l = len(init_array)

        def ceil_pow2(n):
            x = 0
            while (1 << x) < n:
                x += 1
            return x
        self.log = ceil_pow2(l)
        self.size = 1 << self.log
        self.d = [e() for _ in range(2*self.size)]
        self.lz = [im() for _ in range(self.size)]

        for i, a in enumerate(init_array):
            self.d[i+self.size] = a

        for i in range(self.size-1, 0, -1):
            self.__update(i)

    def set(self, p, x):
        p += self.size

        for i in range(self.log, 0, -1):
            self.__push(p >> i)

        self.d[p] = x

        for i in range(1, self.log+1):
            self.__update(p >> i)

    def __getitem__(self, p):
        p += self.size
        for i in range(self.log, 0, -1):
            self.__push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        if l == r:
            return self.e()

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push(r >> i)

        sml = self.e()
        smr = self.e()

        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1

        return self.op(sml, smr)

    def apply(self, l, r, f):
        if l == r:
            return

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push((r-1) >> i)

        l2, r2 = l, r
        while l < r:
            if l & 1:
                self.__all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.__all_apply(r, f)
            l >>= 1
            r >>= 1
        l, r = l2, r2

        for i in range(1, self.log+1):
            if ((l >> i) << i) != l:
                self.__update(l >> i)
            if ((r >> i) << i) != r:
                self.__update((r-1) >> i)

    def __update(self, k):
        self.d[k] = self.op(self.d[2*k], self.d[2*k+1])

    def __all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def __push(self, k):
        self.__all_apply(2*k, self.lz[k])
        self.__all_apply(2*k+1, self.lz[k])
        self.lz[k] = self.im()


@mt
def slv(N, K, LR):
    M = 998244353

    def e():
        return 0

    def op(sl, sr):
        return (sl + sr) % M

    def mapping(fl, sr):
        return (fl + sr) % M

    def composition(fl, fr):
        return (fl + fr) % M

    def im():
        return 0

    memo = LazySegmentTree(op, e, mapping, composition, im, [0]*(N+1))
    memo.apply(1, 1+1, 1)
    for i in range(1, N+1):
        n = memo[i]
        for l, r in LR:
            ll = min(N+1, i+l)
            rr = min(N+1, i+r+1)
            memo.apply(ll, rr, n)

    return memo[N]


def main():
    N, K = read_int_n()
    LR = [read_int_n() for _ in range(K)]
    print(slv(N, K, LR))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
S = [tuple(map(int,input().split())) for _ in range(K)]
MOD=998244353
dp=[0]*N
dp[0]=1
for i in range(N-1):
    x = dp[i]
    dp[0]=0
    for k in range(K):
        l,r = S[k]
        if i+l < N:
            dp[i+l]+=x
            dp[i+l]%MOD
        if i+r+1 < N:
            dp[i+r+1]-=x
            dp[i+r+1]%MOD
    dp[i+1]+=dp[i]
    dp[i+1]%MOD
print(dp[-1]%MOD)

Submission status: Time Limit Exceeded

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

for i in range(1,N):
    for j in range(K):
        l = max(0,i-R[j])
        r = max(0,i-L[j]+1)
        DP[i] += SDP[r] - SDP[l]
    SDP[i+1] = SDP[i] + DP[i]
print(DP[N-1]%MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
N, K = map(int,input().split())
S = []
for k in range(K):
    L, R = map(int,input().split())
    for l in range(L,R+1):
        S.append(l)
S.sort()
dp = [0]*(N+1)
dp[1] = 1
for k in range(1,N+1):
    for e in S:
        if k+e <= N:
            dp[k+e] += dp[k]
            dp[k+e] %= MOD
        else:
            break
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:

icase=0
if icase==0:
    n,k=map(int,input().split())
    lr=[[0]*2 for i in range(k)]
    for i in range(k):
        lr[i]=list(map(int,input().split()))
elif icase==1:
    n,k=5,2
    lr=[[1, 1], [3, 4]]
elif icase==2:
    n,k=60,3
    lr=[[5, 8], [1, 3], [10, 15]]
elif icase==3:
    n,k=30,2 
    lr=[[1,1], [6,8]]
elif icase==4:
    n,k=30,1 
    lr=[[6,8]]

mod=998244353

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

for i in range(1,n):
    for kk in range(k):
        if i+lr[kk][0]>n+1:
            continue
#for kk in range(k):
#    for i in range(1,n):
        for lri in range(lr[kk][0],min(lr[kk][1]+1,n+1)):
            j=i+lri
            if j<=n:
                dp[j]=(dp[j]+dp[i])%mod
#    print(dp)

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
#editorial
n,k=map(int,input().split())
*lr,=[tuple(map(int, input().split())) for _ in range(k)]
res =[0]*(2*n+3)
##############
diff=[0]*(2*n+3)
######
#res[0]=1

diff[0]=1
diff[1]=-1
mod=998244353

for i in range(n+1):
    res[i]=res[i-1]+diff[i]
    for li,ri in lr:
        diff[i+li]+=res[i]
        diff[i+ri+1]-=res[i]
    #print(res[:n+1])
    #print((diff[:n+1]))
print(res[n-1]%mod)
#print(res[:n+1])
#print((diff[:n+1]))

Submission status: Time Limit Exceeded

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

    dp = [0] * (n+1);

    dp[0] = 1
    dp[1] = -1

    for i in range(0, n):
        if i>0: dp[i] += dp[i-1]
        for l,r in lr:
            if i+l > n: continue
            dp[i+l] += dp[i]
            dp[min(n, i+r+1)] -= dp[i]

    print(dp[n-1] % 998244353)

main()

Submission status: Time Limit Exceeded

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

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

dp=[0]*(n+1)
dp[1]=1
dpsum=[0]*(n+1)
dpsum[1]=1

for i in range(1,n):
    dpsum[i]=dp[i]+dpsum[i-1]
    for j in range(k):
        l,r=k_list[j]
        li=i+l
        ri=i+r+1
        if li<=n:
            dp[li]+=dpsum[i]
        if ri<=n:
            dp[ri]-=dpsum[i]

print(dp[n]%998244353)

Submission status: Time Limit Exceeded

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

dp = [0] * (n+1);

dp[0] = 1
dp[1] = -1

for i in range(0, n):
    if i>0: dp[i] += dp[i-1]
    for l,r in lr:
        if i+l > n: continue
        dp[i+l] += dp[i]
        dp[min(n, i+r+1)] -= dp[i]

print(dp[n-1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
def N():
    return int(input())
def L():
    return list(map(int,input().split()))
def NL(n):
    return [list(map(int,input().split())) for i in range(n)]
mod = pow(10,9)+7
#import numpy
#import sympy
import math
md = 998244353

n,k = L()
lr = NL(k)
s = set()

for l,r in lr:
    s |= set(range(l,r+1))
l = [0]*(n+1)
l[1]=1

for i in range(1,n+1):
    for j in s:
        if i+j<n+1:
            l[i+j] = (l[i+j]+l[i])%md
    #print(l)
#print(l)
print(l[n]%md)

Submission status: Time Limit Exceeded

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

dp = [0] * (n+1);

dp[0] = 1
dp[1] = -1

for i in range(0, n):
    if i>0: dp[i] += dp[i-1]
    for l,r in lr:
        if i+l > n: continue
        dp[i+l] += dp[i]
        dp[min(n, i+r+1)] -= dp[i]

print(dp[n-1] % 998244353)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
N, K = map(int,input().split())
S = set()
for k in range(K):
    L, R = map(int,input().split())
    for l in range(L,R+1):
        S.add(l)
dp = [0]*(2*N+1)
dp[1] = 1
for k in range(1,N+1):
    for e in S:
        dp[k+e] += dp[k]
#        dp[k+e] %= MOD
print(dp[N]%MOD)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
N, K = map(int,input().split())
S = set()
for k in range(K):
    L, R = map(int,input().split())
    for l in range(L,R+1):
        S.add(l)
dp = [0]*(2*N+1)
dp[1] = 1
for k in range(1,N+1):
    for e in S:
        dp[k+e] += dp[k]
        dp[k+e] %= MOD
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
# 配るDP
def resolve():
  base = 998244353
  N, K = map(int, input().split(" "))

  LRs = []
  for _ in range(K):
    (L, R) = map(int, input().split(" "))
    LRs.append((L, R))

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

  for i in range(1, N+1):
    dp_sum[i] = dp[i] + dp_sum[i-1]
    if dp_sum[i] > base:
      dp_sum[i] %= base
    for lr in LRs:
      left = i + lr[0]
      right = i + lr[1] + 1
      if left <= N:
        dp[left] += dp_sum[i]
      if right <= N:
        dp[right] -= dp_sum[i]
    
  print(dp[-1]%base)

if __name__ == "__main__":
  resolve()

Submission status: Time Limit Exceeded

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

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

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

for i in range(1,n):
    for j in range(k):
        l,r=k_list[j]
        li=i-r
        ri=i-l
        if ri<0:
            continue
        if li<=0:
            dp[i]+=dpsum[ri]
        else:
            dp[i]+=dpsum[ri]-dpsum[li-1]
    dpsum[i]=dpsum[i-1]+dp[i]

print(dp[n-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(i) for i in input().split()]
a = []
for _ in range(k):
    x, y = [int(i) for i in input().split()]
    a.append([x, y])
a.sort()
dp = [0] * n
dp[0] = 1
for i in range(1, n):
    for j in a:
        ok = True
        for s in range(j[0], j[1] + 1):
            if i >= s:
                dp[i] += dp[i - s]
            else:
                ok = False
                break
        if not ok:
            break

print(int(dp[n - 1]) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
input = sys.stdin.readline
read = lambda: list(map(int, input().strip().split()))

MOD = 998244353
def main():
	n, k = read(); arr = []
	for i in range(k):
		a, b = read()
		arr.extend(range(a, b+1))
	dp = [0]*(n+1)
	dp[1] = 1
	for i in range(1, n+1):
		for j in arr:
			if (i+j) <= n:
				dp[i+j] += dp[i]
				dp[i+j] %= MOD
	print(dp[n])

	

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(i) for i in input().split()]
a = []
for _ in range(k):
    x, y = [int(i) for i in input().split()]
    a.append([x, y])
a.sort()
dp = [0] * n
dp[0] = 1
for i in range(1, n):
    for j in a:
        for s in range(j[0], j[1] + 1):
            if i >= s:
                dp[i] += dp[i - s]

print(int(dp[n - 1]) % 998244353)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, k  = map(int, input().split())
lis = []
ans = [0]*n + [1]
anssum = [0]*(n) + [1, 0]
for _ in range(k):
  a, b = map(int,input().split())
  lis.append((a, b))
for l in reversed(range(1, n)):
  for a, b in lis:
    p, q = min(n+1, l+b+1), min(n+1, l+a)
    ans[l] = ans[l] - anssum[p] + anssum[q]
  anssum[l] = anssum[l+1] + ans[l]
print(ans[1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
n, k  = map(int, input().split())
lis = []
ans = [0]*n + [1]
anssum = [0]*(n) + [1] + [0]*2*n
for _ in range(k):
  a, b = map(int,input().split())
  lis.append((a, b))
for k in reversed(range(1, n)):
  for a, b in lis:
    ans[k] = ans[k] - anssum[k+b+1] + anssum[k+a]
  anssum[k] = anssum[k+1] + ans[k]
print(ans[1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]
 
# dpの高速化 => O(N)で解く
dp = [0] * N
dp[0] = 1
mod = 998244353
 
for i in range(N):
  for j in range(K):
    L = X[j][0]
    R = X[j][1]
    for k in range(L, R+1):
      if 0 <= i - k < N-1:
        dp[i] += dp[i-k]
        dp[i] %= mod
      else: continue

print(dp[N-1])

Submission status: Time Limit Exceeded

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

# dpの高速化 => O(N)で解く
dp = [0] * N
dp[0] = 1
mod = 998244353
 
for i in range(N):
  for j in range(K):
    L = X[j][0]
    R = X[j][1]
    for k in range(L, R+1):
      if 0 <= i - k <= N-1:
        dp[i] += dp[i-k]
        dp[i] %= mod
      else: continue

print(dp[N-1])

Submission status: Time Limit Exceeded

Solution code:
n,k = list(map(int, input().split()))
s = set()
for _ in range(k):
    l,r = list(map(int, input().split()))
    for i in range(l,r+1):
        s.add(i)

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

for i in range(n-1):
    for j in s:
        if i+j < n:
            dp[i+j] += dp[i]
            dp[i+j] %= 998244353

print(dp[-1])

Submission status: Time Limit Exceeded

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

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

mod = 998244353

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

for i in range(N-1):
    tmp = (tmp + dp[i]) % mod
    # dp[i] = tmp
    for l, r in LR:
        dp[min(i+l, N)] = (dp[min(i+l, N)] + tmp) % mod
        dp[min(i+r+1, N)] = (dp[min(i+r+1, N)] - tmp) % mod
print(dp[N-1])

Submission status: Time Limit Exceeded

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

num=len(seg)
ans=[1]
for i in range(1,N):
    val=0
    for k in range(num):
        ad=i-seg[k]
        if ad>=0:
            val+=ans[ad]
    ans.append(val)
print(ans[N-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,bisect

icase=0
if icase==0:
    n,k=map(int,input().split())

    s=[]
    for i in range(k):
        li,ri=list(map(int,input().split()))
        for i in range(li,ri+1):
            s.append(i)
elif icase==1:
    n,k=5,2
    s=[1, 3, 4]
elif icase==2:
    n,k=60,3    
    s=[5, 6, 7, 8, 1, 2, 3, 10, 11, 12, 13, 14, 15]

s.sort()

mod=998244353

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

iri=[0]*(n+1)
for si in s:
    iri[si]=1
for i in range(1,n+1):
    iri[i]=iri[i]+iri[i-1]    

for i in range(1,n):
#    ir=min(bisect(s,n-i)+1,n)
    ir=min(iri[n-i]+1,n)
    for si in s[:ir]:
        j=i+si
        if j<=n:
            dp[j]=(dp[j]+dp[i])%mod
#    print(i,ir,dp)

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
ni8 = np.int64
MOD = 998244353


def solve(lr, dp, n, k):
    acc_dp = np.ones_like(dp)
    for i in range(1, n):
        val = 0
        for j in range(k):
            a = i - lr[j, 0]
            if a < 0:
                continue
            b = i - lr[j, 1] - 1
            val += acc_dp[a] - (acc_dp[b] if b >= 0 else 0)
        dp[i] = val % MOD
        acc_dp[i] = (acc_dp[i - 1] + dp[i]) % MOD
    return dp[n - 1]


def main():
    f = open(0)
    n, k = [int(x) for x in f.readline().split()]
    lr = np.fromstring(f.read(), ni8, sep=' ').reshape((-1, 2))
    dp = np.zeros(n, ni8)
    dp[0] = 1
    ans = solve(lr, dp, n, k)
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, K = map(int, input().split())

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


q = deque()
q.append(0)

boxes = [0 for n in range(N)]
while q:
    i = q.popleft()
    for s in S:
        if i + s >= N:
            continue
        boxes[i + s] += 1
        q.append(i+s)


print(boxes[-1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
D=set()
for _ in range(K):
	L,R=map(int,input().split())
	for l in range(L,R+1):
		D.add(l)
	
MOD = 998244353

dp = [ 0 for _ in range(N+1) ]
dp[1] = 1

# print(D)

# これでは、データによってはO(n ** 2)でTLE
for n in range(1,N+1):
	for d in D:
		if n+d <= N and dp[n]:
			dp[n+d] += dp[n]
			# print("遷移",n,d,"値",dp[n+d])

# d[n+d]

# print(dp)
print(dp[N] % MOD)

Submission status: Time Limit Exceeded

Solution code:
n,k = list(map(int, input().split()))
numlist=[]
for i in range(k):
    l,r=list(map(int, input().split()))
    for j in range(l,r+1):
        numlist.append(j)
numlist.sort()
nlen=len(numlist)
count=[0]*(n+2)
count[0]=1
for i in range(n-1):
    count[i]%=998244353
    for j in range(nlen):
        num=numlist[j]-1
        if i+1>num:
            count[i+1]+=count[i-num]
        else:
            break
print(count[i+1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
n,k = list(map(int, input().split()))
numlist=[]
for i in range(k):
    l,r=list(map(int, input().split()))
    for j in range(l,r+1):
        numlist.append(j)
numlist.sort()
nlen=len(numlist)
count=[0]*(n+2)
count[0]=1
for i in range(n-1):
    for j in range(nlen):
        num=numlist[j]-1
        if i+1>num:
            count[i+1]=(count[i+1]+count[i-num])%998244353
print(count[i+1])