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: Wrong Answer

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[min(P)] = 1

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]

print(s[N] % MOD)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
N-=1
mvs = set()
mods = 998244353
dps = [0]+[0 for i in range(N)]

for _ in range(K):
  a,b = map(int,input().split())
  for k in range(a,b+1):
    mvs.add(k)

for k in mvs:
  if k < N:
    dps[k]+=1

for i in range(2,N+1):
  for k in mvs:
    dps[i] += dps[i-k] % mods if i-k >0 else 0
print(dps[N]%mods)

Submission status: Wrong Answer

Solution code:
# # Make IO faster
# import sys
# input = sys.stdin.readline

# # get single (or) multiple str
# X = input()

# # get single int
# N = int(input())
# # get multiple int (e.g., 2)
# X, Y = map(int, input().split())
# # get multiple int (e.g., 2) for N lines
# XY = [list(map(int, input().split())) for _ in range(N)]

# from IPython import embed; embed(); exit();

# 全部入り
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, bisect_right
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = list(MAP())
x = []
for i in range(K):
    l, r = list(MAP())
    for j in range(l, r + 1):
        x.append(j)
x = sorted(x)
# print(x)

ans = [0 for _ in range(N)]
ans[0] = 1
for i in range(1, N):
    # print(i, bisect_left(x, i))
    N = min(bisect_left(x, i) + 1, len(x))
    for j in range(N):
        # print(i, j, N)
        ans[i] = (ans[i] + ans[i - x[j]]) % 998244353
