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 -*-
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 SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__len = _len
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])
        # ep(self.__tree[self.__size:])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

    def max_right(self, l, f):
        # https://atcoder.jp/contests/practice2/submissions/16636885
        assert 0 <= l <= self.__len
        if l == self.__len:
            return self.__len

        l += self.__size
        sm = self.__ie
        while True:
            while l % 2 == 0:
                l >>= 1
            if not f(self.__op(sm, self.__tree[l])):
                while l < self.__size:
                    l = 2*l
                    if f(self.__op(sm, self.__tree[l])):
                        sm = self.__op(sm, self.__tree[l])
                        l += 1
                return l - self.__size
            sm = self.__op(sm, self.__tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self.__len

    def min_left(self, r, f):
        assert 0 <= r <= self.__len
        if r == 0:
            return 0

        r += self.__size
        sm = self.__ie
        while True:
            r -= 1
            while r > 1 and (r % 2):
                r >>= 1
            if not f(self.__op(sm, self.__tree[r])):
                while r < self.__size:
                    r = 2*r + 1
                    if f(self.__op(sm, self.__tree[r])):
                        sm = self.__op(sm, self.__tree[r])
                        r -= 1
                return r + 1 - self.__size
            sm = self.__op(sm, self.__tree[r])

            if (r & -r) == r:
                break

        return 0

    def __getitem__(self, key):
        return self.__tree[key + self.__size]



@mt
def slv(N, K, LR):
    M = 998244353
    memo = SegmentTree([0] * (N+1), add, 0)
    memo.update(1, 1)
    for i in range(2, N+1):
        v = 0
        for l, r in LR:
            v += memo.query(max(0, i-r), max(0, i-l+1))
            v %= M
        memo.update(i, v)

    return memo[N]


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

    # N = 2 * (10**5)
    # p = [random.randint(1, N) for _ in range(20)]
    # p.sort(reverse=True)
    # LR = []
    # K = 10
    # for i in range(1, 11):
    #     LR.append([2*i-1, 2*i])
    # LR.sort()
    # LR[0][0] = 1
    # print(N, K, LR)

    # print(slv(N, K, LR))



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# coding:utf-8

def main():
    n, k = map(int, input().split())
    lrs = []
    for i in range(k):
        l, r = input().split()
        lrs.append([int(l), int(r)])
    stdOut = solve(n, k, lrs)
    print(stdOut)


"""
方針
和集合の要素の和がn-1と等しくなる組み合わせを考える
和集合の要素の個数の最大はn-1なので、単純に総当たりで行うとO(n^n)



"""

mod = 998244353


def solve(n, k, lrs):
    # 和集合Sの作成
    S = []
    for i in range(k):
        lr = lrs[i]
        l = lr[0]
        r = lr[1]
        for j in range(r - l + 1):
            S.append(l + j)
    S.sort()

    # 参考:https://wakabame.hatenablog.com/entry/2017/09/10/211428
    # p:割られる数 a:整数列 A:求めたい部分和 N:aの要素数
    # 例(998244353, [1, 3, 4], 4, 3) => 4 (1111,13,31,4)
    # この世に出ている部分和数え上げ問題は重複
    p = mod
    a = S
    A = n - 1
    N = len(S)
    dp = [0 for i in range(A + 1)]
    dp[0] = 1
    # dp[i]:部分和iの組み合わせ数
    for i in range(A + 1):
        for ai in a:
            index = i - ai
            if index >= 0:
                dp[i] += dp[index]
        dp[i] = dp[i] % mod
    return dp[-1] % mod


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

lrlist=[]
for _ in range(K):
  l,r=map(int,input().split())
  lrlist.append((l,r))
#print(lrlist)

#A1～Aiまでの和 O(logN)
def BIT_query(idx):
  res_sum = 0
  while idx > 0:
    res_sum += BIT[idx]
    idx -= idx&(-idx)
  return res_sum
#Ai += x O(logN)
def BIT_update(idx,x):
  while idx <= N:
    BIT[idx] += x
    idx += idx&(-idx)
  return  

#初期化
BIT=[0]*(N+1)
BIT_update(1,1)

for i in range(2,N+1):
  for l,r in lrlist:
    left=i-r
    right=i-l    
    if right<1:
      continue
    elif left<1:
      left=1
    
    sum_intv=BIT_query(right)-BIT_query(left-1)
    BIT_update(i,sum_intv)
    
print((BIT_query(N)-BIT_query(N-1))%MOD)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-


def main():
    n, m = map(int, input().split())
    p = [list(map(int, input().split())) for _ in range(m)]
    s = set()
    for pp in p:
        s |= set(range(pp[0], pp[1]+1))
    s = list(s)
    s.sort()
    d = dict()
    d[1] = 1
    for i in range(2, n+1):
        ans = 0
        for ss in s:
            if i-ss > 0:
                ans += d[i - ss]
                ans %= 998244353
        d[i] = ans
    print(d[n] % 998244353)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
li = []
for i in range(K):
  l, r = map(int, input().split())
  for j in range(l, r+1):
    li.append(j)
li.sort()
    
ans = [0] * (N+1)
ans[1] = 1
for i in range(1, N+1):
  if ans[i] > 0:
    for n in li:
      if i+n <= N:
        ans[i+n] += ans[i]
        ans[i+n] %= 998244353
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

MOD=998244353
D=[0]*(N+1)
D[1]=1

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

for i in range(2,N+1):
    for j in S:
        if j >i: break
        D[i]+=D[i-j]
    D[i]%=998244353

#print(S)
print(D[N])

Submission status: Time Limit Exceeded

Solution code:
M=998244353
y=lambda:map(int,input().split())
n,k=y()
q=set()
for i in range(k):
    a,b=y()
    for j in range(a,b+1):q.add(j)
s=[(n,n+1)]
t=[[0,-1]for i in range(n+1)]
t[0]=[1,0]
t[-1]=[0,1]
while s:
    v=s[-1][0]
    if t[v-1][1]<0:
        t[v-1][1]=0
        for i in q:
            if v-i>0:
                if t[v-i-1][1]>=0:t[v-1][0]+=t[v-i-1][0];t[v-i][0]%=M
                else:s.append((v-i,v));t[v-1][1]+=1
    else:
        t[s[-1][1]-1][0]+=t[v-1][0]
        t[s[-1][1]-1][0]%=M
        t[s[-1][1]-1][1]-=1
        s.pop()
print(t[-2][0])

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
def main():
    large_num = 998244353
    n, k = map(int, input().split())
    n -= 1
    jump = set()
    m = map(int, read().split())
    ab = zip(m, m)
    for a, b in ab:
        jump.add((a, b))

    dp = [0] * (n + 1)
    dp[0]=1
    for i1 in range(1, n+1):
        for je in jump:
            for se in range(je[0], je[1]+1):
                if se > i1:
                    break
                else:
                    dp[i1] += dp[i1 - se]
                    dp[i1] = dp[i1] % large_num
    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, k = map(int, input().split())
dp = np.array([0 for i in range(n)])
 
s = []
for i in range(k):
  l, r = map(int, input().split())
  s.append([l,r])
  
dp[0] = 1
for i in range(n):
  for l,r in s:
    dp[i+l:i+r+1] = (dp[i+l:i+r+1] + dp[i]) % 998244353

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
P=998244353
N,K=map(int,input().split())
LR=[]
for _ in range(K):
  l,r=map(int,input().split())
  LR+=range(l,r+1)
LR=list(set(LR))
c=[0]*N
c[0]=1
for k in range(N):
  S=[x for x in LR if x<=k]
  while len(S):
    c[k]+=c[k-S[-1]]%P
    S.pop()
print(c[-1]%P)

Submission status: Time Limit Exceeded

Solution code:
MOD=998244353
N,K=map(int, input().split())
s=set()
for i in range(K):
    l,r=map(int, input().split())
    for i in range(l,r+1):
        s.add(i)
a = list(s)
a.sort()
n = [0]*(N)
n[0]=1
for i in range(N-1):
    p = 0
    for j in a:
        if i + 1 >= j:
            p = (p+n[i-j+1]) % MOD
    n[i+1] = p % MOD
print(n[-1])

Submission status: Time Limit Exceeded

Solution code:
mod=998244353
N,K=[int(r) for r in input().split()]
T=[]
for i in range(K):
  a,b=[int(r) for r in input().split()]
  for j in range(a,b+1):
    T.append(j)
S=set(T)

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]%mod


