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:
n,k=map(int,input().split())
s=set()
for i in range(k):
  l,r=map(int,input().split())
  for ll in range(l,r+1):
    s.add(ll)
dp=[0]*(n+1)
dp[1]=1
mod=998244353

for i in range(n):
  for ss in s:
    if i+ss<=n:
      dp[i+ss]+=dp[i]
      dp[i+ss]%=mod
print(dp[-1]%mod)

Submission status: Time Limit Exceeded

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

s = [] 
for i in range(k):
    lk = list(map(int, input().split()))
    for j in range(lk[0], lk[1] + 1):
        s.append(j)

dp = [0 for _ in range(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[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
dp = [0] * N
dp[0] = 1
dp_sum = [0] * N
L = [0] * K
R = [0] * K
mod = 998244353

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

for i in range(1, N):
    # マスiにたどり着くためのパターン数を数える
    cnt = 0
    for j in range(K):
        start = max(0, i - R[j])
        end = i - L[j]
        if end < 0:
            continue
        cnt += sum(dp[start:end+1]) % mod
        cnt %= mod
    dp[i] = cnt

print(dp[N - 1])

Submission status: Time Limit Exceeded

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

MOD = 998244353
class Mint:
    __slots__ = ('value')

    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self

    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self

    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj

    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self

    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self

    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj

    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

LR.sort(key=lambda x: x[1])
pl = pr = -1
LR2 = []
for l, r in LR:
    if LR2:
        pl, pr = LR2.pop()
        if l <= pl:
            LR2.append((l, r))
        elif l <= pr:
            LR2.append((pl, r))
        else:
            LR2.append((pl, pr))
            LR2.append((l, r))
    else:
        LR2.append((l, r))

dp = [Mint() for _ in range(N + 5)]
dp[1] += 1
dp[2] -= 1
for i in range(1, N):
    dp[i] += dp[i - 1]
    for l, r in LR2:
        nl = min(i + l, N + 1)
        nr = min(i + r, N + 1)
        dp[nl] += dp[i]
        dp[nr + 1] -= dp[i]
dp[N] += dp[N - 1]
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input=sys.stdin.readline
N,K=map(int,input().split())
rangs=[]
for _ in range(K):
    l,r=map(int,input().split())
    for i in range(l,r+1):
        rangs.append(i)
from functools import lru_cache
@lru_cache(maxsize=None)
def dynam(n):
    res=0
    for go in rangs:
        if n==go:
            res+=1
        elif n>go:
            res+=dynam(n-go)
    return res
print(dynam(N-1)%998244353)

Submission status: Time Limit Exceeded

Solution code:
root=[]
n,k = map(int,input().split())
for i in range(k):
    x,y = map(int,input().split())
    root.append([x,y])

toori=[0]*(2*10**5)+[0]*n+[0]*(2*10**5)
toori[2*10**5]=1
cum=[0]*k
for a,i in enumerate (root):
    s=0
    for j in range (i[0],i[1]+1):
        s+=toori[2*10**5+1-j]
    cum[a]=s
aaa=sum(cum)
toori[2*10**5+1]+=aaa


for now in range(2,n):#nowが今の場所
    hueru=0
    for a,i in enumerate (root):
        hueru+=(toori[2*10**5+now-i[0]] - toori[2*10**5+now-1-i[1]])
    aaa+=hueru
    toori[2*10**5+now]+=aaa
    toori[2*10**5+n-1]%=998244353
    


print(toori[2*10**5+n-1]%998244353)

Submission status: Time Limit Exceeded

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

for _ in range(K):
  L, R = map(int, input().split())
  move.append((L, R))

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

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

print(dp[N-1])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(k)]
dp = [0]*(n+1)
dp[1] = 1
mod = 998244353

for i in range(2, n+1):
    for j in range(k):
        li = max(i-s[j][1], 1)
        ri = i-s[j][0]
        if ri < 0:
            continue
        dp[i] += sum(dp[li: ri+1])
        dp[i] %= mod
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())

from sys import setrecursionlimit
setrecursionlimit(10**6)

N= 998244353
def find1(ar,n):
    if n==0:
        return 1
    elif n<0:
        return 0
    elif d[n]!=0:
        return d[n]
    s=0
    for i in ar:
        s=(s+find1(ar,n-i)%N)%N
    d[n]=s
    return s

n,k=sep()
ar=[]
from collections import defaultdict
d=defaultdict(int)
for i in range(k):
    l,r=sep()
    ar+=list(range(l,r+1))
ar.sort()
t=n

print(find1(ar,n-1))

Submission status: Time Limit Exceeded

Solution code:
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())

