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

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    # 標準入力を取得
    N, K = list(map(int, input().split()))
    L, R = [], []
    for k in range(K):
        L_k, R_k = list(map(int, input().split()))
        L.append(L_k)
        R.append(R_k)

    return N, K, L, R


def main(N: int, K: int, L: list, R: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): マスの数(2 <= N <= 2 * 10**5)
        K (int): 区関数(1 <= K <= min(K, N))
        L (list): 区間の下限(1 <= L_i <= R_i <= N)
        R (list): 区間の上限(1 <= L_i <= R_i <= N)
    """
    # 求解処理
    S = set()
    for k in range(K):
        for s in range(L[k], R[k] + 1):
            S.add(s)
    S = sorted(S)

    m = {i: 0 if i != 1 else 1 for i in range(1, N + 1)}
    for i in range(1, N):
        if m[i] == 0:
            continue
        for s in S:
            if i + s <= N:
                m[i + s] += m[i]
            else:
                break

    ans = m[N] % 998244353

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, K, L, R = get_input()

    # メイン処理
    main(N, K, L, R)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
inf=998244353


N,K=map(int,input().split())
SS=[]

for i in range(K):
    s1,s2=map(int,input().split())
    for j in range(s1,s2+1):
        SS.append(j)



table = [0 for k in range(N-1)] 

for s in SS:
    if s<=N-1:
        table[s-1]+=1
for i in range(N-1):
    if table[i]!=0:
        for s in SS:
            if i+s<N-1:
                table[i+s]+=table[i]
                table[i+s]%=inf
                #print(table,i,s)
print(table[-1]%inf)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
L=list()
R=list()
dice=list()
dp=[0]*N
dp[0]=1
for i in range(K):
    l,r=map(int,input().split())
    for i in range(l,r+1):
        if i<=N-1:
            dice.append(i)
dice.sort()
for i in range(1,N):
    for j in range(len(dice)):
        if i-dice[j]<0:
            break
        else:
            dp[i]+=dp[i-dice[j]]%998244353
print(dp[N-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
n = list(map(int, input().split()))
masu = [0]*n[0]
masu[0] = 1
l = [0]*n[1]
r = [0]*n[1]
for i in range(n[1]):
    kukan = list(map(int, input().split()))
    l[i] = kukan[0]
    r[i] = kukan[1]
l.sort()
r.sort()
for i in range(n[0]):
    for j in range(n[1]):
        if i + l[j] >= n[0]:
            break
        for k in range(l[j],r[j]+1):
            if i+k < n[0]:
                masu[i+k]+=masu[i]
            else:
                break
print(masu[n[0]-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

p = 998244353

jump = []
for i in range(k):
    a, b = map(int, input().split())
    jump += list(range(a, b+1))

dp = [0]*(n+1+max(jump))
dp[0] = 1
for i in range(n):
    for j in range(len(jump)):
        dp[i+jump[j]] += dp[i]%p
        dp[i+jump[j]] %= p

print(dp[n-1]%p)

Submission status: Time Limit Exceeded

Solution code:
n,k = tuple(map(int,input().split()))
boolean = [False for _ in range(n+1)]
for _ in range(k):
  l,r = tuple(map(int,input().split()))
  for num in range(l,r+1):
    boolean[num] = True;
dp = [0 for _ in range(n+1)]
dp[1] = 1
for i in range(2,n+1):
  for lower in range(1,i):
    if boolean[lower]:  #start + lower
      start = i - lower
      dp[i]+= dp[start]
print(dp[n]%998244353)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,k=map(int,input().split())
    xy = [map(int, input().split()) for _ in range(k)]
    x, y = [list(i) for i in zip(*xy)]
    slist=[]
    for j in range(k):
        jlist=list(range(x[j],y[j]+1))
        slist.extend(jlist)
    alist=[1]
    blist=[0]*(n-1)
    alist.extend(blist)
    for r in range(n):
        for sa in slist:
            if r+sa<=n-1:
                alist[r+sa]+=alist[r]
    ans=alist[n-1]
    answer=ans%998244353
    print(answer)


main()

Submission status: Time Limit Exceeded

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

lr.sort()

masu = [0 for i in range(n)]
masu[0] = 1
len_lr = len(lr)

for i in range(1,n):
    ok = 0
    ng = len_lr
    while ng-ok > 1:
        if i-lr[(ok+ng)//2] >=0:
            ok = (ok+ng)//2
        else:
            ng = (ok+ng)//2

    if i - lr[ok] >= 0:
        for j in range(ok+1):
            masu[i] += masu[i - lr[j]]
            masu[i] %= 998244353

print(masu[-1])

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
s=[0]*(N+1)
mod=998244353
l=[]
for i in range(K):
   a,b=map(int,input().split())
   for j in range(a,b+1):
      if s[j]==1:
         break
      s[j]=1
for i,j in enumerate(s):
   if j==1:
      l.append(i)
dp=[0]*(N+1)
dp[1]=1
for i in range(1,N+1):
   l=[k for k in l if k+i<=N]
   for j in l:
      dp[i+j]=(dp[i]+dp[i+j])%mod
print(dp[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
import numpy as np
from numba import njit
def main():
    large_num = 998244353
    n, k = map(int, input().split())
    n -= 1

    s = set()
    m = map(int, read().split())
    ab = zip(m, m)
    for a, b in ab:
        for i1 in range(a, b + 1):
            s.add(i1)
    s = list(s)
    s.sort()
    s = np.array(s)

    @njit()
    def sol(s, n):
        dp = np.zeros(n+1)
        dp[0] = 1
        for i1 in range(1, n+1):
            for se in s:
                if se > i1:
                    break
                else:
                    dp[i1] += dp[i1 - se]
            dp[i1] = dp[i1] % large_num
        return dp[-1]

    print(int(sol(s, n)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
s = []
mod = 998244353
for _ in range(k):
    l, r = map(int, input().split())
    s += [i for i in range(l, r + 1)]

s.sort()

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

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

print(dp[n] % mod)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from io import BytesIO, IOBase

_str = str
str = lambda x=b"": x if type(x) is bytes else _str(x).encode()

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

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


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


input = lambda: sys.stdin.readline().rstrip("\r\n")
def List(): return list(map(int, input().split()))
def Num(): return int(input())

MOD = 998244353


def countWays(arr, m, N):
    count = [0 for i in range(N + 1)]
    count[0] = 1
    for i in range(1, N + 1):
        for j in range(m):
            if i >= arr[j]:
                count[i] += (count[i - arr[j]]) % MOD
    return count[N] % MOD


n, k = List()
s = set()
for i in range(k):
    a, b = List()
    for ele in range(a, b + 1):
        s.add(ele)
s = list(s)
# print(s)
print(countWays(s, len(s), n - 1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil as C, floor as F, sqrt, gcd as G
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ

class Heap:
  def __init__(self, data, reverse=False):
    self.reverse = -1 if reverse else 1
    self.data = [self.reverse * d for d in data]
    HQ.heapify(self.data)
  def push(self, x): return HQ.heappush(self.data, self.reverse * x)
  def pop(self): return self.reverse * HQ.heappop(self.data) 

ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

n, k = I()
steps = set()
mod = 998244353

for _ in range(k):
    l, r = I()
    steps.update([i for i in range(l, r+1)])

ans = 0
heap = Heap([1])
seen = set([1])
cache = D(int)
cache[1] = 1

def go(i):
    for step in steps:
        # print(heap.data, seen, cache)
        t = i + step
        if t <= n:
            cache[t] += cache[i]
            cache[t] %= mod
            if t not in seen:
                heap.push(t)
                seen.add(t)

    
while heap.data:
    go(heap.pop())

print(cache[n])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
S = {}
for i in range(k):
  tmp = list(map(int,input().split()))
  lr = range(tmp[0],tmp[1]+1)
  S = set(lr).union(S)

MOD = 998244353

dp = [0]*(n+1)
dp[1] = 1
for i in range(1,n+1):
  for j in S:
    if i-j > 0:
      dp[i] += dp[i-j]%MOD
print(dp[n]%MOD)

Submission status: Time Limit Exceeded

Solution code:
mod=998244353
def countWays(arr,m,n):
	count=[0 for i in range(n+1)]
	count[0]=1
	for i in range(1,n+1):
		for j in range(m):
			if (i>=arr[j]):
				count[i]+=(count[i-arr[j]])
	return count[n-1]
	
	
	
	

s=set()
n,k=map(int,input().split())
for i in range(k):
	a,b=map(int,input().split())
	for i in range(a,b+1):
		s.add(i)
		

arr=list(s)
m=len(arr)

print(countWays(arr,m,n)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
n,k = map(int, sys.stdin.readline().rstrip("\n").split())
s = []
for _ in range(k):
    l,r = map(int, sys.stdin.readline().rstrip("\n").split())
    for i in range(l,r+1):
        s.append(i)
h = 998244353
ans = 0
c = [1]+[0]*(n-1)
for i in range(1,n):
    for j in s:
        if i-j >= 0:
            c[i] += c[i-j]
            c[i] = c[i] % h
print(c[n-1])

Submission status: Time Limit Exceeded

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

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

d = [0] * N


def func(pos):
    for a in area:
        for i in range(a[0], a[1]+1):
            if pos - i > -1:
                d[pos-i] += d[pos] % 998244353


d[N-1] = 1
for i in range(N-1, -1, -1):
    if d[i] > 0:
        func(i)

print(d[0] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
def I():
    return stdin.readline().rstrip()
def MI():
    return map(int,stdin.readline().rstrip().split())
def LI():
    return list(map(int,stdin.readline().rstrip().split()))
#main part
n,k=MI()
inf=998244353
s=[]
for _ in range(k):
    l,r=MI()
    if l==r:
        s.append(l)
    else:
        for i in range(l,r+1):
            s.append(i)
s.sort()
dp=[0]*(n+2)
for i in range(1,len(dp)):
    if i in s:
        dp[i+1]+=1
    for j in range(len(s)):
        if i-s[j]<0:
            break
        else:
            dp[i]+=dp[i-s[j]]
print(dp[n]%inf)

Submission status: Time Limit Exceeded

Solution code:
import collections

N, K = map(int, input().split())
L = list()
R = list()
for _ in range(K):
    line = list(map(int, input().split()))
    L.append(line[0])
    R.append(line[1] + 1)

dp = [0] * N
dp[0] = 1
for i in range(1, N):
    for left, right in zip(L, R):
        for d in range(left, right):
            if d > i:
                break
            dp[i] += dp[i - d]
            dp[i] %= 998244353
print(dp[-1])

Submission status: Time Limit Exceeded

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

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

dic = dict()
dic[1] = 1

for i in range(1,n+1):
    if i in dic.keys():
        for j in s:
            if i + j in dic.keys():
                dic[i+j] += dic[i]
            else:
                dic[i+j] = dic[i]

if n in dic.keys():
    print(dic[n] % 998244353)
else:
    print(0)

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

result = [1]
for ni in range(1, N):
  result.append(0)
  for l, r in LR:
    for j in range(l, r+1):
      if ni-j<0: continue
      result[ni] = (result[ni]+result[ni-j]) % mod


print(result[N-1])

Submission status: Time Limit Exceeded

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

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

for j in range(1,N):
    for s in S:
        if j + s > N or step[j] == 0:
            continue
        step[j+s] += (step[j]%998244353)
        step[j+s] %= 998244353
print(step[N])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
cc = [list(map(int,input().split())) for i in range(K)]
masu = [1]+[0]*(N-1)
ccc = []
for i,j in cc:
  for k in range(i,j+1):
    ccc.append(k)
ccc.sort()
for i in range(N):
  for j in ccc:
    if i-j>=0:
      if masu[i-j]!=0:
        masu[i]+=masu[i-j]
    else:
      break
print(masu[-1]%998244353)

Submission status: Time Limit Exceeded

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

MOD = 998244353

@njit((i8[:], i8, i8[:]), cache=True)
def call(cell, n, leap):
    for i in range(n):
        if cell[i]:
            for j in leap:
                if i + j < n:
                    cell[i+j] = (cell[i] + cell[i+j])%MOD
    return cell

def main():
    n, k = map(int, sys.stdin.buffer.readline().split())
    leap = set()
    cell = np.array([0]*n, np.int64)
    cell[0] = 1 
    for x in sys.stdin.buffer.readlines():
        l, r = map(int, x.split())
        leap |= set(range(l,r+1)) 
    leap = np.array(list(leap), np.int64)
    c = call(cell, n, leap)
    print(c[-1]%MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

S = []
for i in range(K):
  for j in range(X[i][0], X[i][1]+1): S.append(j)

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

# N-1個目のマスまでdp
for i in range(N-1):
  for j in S:
    if 0 <= i + j <= N-1:
      dp[i+j] += dp[i]
      dp[i+j] %= mod
    else: continue

print(dp[N-1])

Submission status: Time Limit Exceeded

Solution code:

def main():
    mod = 998244353
    n,k = map(int,input().split())
    rngs = []
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(k):
        rngs.append(list(map(int,input().split())))
    for i in range(1,n+1):
        for rng in rngs:
            for j in range(rng[0],rng[1]+1):
                try:
                    dp[i+j] += dp[i]
                except IndexError:
                    continue
    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):
  a,b=map(int,input().split(" "))
  for i in range(a,b+1):
    S.append(i)
S=list(set(S))

G=[0 for i in range(n+max(S))]
G[0]=1

for i in range(n-1):
  for j in range(int(len(S))):
    k=i+S[j]
    G[k]=(G[k]+G[i])%998244353

print(G[n-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.zeros(N+1, dtype=np.int64)
mv = np.zeros(N+1, dtype=np.int64)
for i in range(K):
    l, r = list(map(int, input().split()))
    for j in range(l, r+1):
        mv[j] = 1

def shift_and_add(dp, mv, m, i):
    dp += np.concatenate((np.zeros(i+1, dtype=np.int64), mv[1:N-i+1]*m))
    dp %= MOD
        
dp[1] = 1
for i in range(1, N+1):
    m = dp[i]
    shift_and_add(dp, mv, m, i)

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain
(N,K), *lr = [list(map(int, s.split())) for s in open(0)]
lr.sort()
mstep = lr[0][0]
MOD = 998244353
dp = [0] * (N+1)
dp[1] = 1

steps = list(chain.from_iterable(range(l, r+1) for l, r in lr))

for i in range(2, N+1):
    dp[i] = sum(dp[i-step] for step in steps if i-step >= 1) % MOD
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 998244353
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    LR = [LI() for _ in range(K)]

    # N * KのDP?
    dp = [0] * N
    dp[0] = 1
    for i in range(N):
        for l, r in LR:
            for j in range(i + l, min(i + r + 1, N)):
                dp[j] += dp[i]
                dp[j] %= MOD

    print(dp[-1])

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys

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


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()
    S = []
    for l,r in LR:
        S += list(range(l,r+1))
    dp = [0] *(N+1)
    dp[1] = 1
    for i in range(1, N + 1):
        for s in S:
            if i - s > 0:
                dp[i] += dp[i - s]
                dp[i] %= M
            else:
                break
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import numpy as np
n, k = map(int, input().split())
s_list = []
a_list = np.zeros((n + 1) * 2, dtype=int)
a_list[1] = 1
for i in range(k):
    l, r = map(int, input().split())
    s_list.append([l, r + 1])
for i in range(1, n):
    for l, r in s_list:
        a_list[(i+l):(i+r)] += a_list[i] % 998244353
print(a_list[n] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
n,k=list(map(int,input().split()))
arr=[]
for i in range(k):
    arr.append(list(map(int,input().split())))
    
mod=998244353
m=len(arr)
dp=[0]*(n+1)
dp[1]=1
for i in range(2,n+1):
    cnt=0
    for k in arr:
        for j in range(k[0],k[1]+1):
            if i-j>0:
                cnt=(cnt+dp[i-j])%mod
            else:
                break
    dp[i]=cnt
        
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]
    import numpy as np
    n,k=map(int,input().split())
    a=[0]*n
    a=np.array(a)
    MOD=998244353
    for i in range(k):
      l,r=map(int,input().split())
      a[l-1:r]=1
    dp=[0]*n*2
    dp[0]=1
    dp=np.array(dp)
    for i in range(1,n):
      if dp[i-1]==0:
        continue
      else:
        dp[i:i+n]+=dp[i-1]*a
        dp[i:i+n]%=MOD
    print(dp[n-1])
    
if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

class BIT:
    def __init__(self, n, init=None):
        self.size = n
        if init is None:
            self.v = [0] * (n + 1) # don't use bit[0]
        else:
            self.v = [0] + init
            for i in range(1, n):
                if i + (i & -i) <= n: self.v[i + (i & -i)] += self.v[i]

    def sum(self, i):
        '''
        Calculate a[1] + ... + a[i]
        '''
        S = 0
        while i > 0:
            S += self.v[i]
            i -= i & -i
        return S

    def add(self, i, x):
        '''
        set a[i] to be a[i] + x
        '''
        assert i > 0
        while i <= self.size:
            self.v[i] += x
            i += i & -i

N, K = map(int, input().split())
segments = [tuple(map(int, input().split())) for _ in range(K)]
bit = BIT(N + 1)
bit.v[1] = 1
for i in range(1, N + 1):
    temp = bit.sum(i)
    for s, t in segments:
        if i + s <= N:
            bit.add(i + s, temp)
            bit.add(min(i + t + 1, N + 1), -temp)
print(bit.sum(N) % MOD)

Submission status: Time Limit Exceeded

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

N = 2 * n
# N: 処理する区間の長さ

data0 = [0]*(N+1)
data1 = [0]*(N+1)

mod = 998244353
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        data[k] += x
        data[k] %= 998244353
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def _get(data, k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

add(1, 2, 1)
for i in range(n):
    now = query(i+1, i+2)
    for l, r in lrl:
        add(l+i+1, r+i+2, now)

print(query(n, n+1) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy

q = 998244353

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

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

result = numpy.zeros(N, dtype=int)
result[0] = 1

for i in range(N):
    for l, r in S:
        if i + l >= N:
            break
        if i + r >= N:
            r = N - i - 1
        result[i + l:i + r + 1] = (result[i + l:i + r + 1] + result[i]) % q

print(result[-1])

Submission status: Time Limit Exceeded

Solution code:
# region header
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
import copy
# @lru_cache(maxsize=None)
# sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
# endregion
# region input function


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


# endregion


class RAQ():
    def __init__(self, N, identity):
        """
        Parameters
        ----------
        N: int
            the number of nodes

        identity: int
            queries' identity element
            query = max -> -inf
            query = min -> inf
        """
        self.N = N
        self.depth = (N - 1).bit_length()
        self.N0 = 2 ** self.depth
        self.identity = identity
        self.init_val = 0
        self.data = [self.init_val] * (2 * self.N0)
        self.lazy = [self.init_val] * (2 * self.N0)

    def init_list(self, list):
        """init list directly

        Args:
            list (list(int)): init list
        """
        for i in range(self.N):
            self.update(i, i + 1, list[i])

    def _segfunc(self, left, right):
        res = sum([left, right])
        return res

    def _generate_index(self, l, r):
        """
        Parameters
        ----------
        l,r: int
            target range [l,r) (0-index)

        Return
        ----------
        res: iter(int)
            actually update index
        """
        L = l + self.N0
        R = r + self.N0
        lm = (L // (L & -L)) >> 1  # update target
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1
            R >>= 1
        while L:
            yield L
            L >>= 1

    def _propagates(self, *ids):
        """
        Parameters
        ----------
        ids: iter(int)
            update target
        """
        for i in reversed(ids):
            v = self.lazy[i - 1]
            if not v:
                continue
            self.lazy[2 * i - 1] += v
            self.lazy[2 * i] += v
            self.data[2 * i - 1] += v
            self.data[2 * i] += v
            self.lazy[i - 1] = self.init_val

    def update(self, l, r, x):
        """
        Parameters
        ----------
        l,r: int
            target range [l,r) (0-index)
        x: int
            add value
        """
        L = self.N0 + l
        R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R - 1] += x
                self.data[R - 1] += x
            if L & 1:
                self.lazy[L - 1] += x
                self.data[L - 1] += x
                L += 1
            L >>= 1
            R >>= 1
        for i in self._generate_index(l, r):
            self.data[i - 1] = self._segfunc(self.data[2 * i - 1], self.data[2 * i]) + self.lazy[i - 1]

    def query(self, l, r):
        """
        Parameters
        ----------
        l,r: int
            target range [l,r) (0-index)

        Return
        ----------
        res: int
        """
        self._propagates(*self._generate_index(l, r))
        L = self.N0 + l
        R = self.N0 + r

        s = self.identity
        while L < R:
            if R & 1:
                R -= 1
                s = self._segfunc(s, self.data[R - 1])
            if L & 1:
                s = self._segfunc(s, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def get_list(self):
        """get all list

        Returns:
            list(int): origin list
        """
        for i in range(self.N):
            self._propagates(*self._generate_index(i, i + 1))
        return self.data[self.N0 - 1:self.N0 + self.N - 1]


n, k = inpl()
query = []
for _ in range(k):
    l, r = inpl()
    query.append([l, r])
st = RAQ(n, 0)
st.update(n - 1, n, 1)
for i in range(n, 0, -1):
    for l, r in query:
        if i - l > 0:
            st.update(max(0, i - r - 1), i - l, st.query(i - 1, i))
print(st.query(0, 1) % 998244353)

Submission status: Time Limit Exceeded

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

dp=[0]*(N+1)
dp[1]=1
 
for i in range(2,N+1):
    for j in S:
        if i<j:
            break
        else:
            dp[i]+=dp[i-j]
            dp[i]%998244353

#print(S)
#print(dp)
print(dp[-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys

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


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()
    dp = [0] *(N+1)
    dp[1] = 1
    for i in range(1, N + 1):
        for l,r in LR:
            for s in range(l,r+1):
                if i - s > 0:
                    dp[i] += dp[i - s]
                    dp[i] %= M
                else:
                    break
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K=map(int,input().split())
L=[0]*(N+1)
for i in range(K):
  a,b=map(int,input().split())
  for i in range(a,b+1):
    L[N-i]+=1
qw=[i for i in L]
p=np.poly1d(L)
k=np.poly1d(qw)
ans=0
mod=998244353
s=p.coef
if len(s)>=N:
  ans+=s[-N]

for i in range(N):
  p=p*k
  s=p.coef
  if len(s)>=N:
    ans+=s[-N]
    p=np.poly1d(s[-N:])
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
N, K = map(int, input().split())
MOD = 998244353

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

count = [0]*(N+1)
count[1] = 1
for i in range(1, N+1):
    for k in range(N+1):
        if mark[k] > 0 and (i + k) <= N:
            count[i + k] = (count[i + k] + count[i]) % MOD

print(count[N])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
MOD = 998244353
S = [0] * (N + 1)
for i in range(K):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        S[j] = 1

dp = [0] * N
dp[0] = 1
for i in range(1, N):
    for j in range(1, i + 1):
        if S[j]:
            dp[i] += dp[i - j]
print(dp[-1] % MOD)