print(dp[N]%mod)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(k)]
MOD = 998244353
cand = []
for l, r in lr:
    cand += list(range(l, r+1))
    # for i in range(l, r+1):
    #     cand.append(i)
cand.sort()
cand = tuple(cand)
# print(cand)
dp = [0] * (n+1)
dp[0] = 1
for i in range(1, n+1):
    tmp = 0
    for num in cand:
        if i - num >= 0:
            tmp += dp[i-num]
            tmp %= MOD
        else:
            dp[i] = (tmp % MOD)
            break
    dp[i] = (tmp % MOD)
print(dp[-2])

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
import sys
input = sys.stdin.readline  #文字列では使わない
N,K = map(int, input().split())
S =set()
for _ in range(K):
    l,r = map(int, input().split())
    S |=set(list(range(l,r+1)))
S =list(S)
S.sort()
DP =[0]*(N+1)
DP[1] =1
for i in range(1,N+1):
    for s in S:
        if i +s <=N:
            DP[i+s] +=(DP[i])%998244353 
        else:
            break
ans =DP[N] %998244353 
print(ans)

Submission status: Time Limit Exceeded

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

import sys


def main():
    mod = 998244353
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def mi():     return map(int, input().split())    

    n, k = mi()
    intervals = [tuple(mi()) for _ in range(k)]
    N = n
    
    # N: 処理する区間の長さ
    LV = (N-1).bit_length()
    N0 = 2**LV
    data = [0]*(2*N0)
    lazy = [0]*(2*N0)

    def gindex(l, r):
        L = (l + N0) >> 1; R = (r + N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1

    # 遅延伝搬処理
    def propagates(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if not v:
                continue
            lazy[2*i-1] = (lazy[2*i-1] + v) % mod
            lazy[2*i] = (lazy[2*i] + v) % mod
            data[2*i-1] = (data[2*i-1] + v) % mod
            data[2*i] = (data[2*i] + v) % mod
            lazy[i-1] = 0

    # 区間[l, r)にxを加算
    def update(l, r, x):
        *ids, = gindex(l, r)
        propagates(*ids)
        L = N0 + l; R = N0 + r
        while L < R:
            if R & 1:
                R -= 1
                lazy[R-1] = (lazy[R-1] + x) #% mod
                data[R-1] = (data[R-1] + x) #% mod
            if L & 1:
                lazy[L-1] = (lazy[L-1] + x) #% mod
                data[L-1] = (data[L-1] + x) #% mod
                L += 1
            L >>= 1; R >>= 1
    
    # [l] を求める
    def get(l):
        propagates(*gindex(l, l+1))
        return (data[N0+l-1]) % mod



    update(0, 1, 1)
    for i in range(n):
        p = get(i)
        # print(p)
        for l, r in intervals:
            if i + l < n:
                update(i + l, min(i + r + 1, n), p)
    
    # print(query(n-1, n))
    print(get(n-1))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353


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

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

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

    for n in range(2, N + 1):
        for S in SN:
            L, R = S
            #print("n={},L={},R={}".format(n, L, R))
            #print("n-R={}, n-L={}".format(n - R, n - L))
            dp[n] = (dp[n] +
                     sum(dp[max(1, (n - R)):max(0, (n - L)) + 1])) % MOD
            #print(dp)

    print(dp[N])


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())
  S|={i for i in range(l,r+1)}
dp=[0 for _ in range(n+1)]
for i in S:
  dp[i]=1

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# coding:utf-8

def main():
    n, k = map(int, input().split())
    lrs = []
    for i in range(k):
        l, r = input().split()
        lrs.append([int(l), int(r)])
    stdOut = solve(n, k, lrs)
    print(stdOut)


"""
方針
和集合の要素の和がn-1と等しくなる組み合わせを考える
和集合の要素の個数の最大はn-1なので、単純に総当たりで行うとO(n^n)



"""

mod = 998244353


def solve(n, k, lrs):
    # 和集合Sの作成
    S = []
    for i in range(k):
        lr = lrs[i]
        l = lr[0]
        r = lr[1]
        for j in range(r - l + 1):
            S.append(l + j)
    S.sort()

    # 参考:https://wakabame.hatenablog.com/entry/2017/09/10/211428
    # p:割られる数 a:整数列 A:求めたい部分和 N:aの要素数
    # 例(998244353, [1, 3, 4], 4, 3) => 4 (1111,13,31,4)
    # この世に出ている部分和数え上げ問題は重複
    p = mod
    a = S
    A = n - 1
    N = len(S)
    dp = [0 for i in range(A + 1)]
    dp[0] = 1
    # dp[i]:部分和iの組み合わせ数
    for i in range(A + 1):
        for ai in a:
            if ai <= i:
                dp[i] += dp[i - ai]
    return dp[-1] % mod


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
mod=998244353
N,K=[int(r) for r in input().split()]
T=[]
for i in range(K):
  a,b=[int(r) for r in input().split()]
  for j in range(a,b+1):
    T.append(j)
S=set(T)

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]