from sys import setrecursionlimit
setrecursionlimit(10**6)

N= 998244353
def find1(ar,n):
    if n==0:
        return 1
    elif n<0:
        return 0
    elif d[n]!=0:
        return d[n]
    s=0
    for i in ar:
        s=(s+find1(ar,n-i)%N)%N
    d[n]=s
    return s

n,k=sep()
ar=[]
from collections import defaultdict
d=defaultdict(int)
for i in range(k):
    l,r=sep()
    ar+=list(range(l,r+1))
ar.sort()
t=n
while(t>100):
    find1(ar,t)
    t//=2
print(find1(ar,n-1))

Submission status: Time Limit Exceeded

Solution code:
divnum = 998244353
n, k = map(int, input().split())
set_A = set()
for _ in range(k):
	a, b = map(int, input().split())
	set_A = set_A | set(range(a, b+1))
ans_list = [0]*(n+1+max(set_A))
ans_list[1] = 1
for i in range(1,n):
	for j in set_A:
		ans_list[i+j] = (ans_list[i+j]+ans_list[i])%divnum
print(ans_list[n])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
set_A = set()
for _ in range(k):
	a, b = map(int, input().split())
	set_A = set_A | set(range(a, b+1))
ans_list = [0]*(n+1+max(set_A))
ans_list[1] = 1
for i in range(1,n):
	for j in set_A:
		ans_list[i+j] += ans_list[i]
print(ans_list[n]%998244353)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
class ModInt(int):
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return ModInt(self.x + other.x) if isinstance(other, ModInt) else ModInt(self.x + other)

    def __sub__(self, other):
        return ModInt(self.x - other.x) if isinstance(other, ModInt) else ModInt(self.x - other)

    def __mul__(self, other):
        return ModInt(self.x * other.x) if isinstance(other, ModInt) else ModInt(self.x * other)

    def __floordiv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, MOD - 2, MOD))
        else:
            if other == 0:
                raise ZeroDivisionError
            else:
                return ModInt(self.x * pow(other, MOD - 2, MOD))

    def __pow__(self, other):
        return ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else ModInt(pow(self.x, other, MOD))

    __radd__ = __add__

    def __rsub__(self, other):
        return ModInt(other.x - self.x) if isinstance(other, ModInt) else ModInt(other - self.x)

    __rmul__ = __mul__

    def __rfloordiv__(self, other):
        return ModInt(other.x * pow(self.x, MOD - 2, MOD)) if isinstance(other, ModInt) else ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else ModInt(pow(other, self.x, MOD))


def main():
    n, k = map(int, input().split())
    L, R = [], []
    for _ in range(k):
        l, r = map(int, input().split())
        L.append(l)
        R.append(r)
    dp = [0] * (n + 1)
    s = [0] * (n + 1)
    dp[1] = ModInt(1)
    s[1] = ModInt(1)
    for i in range(2, n + 1):
        for j in range(k):
            l = max(1, i - R[j])
            r = i - L[j]
            dp[i] += s[r] - s[l - 1]
        s[i] = s[i - 1] + dp[i]
    print(dp[n])


if __name__ == "__main__":
    main()

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

# O(NK)
for i in range(2, n+1):
    for j in range(k):
        li = i-R[j]
        ri = i-L[j]
        if ri<0: continue
        li = max(li, 1)
        dp[i] += cumsum[ri]-cumsum[li-1]
    cumsum[i] = cumsum[i-1]+dp[i]

print(dp[n]%mod)