print(ans[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
def main():
    MOD = 998244353

    N, K = map(int, input().split())
    move = []
    for i in range(K):
        l, r = map(int, input().split())
        move.extend(list(range(l, r+1)))

    dpt = [[0] * N for i in range(N // min(move))]
    dpt[0][0] = 1

    for i in range(N // min(move) - 1):
        for j in range(N):
            if dpt[i][j] != 0:
                for m in move:
                    if j + m < N:
                        dpt[i+1][j+m] += dpt[i][j]
                        dpt[i+1][j+m] %= MOD

    result = 0
    for i in range(N//min(move)):
        result += dpt[i][-1]
    print(result%MOD)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    ds = set()
    for _ in range(k):
        l, r = map(int, input().split())
        ds = ds | {i for i in range(l, r + 1)}
    dp = [0] * (n + 1)
    dp[1] = 1

    for i in range(2, n + 1):
        for d in ds:
            if i - d < 0:
                break
            dp[i] += dp[i - d] % 998244353

    print(dp[-1] % 998244353)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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())
    S = set()
    for k in range(K):
        L, R = map(int, readline().split())
        S |= set(range(L, R + 1))

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

    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: Wrong Answer

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

dp = [0]*N
dp[0] = 1
dp[1] = -1
for i in range(N):
    dp[i] += dp[i-1]
    dp[i] %= mod
    for s in S:
        if s[0]+i < N:
            dp[s[0]+i] += dp[i]
            dp[s[0]+i] %= mod
        if s[1]+i+1 < N:
            dp[s[1]+i+1] -= dp[i]
            dp[s[1]+i+1] %= mod
print(dp[-1])

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 998244353
EPS = 10**-10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        self.n = n
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            s %= MOD
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            self.tree[i-1] %= MOD
            i += i & -i

    def query(self, l, r):
        """ 区間和の取得 [l, r) """
        return self.sum(r-1) - self.sum(l-1)
    
    def get(self, i):
        """ 一点取得 """
        return self.query(i, i+1)

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

N, K = MAP()
LR = []
for i in range(K):
    l, r = MAP()
    LR.append((l, r))

dp = BIT(N+1)
dp.add(1, 1)
for i in range(2, N+1):
    for l, r in LR:
        cnt = dp.query(max(i-r, 0), max(i-l+1, 0))
        dp.add(i, cnt)
ans = dp.get(N)
print(ans)

Submission status: Wrong Answer

Solution code:
q = 998244353

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

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

result = [0] * N
result[0] = 1

for i in range(N):
    for s in S:
        if i + s < N:
            result[i + s] = (result[i + s] + result[i]) % q
        else:
            break

print(result[-1])

Submission status: Wrong Answer

Solution code:
mod = 998244353
N = int(1e6)
n, k = map(int, input().split())
seg = []
for i in range(k):
    seg.append(tuple(map(int, input().split())))
pref = [1] + [0] * N
for i in range(1, n):
    pref[i] += pref[i - 1] + mod * mod
    for x, y in seg:
        pref[i] += pref[i - x] - pref[i - y - 1]
    pref[i] %= mod
print(pref[n - 1] - pref[n - 2])

Submission status: Wrong Answer

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

print(lis)


dp = [0] * 2 * N
dp[N] = 1
for i in range(1, N):
    for j in lis:
        dp[N + i] += dp[N + i - j]

print(dp[2 * N - 1] % 998244353)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N,K = MI()
LR = [tuple(MI()) for i in range(K)]
mod = 998244353

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

for i in range(2,N+1):
    dp[i] = dp[i-1]
    for j in range(K):
        l,r = LR[j]
        if i-l > 0:
            dp[i] += dp[i-l]-dp[max(i-r-1,0)]
            dp[i] %= mod

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

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
lr = []
for _ in range(k):
  lr.append(list(map(int,input().split())))
print(lr)
imos = [0 for _ in range(n)]
imos[0] = 1
imos[1] = -1
now = 0
mod = 998244353
for i in range(n):
    now += imos[i]
    now %= mod
    #print(now)
    for j in range(k):
        try:
            imos[i+lr[j][0]] += now
            imos[i+lr[j][0]] %= mod
        except:
            pass
        try:
            imos[i+lr[j][1]+1] -= now
            imos[i+lr[j][1]+1] %= mod
        except:
            pass
    #print(imos)
print(now)

Submission status: Wrong Answer

Solution code:
MOD = 998244353

n, k = map(int, input().split())
left=[]
right=[]
for _ in range(k):
    l,r=map(int, input().split())
    left+=[l]
    right+=[r]
pref = [0,1]

for i in range(n-1):
    new = 0
    for j in range(k):
        new += pref[max(0,i+2-left[j])] - pref[max(0,i+1-right[j])]
        #print(pref[max(0,i+2-left[j])], pref[max(0,i+1-right[j])])
    pref.append((pref[-1] + new) % MOD)
print(new)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
LR = inplt(k)

s = []
for l,r in LR:
    for i in range(l,r+1):
        s.append(i)
s.sort(reverse=True)
dp = [0.1] + [1] + [0]*(n-1)

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

def f(x):
    if dp[x] != 0:
        return dp[x]
    else:
        ret = sum(map(f,[x-ss for ss in s if ss < x])) % 998244353
        dp[x] = ret
        return ret

print(f(n))

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
LR = inplt(k)

s = []
for l,r in LR:
    for i in range(l,r+1):
        s.append(i)
s.sort()
dp = [0.1] + [1] + [0]*(n-1)

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

# def f(x):
#     if dp[x] != 0:
#         return dp[x]
#     else:
#         ret = sum(map(f,[x-ss for ss in s if ss < x])) % 998244353
#         dp[x] = ret
#         return ret

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
LR = inplt(k)

s = []
for l,r in LR:
    for i in range(l,r+1):
        s.append(i)
s.sort(reverse=True)
dp = [0.1] + [1] + [0]*(n-1)

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

def f(x):
    if dp[x] != 0:
        return dp[x]
    else:
        ret = sum(map(f,[x-ss for ss in s if ss < x])) % 998244353
        dp[x] = ret
        return ret

print(f(n))

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
LR = inplt(k)

s = []
for l,r in LR:
    for i in range(l,r+1):
        s.append(i)
s.sort()
dp = [0.1] + [1] + [0]*(n-1)

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

def f(x):
    if dp[x] != 0:
        return dp[x]
    else:
        ret = sum(map(f,[x-ss for ss in s if ss < x])) % 998244353
        dp[x] = ret
        return ret

print(f(n))

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
LR = inplt(k)

s = []
for l,r in LR:
    for i in range(l,r+1):
        s.append(i)
s.sort()
dp = [0.1] + [1] + [0]*(n-1)

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

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:

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

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

for i in range(1, N):
    for l, r in X:
        for k in range(l, r + 1):
            if i + k > N:
                break
            dp[i + k] += dp[i]
            dp[i + k] %= MOD

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 998244353

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def main():
    N, K = LI()
    S = []
    for _ in range(K):
        l, r = LI()
        for i in range(l, r+1):
            S.append(i)
    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(N+1):
        for s in S:
            if i - s < 0:
                continue
            dp[i] += dp[i-s]
            dp[i] %= mod
    print(dp[N-1])

main()

Submission status: Time Limit Exceeded

Solution code:
N, K = (int(i) for i in input().split())
l, r = [0]*K, [0]*K
for k in range(K):
    l[k], r[k] = (int(x) for x in input().split())

# dp : マスiまで移動する方法のパターン数
# TLE
'''
import numpy as np
dp = [0]*N
dp[0] = 1
for i in range(N):
    for k in range(K):
        for j in range(l[k], r[k]+1):
            if (i+j < N):
                dp[i+j] = dp[i+j] + dp[i]
            if j == r[k]:
                print(i, (l[k], r[k]), dp, np.diff(dp))
print(dp[-1]%998244353)
'''

# dp : マスiまで移動する方法のパターン数
# dps : dp[i] と dp[i+1] の 差
dp = [0]*N
dps = [0]*(N-1)
dp[0] = 1
dps[0] = -1
for i in range(N-1):
    for k in range(K):
        if i + l[k] - 1 < (N - 1):
            dps[i + l[k] - 1] += dp[i]
        if i + r[k] < (N - 1):
            dps[i + r[k]    ] -= dp[i]
        #print(i, (l[k], r[k]), dp, dps)
    dp[i+1] = dps[i] + dp[i]
print(dp[-1]%998244353)

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(list(range(l,r+1)))
    
dp=[0]*(N+1)
dp[1]=1

for n in range(2,N+1):
    for i in range(1,n):
        if i in S:
            dp[n]=(dp[n]+dp[n-i])%998244353

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)
N, K = map(int, input().split())

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

m = 998244353

S = []
for lr in LR:
    S.extend(range(lr[0], lr[1]+1))

from functools import lru_cache
@lru_cache(maxsize=None)
def getp(n):
    if n < 1:
        return 0
    elif n == 1:
        return 1
    else:
        return sum([getp(n-s) for s in S])%m

print (getp(N))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
 
LR = [list(map(int, input().split())) for _ in range(K)]
 
m = 998244353
 
S = []
for lr in LR:
    S.extend(range(lr[0], lr[1]+1))
 
p = []
 
for i in range(N):
    if i == 0 :
        p.append(1)
    else:
        t = 0
        for s in S:
            if s <= i:
                t += p[i-s]
        p.append(t%m) 
 
print (p[N-1])

Submission status: Time Limit Exceeded

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

dp=[0 for _ in range(n+1)]
dp[1]=1
dpsum=[0 for _ in range(n+1)]
dpsum[1]=1
for i in range(2,n+1):
  for j in range(k):
    li=i-R[j][1]
    ri=i-R[j][0]
    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]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())

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

m = 998244353

S = []
for lr in LR:
    S.extend(range(lr[0], lr[1]+1))

p = []

for i in range(N):
    if i == 0 :
        p.append(1)
    else:
        t = 0
        for s in S:
            if s <= i:
                t += p[i-s]
        p.append(t%m) 

print (p[N-1])

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n, k = map(int, input().split())
    S = []
    L, R = [], []
    for _ in range(k):
        l1, r1 = map(int, input().split())
        L.append(l1)
        R.append(r1)

    dp = [0 for i in range(n + 1)]
    dpsum = [0 for i in range(n + 1)]
    dp[1] = 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(1, Li)
            dp[i] += dpsum[Ri] - dpsum[Li - 1]  # dp[Li] ~ dp[Ri]

        dpsum[i] = dpsum[i - 1] + dp[i]

    print(dp[n] % 998244353)

resolve()

Submission status: Time Limit Exceeded

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

l = [0] * K
r = [0] * K

for i in range(K):
	l[i], r[i] = map(int, input().split())
	
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 li <= 0:
			dp[i] = dp[i] + dpsum[ri]
		else:
			dp[i] = dpsum[ri] - dpsum[li-1] + dp[i]
			
			
	dpsum[i] = dp[i] + dpsum[i-1]
	
print(dp[N] % MOD)

Submission status: Time Limit Exceeded

Solution code:
# coding:UTF-8
import sys
from math import factorial

MOD = 998244353
INF = 10000000000

def main():
    n, k = list(map(int, input().split()))  # スペース区切り連続数字
    lrList = [list(map(int, input().split())) for _ in range(k)]  # スペース区切り連続数字(行列)

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

    Interm = [0] * (n + 1)
    Interm[0] = 0
    Interm[1] = 1
    for i in range(1, n+1):
        if i >= 2:
            for j in s:
                if n - j >= 1:
                    Interm[i] = (Interm[i] + Interm[i - j]) % 998244353

    result = Interm[n]
    # ------ 出力 ------#
    print("{}".format(result))

if __name__ == '__main__':
    main()

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.append((L, R))

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

for i in range(2, N+1):
    for s in S:
        l = i - s[1]
        r = i - s[0]
        if r < 1:continue
        l = max(1, l)

        dp[i] += dpsum[r] - dpsum[l-1]

    dpsum[i] = dpsum[i-1] + dp[i]

print(dp[-1] % 998244353)

Submission status: Time Limit Exceeded

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

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

mod = 998244353

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(1, li)

    dp[i] += dpsum[ri] - dpsum[li - 1]
  
  dpsum[i] = dpsum[i - 1] + dp[i]

print(dp[n] % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    

def main():
    N, K = MI()
    L = [LI() for i in range(K)]
    D = [0] * N
    D[0] = 1
    D[1] = -1
    num = 0
    for index in range(N):
        num += D[index]
        for l, r in L:
            if index + r + 1 <= N-1:
                D[index+l] += num
                D[index+r+1] -= num
            elif index+l <= N-1:
                D[index+l] += num
                
    print(num % 998244353)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
class BIT():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+1)

    #bit_indexにxをO(log(n))で加算する
    def add(self,i,x):
        #if(i<=0 or i>n):return iに0以下の数字は代入しない
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)
    #bit_1 + bit_2 + …  + bit_n をO(log(n))で求める
    def sum(self,i):
        s = 0
        #iに0以下の数字は代入しない。
        while i > 0:
            s+=self.bit[i]
            i -= (i & -i)
        return s
    
    def rangesum(self,i,k):
        return self.sum(k) - self.sum(i)
    #a_1 + a_2 + … + a_i >= x となるような最小のiを求める(a_k >= 0)
    #xが0以下の場合は該当するものなし→0を返す
    def lower_bound(self,x):
        if x <= 0:
            return 0
        else:
            i = 0
            r = 1
            #最大としてありうる区間の長さを取得する
            #n以下の最小の二乗のべき(BITで管理する数列の区間で最大のもの)を求める
            while(r<self.n):
                r=r<<1
            len = r
            while len > 0:
                if(i+len<self.n and self.bit[i+len]<x):
                    x-=self.bit[i+len]
                    i+=len
                len = len >> 1
            return i+1

def main():
    N, K = MI()
    L = [LI() for i in range(K)]
    Bit = BIT(N)
    Bit.add(1,1)
    Bit.add(2,-1)
    for index in range(1,N+1):
        num = Bit.sum(index)
        for l, r in L:
            if index + r + 1 <= N:
                Bit.add(index+l, num)
                Bit.add(index+r+1, - num)
            elif index+l <= N:
                Bit.add(index+l, num)
                
    print(Bit.sum(N) % 998244353)
                
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353

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

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


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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N, K = MI()
    D = [0] * N
    L = [LI() for i in range(K)]
    D[0] = 1
    for index, num in enumerate(D):
        for l, r in L:
            if index + r + 1 <= N:
                D[index+l:index+r+1] = [_+num for _ in D[index+l:index+r+1]]
            elif index+l <= N-1:
                D[index+l:N] = [_+num for _ in D[index+l:N]]
    print(D[N-1] % 998244353)
                
    
    
if __name__ == "__main__":
    main()

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]
            dp[i] %= mod

print(dp[-1]%mod)

Submission status: Time Limit Exceeded

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

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

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

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

print(dp[n]%mod)