print(dp[N]%mod)

Submission status: Time Limit Exceeded

Solution code:
# ####################################################################
# import io
# import sys
# _INPUT = """\
# 7 1
# 1 3
# """
# sys.stdin = io.StringIO(_INPUT)
####################################################################
import sys
def _p(*_a):
  #return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
####################################################################
def _pa(_aa):
  #return
  for _a in _aa: _p(_a)
####################################################################
N, K = map(int, input().split())

MOD = 998244353
ans = 0

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

A.sort()

# _p(N,K,A)

M = [0] * (N + 1)
M[1] = 1
for m in range(1,N+1):
  for a in A:
    p = m + a
    # _p(m,a,p,M)
    if p > N: break
    M[p] += M[m]
    M[p] = M[p] % MOD

# _p(M)
print(M[N] % MOD)
exit(0)

M = [0] * (N + 1)
for n in range(2, N+1):
  # print(n)
  if M[n] > 0: continue

  for a in A:
    p = n - a
    if p == 1: M[n] += 1
    if p <= 1: break
    M[n] += M[p] % MOD
    M[n] = M[n] % MOD

_p(M)
print(M[N] % MOD)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
LR = []
for i in range(K):
  L,R = map(int,input().split())
  LR += list(range(L,R+1))
LR = sorted(LR)
MOD = 998244353
dp = [0]*N
dp[0] = 1
for i in range(1,N):
  for j in LR:
    if i-j<0: continue
    else: dp[i] += dp[i-j]
  dp[i] %= MOD
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
def getsum(BITTree, i):
    s = 0  # initialize result

    # index in BITree[] is 1 more than the index in arr[]
    i = i + 1

    # Traverse ancestors of BITree[index]
    while i > 0:
        # Add current element of BITree to sum
        s += BITTree[i]

        # Move index to parent node in getSum View
        i -= i & (-i)
    return s