Submission status: Time Limit Exceeded

Solution code:

def main():
    N, K = map(int,input().split())

    mod = 998244353

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

    S.sort()

    ans = [0]*N
    ans[0] = 1

    for i in range (1,N):
        for j in S:
            if i-j < 0:
                break
            else:
                ans[i] += ans[i-j]
        ans[i] %= mod


    print(ans[N-1])


main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    N, K = map(int,input().split())

    mod = 998244353

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

    S.sort()

    ans = [0]*N
    ans[0] = 1

    for i in range (1,N):
        for j in S:
            if i-j < 0:
                break
            else:
                ans[i] += ans[i-j]
                ans[i] %= mod


    print(ans[N-1])


main()

Submission status: Time Limit Exceeded

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

mod = 998244353

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

S.sort()

ans = [0]*N
ans[0] = 1

for i in range (1,N):
    for j in S:
        if i-j < 0:
            break
        else:
            ans[i] += ans[i-j]
            ans[i] %= mod


print(ans[N-1])

Submission status: Time Limit Exceeded

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

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

S = set()
for i in range(K):
    l, r = map(int, input().split())
    for j in range(l, r+1):
      S.add(j)

S = sorted(list(S))

for i in range(1, N+1):
    for d in S:
        if i + d <= N:
            DP[i+d] += DP[i]%998244353

print(DP[N]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
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 ** 6)
INF = float('inf')
# MOD = 10 ** 9 + 7
MOD = 998244353
num_list = []
str_list = []

