Problem: 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.

Submission attempts (in order):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os
    import re
    with open(__file__) as f:
        source = f.read().split('
    for s in source[1:]:
        s = re.sub("'''.*", '', s)
        sp = s.split(maxsplit=1)
        if os.path.dirname(sp[0]):
            os.makedirs(os.path.dirname(sp[0]), exist_ok=True)
        with open(sp[0], 'w') as f:
            f.write(sp[1])

    import nbmodule
    nbmodule.cc.compile()
    exit(0)

from nbmodule import solve
import numpy as np
i8 = np.int64
i4 = np.int32


def main():
    f = open('d4.txt')
    N, K = [int(x) for x in f.readline().split()]
    LR = np.fromstring(f.read(), i8, sep=' ').reshape((-1, 2)).T.copy()
    L = LR[0]
    R = LR[1]
    arg = np.argsort(L)
    left = L[arg]
    right = R[arg]
    w = right - left + 1
    ans = solve(N, left, w)
    print(ans)


if __name__ == '__main__':
    main()

'''

import numpy as np
from numba import njit
from numba.types import i8, i4
from numba.pycc import CC
ni4 = np.int32
ni8 = np.int64
cc = CC('nbmodule')

MOD = 998244353


@cc.export('solve', (i8, i8[:], i8[:]))
def solve(N, left, w):
    l0 = w.max()
    dp_len = N + l0
    dp_prev = np.zeros(dp_len, ni8)
    dp_prev[l0] = 1
    dp = np.zeros(dp_len, ni8)
    left_min = left[0]
    ret = 0
    while l0 + left_min < dp_len:
        for k in range(left.shape[0]):
            pre = 0
            for i in range(l0 + left[k], dp_len):
                cur = pre + dp_prev[i - left[k]] - dp_prev[i - left[k] - w[k]]
                dp[i] += cur
                pre = cur
        ret += dp[-1]
        dp_prev, dp = dp, dp_prev
        dp_prev %= MOD
        dp.fill(0)
        l0 += left_min

    return ret % MOD

if __name__ == '__main__':
    cc.compile()
'''



import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os
    import re
    with open(__file__) as f:
        source = f.read().split('
    for s in source[1:]:
        s = re.sub("'''.*", '', s)
        sp = s.split(maxsplit=1)
        if os.path.dirname(sp[0]):
            os.makedirs(os.path.dirname(sp[0]), exist_ok=True)
        with open(sp[0], 'w') as f:
            f.write(sp[1])

    import nbmodule
    nbmodule.cc.compile()
    exit(0)

from nbmodule import solve
import numpy as np
i8 = np.int64
i4 = np.int32


def main():
    f = open(0)
    N, K = [int(x) for x in f.readline().split()]
    LR = np.fromstring(f.read(), i8, sep=' ').reshape((-1, 2)).T.copy()
    L = LR[0]
    R = LR[1]
    arg = np.argsort(L)
    left = L[arg]
    right = R[arg]
    w = right - left + 1
    ans = solve(N, left, w)
    print(ans)


if __name__ == '__main__':
    main()

'''

import numpy as np
from numba import njit
from numba.types import i8, i4
from numba.pycc import CC
ni4 = np.int32
ni8 = np.int64
cc = CC('nbmodule')

MOD = 998244353


@cc.export('solve', (i8, i8[:], i8[:]))
def solve(N, left, w):
    l0 = w.max()
    dp_len = N + l0
    dp_prev = np.zeros(dp_len, ni8)
    dp_prev[l0] = 1
    dp = np.zeros(dp_len, ni8)
    left_min = left[0]
    ret = 0
    while l0 + left_min < dp_len:
        for k in range(left.shape[0]):
            pre = 0
            for i in range(l0 + left[k], dp_len):
                cur = pre + dp_prev[i - left[k]] - dp_prev[i - left[k] - w[k]]
                dp[i] += cur
                pre = cur
        ret += dp[-1]
        dp_prev, dp = dp, dp_prev
        dp_prev %= MOD
        dp.fill(0)
        l0 += left_min

    return ret % MOD

if __name__ == '__main__':
    cc.compile()
'''



MOD = 998244353


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


def main():
    f = open(0)
    n, k = [int(x) for x in f.readline().split()]
    lr = [[int(x) for x in f.readline().split()] for _ in range(k)]
    dp = [0] * n
    dp[0] = 1
    ans = solve(lr, dp, n)
    print(ans)

main()


Verdicts: Runtime Error

Time Limit Exceeded

Accepted