# Updates a node in Binary Index Tree (BITree) at given index
# in BITree. The given value 'val' is added to BITree[i] and
# all of its ancestors in tree.
def updatebit(BITTree, n, i, v):
    # index in BITree[] is 1 more than the index in arr[]
    i += 1

    # Traverse all ancestors and add 'val'
    while i <= n:
        # Add 'val' to current node of BI Tree
        BITTree[i] += v

        # Update index to that of parent in update View
        i += i & (-i)

    # Constructs and returns a Binary Indexed Tree for given


# array of size n.
def construct(arr, n):
    # Create and initialize BITree[] as 0
    BITTree = [0] * (n + 1)

    # Store the actual values in BITree[] using update()
    for i in range(n):
        updatebit(BITTree, n, i, arr[i])

        # Uncomment below lines to see contents of BITree[]
    # for i in range(1,n+1):
    #     print BITTree[i],
    return BITTree


n,k=map(int,input().split())
c=[]
a=[0]*(n+1)
a[1]=1
BITTree = construct(a,len(a))
mod=998244353
for i in range(k):
    x,y=map(int,input().split())
    c.append([x,y])

for i in range(2,n+1):
    for j in range(len(c)):
        p,q=c[j][0],c[j][1]
        if i-q>0:
            l,r=i-p,i-q

            z=getsum(BITTree,l)-getsum(BITTree,r-1)

            a[i]+=z
            updatebit(BITTree, len(a), i,z)

        else:
            q=i-1
            if i-q>0 and i-p>0:
                l, r = i - p, i - q

                z = getsum(BITTree, l) - getsum(BITTree, r - 1)
                ##z= getsum(BITTree, q) - getsum(BITTree, p - 1)
                ##print(z)
                a[i]+=z
                updatebit(BITTree, len(a), i, z)
                ##print(BITTree)

##print(a)
print(a[n]%mod)

Submission status: Time Limit Exceeded