def main():
    n, k = i_map()
    num_list = i_row_list(k)

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

    for i in range(2, n+1):
        for j in range(k):
            li = i - num_list[j][1]
            ri = i - num_list[j][0]
            if ri < 0:
                continue
            li = max(li, 0)
            dp[i] += dp_sum[ri] - dp_sum[li-1]
        dp_sum[i] = dp_sum[i-1] + dp[i]
    
    print(dp[n]%MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

leng = 0
for i in range(1,n):
    for j in s:
        leng = j[1] - j[0]
        dp[i] += sum(dp[max(0, i-leng-j[0]):max(0,min(n, i-j[0]+1))])

print(dp[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
m = 998244353
def main():
    n,k = map(int,input().split())
    l,r = [],[]
    for _ in range(k):
        l_, r_ = map(int,input().split())
        l.append(l_)
        r.append(r_)

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

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

    print(dp[n]%m)
main()

Submission status: Time Limit Exceeded

Solution code:
m = 998244353
def main():
    n,k = map(int,input().split())
    l,r = [],[]
    for _ in range(k):
        l_, r_ = map(int,input().split())
        l.append(l_)
        r.append(r_)

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

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

    print(dp[n]%m)
main()

Submission status: Time Limit Exceeded

Solution code:
m = 998244353
n,k = map(int,input().split())
l,r = [],[]
for _ in range(k):
    l_, r_ = map(int,input().split())
    l.append(l_)
    r.append(r_)
    
dp = [0]*(n+1)
dp[1] = 1
dpsum = [0]*(n+1)
dpsum[1] = 1

for i in range(2,n+1):
    for j in range(k): 
        li = i - r[j] 
        ri = i - l[j] 
        if ri < 0:
            continue
        li = max(li,1)
        dp[i] += dpsum[ri] - dpsum[li-1]
    dpsum[i] = dpsum[i-1]+dp[i]
    
print(dp[n]%m)

Submission status: Time Limit Exceeded

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

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

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

for i in range(1, n):
    for j in [k for k in lr if k <= n - i]:
        dp[i + j] += dp[i]

print(dp[n] % mod)

Submission status: Time Limit Exceeded

Solution code:
K, N = map(int, input().split())
num_list = []
for i in range(N):
    L, R = map(int, input().split())
    num_list += list(range(L, R+1))
    
num_set = set(sorted(num_list))
counting = [0 for i in range(K+1)]
counting[1]=1
for i in range(2, K+1): 
    for n in num_set:
        if i-n > 0:
            counting[i] += counting[i-n]
print(counting[K]%998244353)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int,input().split())
    moves = []
     
    mod = 998244353
     
    for _ in range(K):
        L, R = map(int,input().split())
        # for d in range(L, R+1):
        #     moves.append(d)
        moves.append((L, R))
    # moves.sort()
     
    dp = [0] * (N + 1)
    dp[1] = 1
    # for dis in moves:
    #     dp[dis] = 1
    # print(moves)
     
    for n in range(1, N+1):
        for L, R in moves:
            if n - L <= 0 :
                continue
            for dis in range(L, R+1):
                if n - dis >= 1:
                    dp[n] += dp[n - dis] % mod
                else:
                    break
     
    # print(dp)
    print(dp[N] % mod)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc179/tasks/abc179_d

n, k = map(int, input().split())
leaps = []
for _ in range(k):
    l, r = map(int, input().split())
    for i in range(l, r+1):
        leaps.append(i)

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

for i in range(1, n + 1):
    for leap in leaps:
        if(i - leap >= 0):
            dp[i] += dp[i - leap]


print(dp[n] % 998244353)

Submission status: Time Limit Exceeded

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

v = []
for _ in range(K):
    L, R = map(int,input().split())
    # for d in range(L, R+1):
    #     moves.append(d)
    v.append((L, R))
v.sort()

dp = [0] * N        # マスi-1に到達するまでの操作列の個数
sdp = [0] * (N + 1) # dp[i]までの累積和 
dp[0] = 1
sdp[1] = 1

for n in range(1, N):
    for p in v:
        left = max(0, n - p[1])
        right = max(0, n - p[0]+1)
        dp[n] += sdp[right] - sdp[left]
    sdp[n+1] = sdp[n] + dp[n]

print(dp[-1] % mod)

Submission status: Time Limit Exceeded

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

v = []
for _ in range(K):
    L, R = map(int,input().split())
    # for d in range(L, R+1):
    #     moves.append(d)
    v.append((L, R))

dp = [0] * N        # マスi-1に到達するまでの操作列の個数
sdp = [0] * (N + 1) # dp[i]までの累積和 
dp[0] = 1
sdp[1] = 1

for n in range(1, N):
    for p in v:
        left = max(0, n - p[1])
        right = max(0, n - p[0]+1)
        dp[n] += sdp[right] - sdp[left]
    sdp[n+1] = sdp[n] + dp[n]

print(dp[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:

def main():
    mod = 998244353
    N, K = map(int,input().split())
    v = []
    
    for _ in range(K):
        L, R = map(int,input().split())
        # for d in range(L, R+1):
        #     moves.append(d)
        v.append((L, R))
    
    dp = [0] * N        # マスi-1に到達するまでの操作列の個数
    sdp = [0] * (N + 1) # dp[i]までの累積和 
    dp[0] = 1
    sdp[1] = 1

    for n in range(1, N):
        for p in v:
            left = max(0, n - p[1])
            right = max(0, n - p[0]+1)
            dp[n] += sdp[right] - sdp[left]
        sdp[n+1] = sdp[n] + dp[n]

    print(dp[-1] % mod)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    
    N, K = map(int,input().split())
    moves = []

    mod = 998244353

    for _ in range(K):
        L, R = map(int,input().split())
        # for d in range(L, R+1):
        #     moves.append(d)
        moves.append((L, R))
    moves.sort()

    dp = [0] * (N + 1)
    dp[1] = 1
    # for dis in moves:
    #     dp[dis] = 1
    # print(moves)

    for n in range(1, N+1):
        for L, R in moves:
            if n - L <= 0 :
                break
            for dis in range(L, R+1):
                if n - dis >= 1:
                    dp[n] += dp[n - dis]
                else:
                    break

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

for i in range(2, N+1):
    sum_list = [0 for L, R in S]

    j = 0
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if sum_list[j] == 0:
            t = sum(dp[LL:RR+1]) % MOD
            sum_list[j] = t
            dp[i] += t
        else:
            if LL >= 2:
                sum_list[j] -= dp[1]
            sum_list[j] += dp[RR]
            sum_list[j] %= MOD
            dp[i] += sum_list[j]
        j += 1

    dp[i] %= MOD

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.zeros(N*2+2, dtype = int)
dp[1] = 1

for i in range(1, N+1):
    atai = dp[i]
    for LR in LRs:
#        p_array = ([atai] * (LR[1] - LR[0] + 1))
#        mae_zero = ([0] * (LR[0] + (i - 1) + 1))
#        usiro_zero = ([0] * (N*2 - (i - 1) - LR[1]))

        mae_zero = np.zeros(LR[0] + i , dtype = "int32")
        usiro_zero = np.zeros(N*2 - (i - 1) - LR[1], dtype = "int32")
        p_array = np.full((LR[1] - LR[0] + 1), atai, dtype = "int32")

        tasu_array = np.concatenate([mae_zero, p_array, usiro_zero])
        dp = (dp + tasu_array) % 998244353

print(dp[N] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.zeros(N*2+2, dtype = int)
dp[1] = 1

for i in range(1, N+1):
    atai = dp[i]
    for LR in LRs:
#        p_array = ([atai] * (LR[1] - LR[0] + 1))
#        mae_zero = ([0] * (LR[0] + (i - 1) + 1))
#        usiro_zero = ([0] * (N*2 - (i - 1) - LR[1]))

        mae_zero = np.zeros(LR[0] + i , dtype = int)
        usiro_zero = np.zeros(N*2 - (i - 1) - LR[1], dtype = int)
        p_array = np.full((LR[1] - LR[0] + 1), atai, dtype = int)

        tasu_array = np.block([mae_zero, p_array, usiro_zero])
        dp = (dp + tasu_array) % 998244353

print(dp[N] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.zeros(N*2+2, dtype = int)
dp[1] = 1

for i in range(1, N+1):
    atai = dp[i]
    for LR in LRs:
        p_array = ([atai] * (LR[1] - LR[0] + 1))
        mae_zero = ([0] * (LR[0] + (i - 1) + 1))
        usiro_zero = ([0] * (N*2 - (i - 1) - LR[1]))
        mae_zero.extend(p_array)
        mae_zero.extend(usiro_zero)
        dp = (dp + np.array(mae_zero)) % 998244353

print(dp[N] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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


checker = np.zeros(N+1 ,dtype = int)
for LR in LRs:
    for i in range(LR[0], LR[1]+1):
        checker[i] = 1


dp = np.zeros(N*2+2, dtype = int)
dp[1] = 1

for i in range(1, N+1):
    atai = dp[i]
    for LR in LRs:
        p_array = ([atai] * (LR[1] - LR[0] + 1))
        mae_zero = ([0] * (LR[0] + (i - 1) + 1))
        usiro_zero = ([0] * (N*2 - (i - 1) - LR[1]))
        mae_zero.extend(p_array)
        mae_zero.extend(usiro_zero)
        dp = (dp + np.array(mae_zero)) % 998244353

print(dp[N] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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


checker = np.zeros(N+1 ,dtype = int)
for LR in LRs:
    for i in range(LR[0], LR[1]+1):
        checker[i] = 1


dp = np.zeros(N*2+2, dtype = int)
dp[1] = 1

for i in range(1, N+1):
    atai = dp[i]
    for LR in LRs:
        p_array = ([atai] * (LR[1] - LR[0] + 1))
        mae_zero = ([0] * (LR[0] + (i - 1) + 1))
        usiro_zero = ([0] * (N*2 - (i - 1) - LR[1]))
        mae_zero.extend(p_array)
        mae_zero.extend(usiro_zero)
        dp += np.array(mae_zero)

print(dp[N] % 998244353)

Submission status: Time Limit Exceeded

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

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

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if LL <= RR:
            t = sum_list[RR] - sum_list[LL-1]
            dp[i] += t
    sum_list[i] = sum_list[i-1] + dp[i]
    dp[i] %= MOD

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys

sys.setrecursionlimit(10**9)

n, k = map(int, input().split())
a = set()
for i in range(k):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        a.add(j)
a = list(a)


@lru_cache(maxsize=None)
def mov(i):
    y = 0
    if i == 1:
        return 1

    for d in a:
        if i - d >= 0:
            y += mov(i - d)
    return y


print(mov(n) % 998244353)

Submission status: Time Limit Exceeded

Solution code:

import numpy as np

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



move_list = []
checker = np.zeros(N+1 ,dtype = int)
for LR in LRs:
    for i in range(LR[0], LR[1]+1):
        checker[i] = 1

for index, check in enumerate(checker):
    if(check == 1):
        move_list.append(index)

dp = np.zeros(N*2+2, dtype = int)
dp[1] = 1

#for i in range(1, N+1):
#    for j in move_list:
#        if(i < j):
#            break
#        dp[i] = (dp[i] +dp[i-j]) % 998244353

for i in range(1, N+1):
    atai = dp[i]
    for LR in LRs:
        p_array = ([atai] * (LR[1] - LR[0] + 1))
        mae_zero = ([0] * (LR[0] + (i - 1) + 1))
        usiro_zero = ([0] * (N*2 - (i - 1) - LR[1]))
        mae_zero.extend(p_array)
        mae_zero.extend(usiro_zero)
#        print(mae_zero)
        dp += np.array(mae_zero)
#        print(dp[1:N+1])

print(dp[N] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
ans=[0 for _ in range(n*3)]
ans[1]=1

idou=[]

for _ in range(k):
  a=list(map(int,input().split()))
  idou.append(a)
  
    
mod=998244353

rui=[0 for _ in range(n+1)]
rui[1]=1
  
for i in range(2,n+1):
  for g in idou:
    x,y=g
    left=max(0,i-y-1)
    right=max(0,i-x)
    ans[i]+=rui[right]-rui[left]

    
  rui[i]+=((rui[i-1]+ans[i]))

    
    

print(ans[n]%mod)

Submission status: Time Limit Exceeded

Solution code:
# TLE: 通常の DP (もらう DP)
# dp[i] = dp[i-x]
n, k = map(int, input().split())

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

MOD = 998244353
dp = [0]*(n+1)  # [0,n]
dp[1] = 1

for i in range(1, n+1): # i:[1,n]
    for s in S: # max n個ある！
        if i-s >= 0:
            dp[i] += dp[i-s]
            dp[i] %= MOD

print((dp[n] + MOD) % MOD)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
n,k = map(int, input().split()) 
num_list = [list(map(int, input().split())) for _ in range(k)]
cnt_list = [0]*n
cnt_list[0] = 1
s_list = []
set_list = [0]*(n+1)

for i in range(len(num_list)):
    if num_list[i][0] == num_list[i][1]:
        s_list.append(num_list[i][0])
    else:
        for j in range(num_list[i][0],num_list[i][1]+1):
            s_list.append(j)

for i in range(len(s_list)):
    set_list[s_list[i]] = 1

for i in range(n):
    cnt_list = [x * cnt_list[i] + y for (x, y) in zip(set_list, cnt_list)]
    set_list.insert(0,0)
    set_list.pop(n)

print(cnt_list[n-1]%mod)

Submission status: Time Limit Exceeded

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


x = [0]*n
x[0] = 1

for i in range(n):
  for d in a:
    if i + d < n and x[i] != 0:
      x[i+d] += x[i]
   
print(x[n-1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
n,k = map(int, input().split()) 
num_list = [list(map(int, input().split())) for _ in range(k)]
cnt_list = [0]*n
cnt_list[0] = 1
s_list = []

for i in range(len(num_list)):
    if num_list[i][0] == num_list[i][1]:
        s_list.append(num_list[i][0])
    else:
        for j in range(num_list[i][0],num_list[i][1]+1):
            s_list.append(j)

for i in range(n):
    if not cnt_list[i] == 0:
        for j in range(len(s_list)):
            if i+s_list[j] < n:
                cnt_list[i+s_list[j]] += cnt_list[i]

print(cnt_list[n-1] % mod)