Solution code:
mod=998244353
n,k=map(int,input().split())
s=set()
for i in range (k):
    x,y=map(int,input().split())
    for m in range (x,y+1):
        s.update([m])

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


for i in range (2,n+1):
    x=0
    for val in s:
        if (i-val)<0:
            continue
        x=x+dp[i-val]
        if x>mod:
            x%=mod
    dp[i]=x

print (dp[n])

Submission status: Time Limit Exceeded

Solution code:
n,k = input().split()
n = int(n)
k = min(int(k),10)
s = []
for j in range(k):
    ins = input().split()
    for i in range(int(ins[0]),int(ins[1])+1):
        s.append(i)
s = list(set(s))
ans = [0]*(n+1)
ans[1]=1
m = 998244353
for j in range(2,n+1):
    for k in s:
        if(k>=j):
            pass
        else:
            ans[j]=(ans[j]%m+ans[j-k]%m)%m
print(ans[-1]%m)

Submission status: Time Limit Exceeded

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

dp = [0] * (n+1)
dp[1] = 1
for i in range(2, n+1):
    # もらうDP
    for l, r in S:
        ll = max(i-r, 0)
        rr = max(i-l+1, 0)
        dp[i] += sum(dp[ll: rr])
        dp[i] %= mod

print(dp[n])

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())
    for j in range(l, r + 1):
        S.append(j)

dp = [0] * N * 10

dp[1] = 1

for i in range(1, N + 1):
    if dp[i] == 0:
        continue
    for s in S:
        if i + s <= N + 1:
            dp[i + s] = (dp[i + s] + dp[i]) % 998244353

print(dp[N])

Submission status: Time Limit Exceeded

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

mod = 998244353
i = 1
dp = [0] * (n+1)
dp[i] = 1
for i in range(n+1):
    if dp[i] == 0:
        continue
    for d in s:
        if i+d <= n:
            dp[i+d] = (dp[i+d] + dp[i]) % mod

print(dp[n] % mod)

Submission status: Time Limit Exceeded

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

S = []
for l, r in A:
    for i in range(l, r + 1):
        S.append(i)

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

for i in range(1, N):
    c = 0
    for j in S:
        if i - j >= 0:
            c += dp[i-j]
    dp[i] = c

print(dp[N-1]%998244353)

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())
    for j in range(l,r+1):
        s.append(j)

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

smax=max(s)

for i in range(0,n):
    for j in range(max(0,i-smax),i):
        if i-j in s:
            dp[i]+=dp[j]

print(dp[n-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
import sys
input = sys.stdin.readline  #文字列では使わない
N,K = map(int, input().split())
S =set()
for _ in range(K):
    l,r = map(int, input().split())
    S |=set(list(range(l,r+1)))
S =list(S)
S.sort()
DP =[0]*(N+1)
DP[1] =1
for i in range(1,N+1):
    for s in S:
        if i +s <=N:
            DP[i+s] +=DP[i]
        else:
            break
ans =DP[N] %998244353 
print(ans)

Submission status: Time Limit Exceeded

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

paths = []
for i in range(K):
    L, R = map(int, input().split(" "))
    paths += list(range(L, R+1))

log = [0] * N
for i in range(N):
    if i == 0:
        log[i] = 1
    for d in paths:
        if i - d >= 0:
            log[i] += log[i-d] % mod

print(log[N-1] % mod)

Submission status: Time Limit Exceeded

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

d_set = set()

for k in range(K):
    L,R = map(int, input().split())
    d_set |= set(list(range(L,R+1)))

dp = [0] * (N+1)
# init
for d in d_set:
    dp[d] = 1

for i in range(N):
    for d in d_set:
        if i+d > N:
            d_set.discard(d)
            break
        dp[i+d] += dp[i]

print(dp[N-1]%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)
s.sort()
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
        else:
            break
print(c[n-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

n,k=map(int,readline().split())
s=set()
for i in range(k):
  l,r=map(int,readline().split())
  s |= set(range(l,r+1))
  
memo=[0]*(n+1)
memo[1]=1
def move(x):
  if memo[x]!=0:
    return memo[x]
  else:
    for j in s:
      if 1<=x-j<=n:
        memo[x]+=move(x-j)
    return memo[x]

print(move(n)%998244353)

Submission status: Time Limit Exceeded

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

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

for i in range(N):
  for l, r in zip(L, R):
    if i - l >= 0:
      dp[i] = (dp[i] + sum(dp[max(0, i - r):i - l + 1])) % mod

print(dp[-1])

Submission status: Time Limit Exceeded

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

MOD = 998244353
P = set()

for l, r in LR:
    _ = [P.add(i) for i in range(l, r + 1)]

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

s[0] = 1

P = sorted(P)

for d in range(N + 1):
    if s[d] == 0:
        continue
    for p in P:
        if d + p < N + 1:
            s[d + p] = s[d + p] % MOD + s[d]
        else:
            break

print(s[N - 1] % MOD)

Submission status: Time Limit Exceeded

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

import sys


def main():
    mod = 998244353
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def mi():     return map(int, input().split())    

    n, k = mi()
    intervals = [tuple(mi()) for _ in range(k)]
    N = n
    
    # N: 処理する区間の長さ
    LV = (N-1).bit_length()
    N0 = 2**LV
    data = [0]*(2*N0)
    lazy = [0]*(2*N0)

    def gindex(l, r):
        L = (l + N0) >> 1; R = (r + N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1

    # 遅延伝搬処理
    def propagates(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if not v:
                continue
            lazy[2*i-1] = (lazy[2*i-1] + v) % mod
            lazy[2*i] = (lazy[2*i] + v) % mod
            data[2*i-1] = (data[2*i-1] + v) % mod
            data[2*i] = (data[2*i] + v) % mod
            lazy[i-1] = 0

    # 区間[l, r)にxを加算
    def update(l, r, x):
        *ids, = gindex(l, r)
        propagates(*ids)
        L = N0 + l; R = N0 + r
        while L < R:
            if R & 1:
                R -= 1
                lazy[R-1] = (lazy[R-1] + x) % mod
                data[R-1] = (data[R-1] + x) % mod
            if L & 1:
                lazy[L-1] = (lazy[L-1] + x) % mod
                data[L-1] = (data[L-1] + x) % mod
                L += 1
            L >>= 1; R >>= 1
    
    # [l] を求める
    def get(l):
        propagates(*gindex(l, l+1))
        return data[N0+l-1]



    update(0, 1, 1)
    for i in range(n):
        p = get(i)
        # print(p)
        for l, r in intervals:
            if i + l < n:
                update(i + l, min(i + r + 1, n), p)
    
    # print(query(n-1, n))
    print(get(n-1))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

LR = [list(map(int, input().split())) for i in range(K)]
S = set()
for i in LR:
    for j in range(i[0], i[1]+1):
        S.add(j)
L = sorted(list(S))

dp = [0 for i in range(N)]
dp[0] = 1
for i in range(1, N):
    x = bisect.bisect(L, i)
    t = L[:x]
    for j in t:
        dp[i] += dp[i-j]
    dp[i] = dp[i] % 998244353

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(300000)

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

S_ = []
for _ in range(K):
    l, r = map(int, input().split())
    S_.append((l,r))
    #S_tmp.update({ l : r })
#S = []


import numpy as np

A = np.array([0 for _ in range(N+1)])

#from functools import lru_cache
#@lru_cache(maxsize=None)

A[1] = 1
for n in range(2,N+1):
    A[n] = sum([ A[max(n-r,1):n-l+1].sum() % L for (l,r) in S_ if l < n ]) % L

print(A[N] % L)

def compute(n):
    if n == 1:
        return 1
    a = 0
    for s in S:
        if s >= n:
            break
        if A[n-s] == 0:
            A[n-s] = compute(n-s)
        a += A[n-s]
    return a % L

#print(compute(N) % L)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = set()
for _ in range(K):
    l, r = map(int, input().split())
    S = S | set(range(l, r + 1))
mod = 998244353

dp = [0 for _ in range(3 * N)]
for s in S:
    dp[s + 1] = 1

S_min = min(S)
for i in range(S_min, N + 1):
    for s in S:
        dp[i] += dp[i - s]
        dp[i] %= mod
print(dp[N] % mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy
import queue

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

i = 1
q = queue.Queue()
for s in S:
    q.put((i, s))

ans = 0
i = 1
while True:
    if q.empty():
        break

    a, b = q.get()

    if N < a + b:
        continue

    if N == a + b:
        ans += 1
        ans = ans % 998244353

    for s in S:
        q.put((a + b, s))

print(ans)