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:
class BIT:
    def __init__(self, n, MOD):
        self.n = n
        self.data = [0] * (n + 1)
        self.MOD = MOD

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            s %= self.MOD
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            self.data[i] %= self.MOD
            i += i & -i


n, k = map(int, input().split())
mod = 998244353
bit = BIT(n + 2, mod)
ranges = []
for _ in range(k):
    l, r = map(int, input().split())
    ranges.append((l, r))

bit.add(1, 1)

for i in range(1, n):
    v = bit.sum(i)
    for l, r in ranges:
        bit.add(i + l, v)
        bit.add(min(n + 1, i + r + 1), -v)
print(bit.sum(n) - bit.sum(n - 1) % mod)

Submission status: Wrong Answer

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)
  
dp = [0]*(N+5)
dp[1] = 1

for i in range(2, N+1):
  dp[i] = dp[i-1]
  for j in range(K):
    if i-L[j] >= 0:
      dp[i] += dp[i-L[j]]
    if i-R[j]-1 >= 0:
      dp[i] -= dp[i-R[j]-1]
    dp[i] %= 998244353
    
print(dp[N]-dp[N-1])

Submission status: Wrong Answer

Solution code:
#dpで素直にやるとO(N^2)だから、累積和で高速化しO(KN)にする

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

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

cnt = [0]*n
cnt[0] = 1
sum = [0]*n
sum[0] = 1
for i in range(1,n):
  for j in range(k):
    if i > s[j][1]:
      cnt[i] += (sum[i-s[j][0]] - sum[i-s[j][1]-1]) % mod
    elif i >= s[j][0]:
      cnt[i] += sum[i-s[j][0]] % mod
    sum[i] = (sum[i-1] + cnt[i]) % mod

print(cnt[-1])

Submission status: Wrong Answer

Solution code:
N,K=list(map(int,input().split()))
L=[]
for i in range(K):
    L.append(list(map(int,input().split())))
import sys
sys.setrecursionlimit(10**6)
S=[]
for i in range(K):
    S.extend(j for j in range(L[i][0],L[i][1]+1))
S=sorted(S)
import numpy as np
D=np.zeros(N+1)
D[1]=1
for i in range(2,N+1):
    for j in range(1,i):
        if (i-j) in S:
            D[i]+=D[j]
print(D[N]%998244353)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
x=998244353
S=[]
for i in range(K):
    l,r=map(int,input().split())
    S.append(l)
    S.append(r)
S=list(set(S))
dp=[0 for i in range(N)]
print(S)
for i in range(N):
    for j in range(len(S)):
        if(i-S[j]>0):
            dp[i]+=dp[i-S[j]]
            dp[i]=dp[i]%x
        elif(i-S[j]==0):
            dp[i]+=1
            dp[i]=dp[i]%x
print(dp)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 998244353

class BIT2:
    def __init__(self, N):
        self.N = (N+1)
        self.data0 = [0] * (N+1)
        self.data1 = [0] * (N+1)
        
    def _add(self, data, k, x):
        while k < self.N: #k <= Nと同義
            data[k] += x
            k += k & -k

    def _sum(self, data, k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s

    def add(self, l, r, x):
        self._add(self.data0, l, -x*(l-1))
        self._add(self.data0, r, x*(r-1))
        self._add(self.data1, l, x)
        self._add(self.data1, r, -x)

    def sum(self, l, r):
        return self._sum(self.data1, r-1) * (r-1) + self._sum(self.data0, r-1) - self._sum(self.data1, l-1) * (l-1) - self._sum(self.data0, l-1)
    
N, K = map(int, readline().split())
bit = BIT2(N)
d = []
for _ in range(K):
    L,R = map(int, readline().split())
    d.append((L,R))
    
d = sorted(d)
bit.add(1,2,1)

for i in range(2,N+1):
    for k in range(K):
        L,R = d[k]
        if i-L > 0:
            tmp = bit.sum(max(1,i-R),i-L+1)%MOD
            bit.add(i,i+1,tmp)
        else:
            break
print(bit.sum(N,N+1))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 998244353
N, K = map(int, readline().split())
data = []
for _ in range(K):
    L,R = map(int, readline().split())
    data.append((L,R))
    
data = sorted(data)
dp = [0]*(N+1)
dp[1] = 1
for i in range(2,N+1):
    for k in range(K):
        L,R = data[k]
        if i-L > 0:
            dp[i] += sum(dp[max(0,i-R):i-L+1])%MOD
        else:
            break
print(dp[N])

Submission status: Wrong Answer

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

LR = [map(int, input().split()) for _ in range(K)]
L, R = [list(i) for i in zip(*LR)]

dp = [0]*N
a=[0]*K
dp[0] = 1
for i in range(1, N):
  for j in range(K):
    if L[j] <= i < R[j]:
      a[j]+=dp[i-L[j]]
      dp[i]+= a[j]
    elif R[j] <= i:
      a[j]+=dp[i-L[j]]-dp[i-R[j]-1]
      dp[i]+=a[j]
      
print(dp[N-1] % mod)

Submission status: Wrong Answer

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

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

memo = {}

def dest(n):
  return sum([memo[n-i] for i in s if n-i in memo])

print(s)

for i in range(1, n):
  memo[i] = dest(i) % 998244353
  if i in s:
    memo[i] += 1
    

print(memo[n-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
# import decimal
# from decimal import Decimal
# decimal.getcontext().prec = 10

# from heapq import heappush, heappop, heapify
# import math
# from math import gcd
# import itertools as it
# import collections
# from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

mod = 998244353

N, K = inpl()
left, right = [0] * K, [0] * K
for i in range(K):
    left[i], right[i] = inpl();

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

for i in range(2, N + 1):
    for k in range(K):
        if i - left[k] >= 0:
            dp[i] += wa[i - left[k]] - wa[max(0, i - right[k] - 1)]
        wa[i] = (wa[i-1] +  dp[i]) % mod
print(dp[N])

Submission status: Wrong Answer

Solution code:
MOD = 998244353

n, k = map(int, input().split())
l = [0] * k
r = [0] * k
for i in range(k):
    l[i], r[i] = map(int, input().split())

s = [0] * (n + 2)
for i in range(k):
    for j in range(l[i], r[i] + 1):
        s[j] = 1

ans = [0] * (n + 1)
ans[0] = 1
for i in range(n - 1):
    ans[i + 1] = ans[i]
    for j in range(k):
        ans[i + 1] += ans[max(-1, i + 1 - l[j])] - \
            ans[max(-1, i + 1 - r[j] - 1)]
        ans[i + 1] = ans[i + 1] % MOD
print(ans[n - 1] - ans[n - 2])

Submission status: Wrong Answer

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N,K = map(int,input().split())
    LR = [list(map(int,input().split())) for i in range(N)]

    mod = 998244353

    dp = [0 for i in range(N)]
    dp = np.array(dp)

    left = N
    for i in range(K):
        left = min(left,LR[i][0])

    dp[left-1] = 1

    for i in range(left-1,N):
        for k in range(K):
            l = LR[k][0]
            r = LR[k][1]
            if i + l >= N:
                continue
            else:
                L = i + l
            if i + r >= N:
                R = N - 1
            else:
                R = i + r
            dp[L:R+1] += dp[i]
            dp[L:R+1] %= mod

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



main()

Submission status: Wrong Answer

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

mod=998244353
w=[]
d=[0]*200005
d[1]=1
n,k=map(int,input().split())
for i in range(k):
    a,b=map(int,input().split())
    w.append((a,b))
f=0
for i in range(1,n):
    f+=d[i]
    if d[i]:
        for j,k in w:
            if i+j<=n:
                d[i+j]+=1
                d[min(n+1,i+k+1)]-=1
#    if i==4: break
ans=chk=0
d[1]=0
for i in range(n):
    chk+=d[i]
    d[i]=chk
    ans+=d[i]
    ans%=mod

#print(d[:65])    
print(ans)

Submission status: Wrong Answer

Solution code:
def input_int():
    return(int(input()))

def input_int_list():
    return(list(map(int,input().split())))

def input_int_map():
    return(map(int,input().split()))

def run():
    n, k = input_int_map()

    ranges = []
    for _ in range(k):
        l, r = input_int_map()
        ranges.append((l, r))

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

    for i in range(0, n):
        dp[i] = dp[i - 1]

        for l, r in ranges:
            if i + l < n:
                dp[i + l] += dp[i]

            if i + r + 1 < n:
                dp[i + r + 1] -= dp[i]

    result = dp[-1] % 998244353
    print(result)

run()

Submission status: Wrong Answer

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

LR = [map(int, input().split()) for _ in range(K)]
L, R = [list(i) for i in zip(*LR)]

a = []
for i in range(K):
  a.extend(list(range(L[i], R[i] + 1)))
LR = list(set(a))

print(LR)
DP = [0]*N
DP[0] = 1
for i in range(N):
  if i + LR[-1] > N:
    LR.pop(-1)
  if len(LR) < 1:
    break
  
  for s in LR:
    local = i + s
    if local < N:
      DP[local] += DP[i]


print(DP[N-1] % mod)

Submission status: Wrong Answer

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

LR = [map(int, input().split()) for _ in range(K)]
L, R = [list(i) for i in zip(*LR)]

a = []
for i in range(K):
  a.extend(list(range(L[i], R[i] + 1)))
LR = list(set(a))

print(LR)
DP = [0]*N
DP[0] = 1
for i in range(N):
  if i + LR[-1] >= N:
    LR.pop(-1)
  if len(LR) < 1:
    break
  
  for s in LR:
    local = i + s
    if local < N:
      DP[local] += DP[i]


print(DP[N-1] % mod)

Submission status: Wrong Answer

Solution code:
N,K = [int(i) for i in input().split()]
mod = 998244353
LR = []
S = []
dp = [0]*(N+1)
for i in range(K):
  LR.append([int(i) for i in input().split()])
for i in range(N):
  for lr in LR:
    if lr[0] <= i and i <= lr[1]:
      S.append(i)
S = list(set(S))
#print(S)

for i in range(1,N):
  if i in S:
    dp[i] = 1
  for j in range(len(S)):
    if i-S[j] < 1:
      break
    print(i, S[j], i-S[j])
    dp[i] += 1*dp[i-S[j]]
    dp[i] %= mod

print(dp[-2])

Submission status: Wrong Answer

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

dp = [0] * (n + 1)
acc = [0] * (n + 1)
dp[1], acc[1] = 1, 1
for i in range(2, n + 1):
    for l, r in lr:
        dp[i] += acc[max(i - l, 0)]
        dp[i] -= acc[max(i - r, 0)]
    dp[i] %= mod
    acc[i] = (dp[i] + acc[i - 1]) % mod
print(dp[n])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
def main():
    import numpy as np

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

    dp = np.zeros(N + 1, dtype=np.int64)
    dp[1] = 1
    cumsum = np.zeros(N + 1, dtype=np.int64)
    cumsum[1] = 1
    for i in range(2, N + 1):
        for left_section, right_section in section:
            left = max(i - right_section - 1, 0)
            right = i - left_section
            if right < 0:
                continue
            dp[i] += cumsum[right] - cumsum[left]
        cumsum[i] = cumsum[i - 1] + dp[i]
    print(dp[-1] % MOD)
    # print(dp)
    # print(cumsum)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

for i in range(N):
  for j in range(K):
    dp[i]+=dpc[max(i-L[j]+1,0)]-dpc[max(i-R[j],0)]
  dpc[i+1]=dpc[i]+dp[i]

print(dp[N-1])

Submission status: Wrong Answer

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

def input_int_array():
    return map(int, input().split())


def answer():
    n, k = input_int_array()
    spans = [tuple(input_int_array()) for x in range(k)]

    count = [0 for x in range(n)]
    count[0] = 1

    for i in range(n):
        if i > 0:
            count[i] += count[i-1]
        for j in range(k):
            l, r = spans[j]
            for lr in range(l, r + 1):
                if i + lr < n:
                    count[i + lr] += count[i]
                else:
                    break
    print(count[-1] % 998244353)


answer()

Submission status: Wrong Answer

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)]
    n,k=map(int,input().split())
    MOD=998244353
    lr=[list(map(int,input().split())) for _ in range(k)]
    dp=[0]*(n+1)
    dpsum=[0]*(n+1)
    dp[1]=1
    dpsum[1]=1
    for i in range(2,n+1):
      for l,r in lr:
        li=i-r
        ri=i-l
        if r<0:continue
        li=max(1,li)
        dp[i]+=dpsum[ri]-dpsum[li-1]
      dpsum[i]=(dpsum[i-1]+dp[i])%MOD
    print(dp[n])
    
if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
n,k = (int(x) for x in input().split())
lr = []
for _ in range(k):
    l,r = (int(x) for x in input().split())
    lr.append((l,r))
lr.sort()
print(lr)

mod = 998244353

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

for i in range(2,n+1):
    cnt = 0
    for l,r in lr:
        if l >= i:
            break
        else:
            cnt += dp[i-l] - dp[max(0,i-r-1)]
    dp[i] = (dp[i-1] + cnt) % mod

print(cnt%mod)

Submission status: Wrong Answer

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

mod = 998244353

n, k = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(k)]

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

for i in range(1, n):
    dp[i+1] += dp[i]
    for l, r in lr:
        dp[i+1] += dp[max(i-l+1, 0)] - dp[max(i-r, 0)]
        dp[i+1] %= mod

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

Submission status: Wrong Answer

Solution code:
def main():
    mod=998244353
    n,k=map(int,input().split())
    region=[]
    for _ in range(k):
        a,b=map(int,input().split())
        region.append((a,b))

    #dp[i]はマスiに行く方法の個数
    #workにdp[i-1]からの増減分を保持
    dp=[0]*(n+1)
    work=[0]*(n+1)

    #initialize
    for j in region:
        if 1+j[0]<=n:
            work[1+j[0]]=1
        if 1+j[1]+1<=n:
            work[1+j[1]+1]=-1    

    for i in range(2,n+1):
        dp[i]=dp[i-1]+work[i]
        dp[i]%=mod
        for j in region:
            if i+j[0]<=n:
                work[i+j[0]]+=dp[i]
                work[i+j[0]]%=mod
            if i+j[1]+1<=n:
                work[i+j[1]+1]-=dp[i]
                work[i+j[1]+1]%=mod
    print(dp[n])


main()

Submission status: Wrong Answer

Solution code:
import math

CON = 998244353

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

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

def solve():
    dp[1] = 1
    cs[1] = 1

    for i in range(2, N + 1):
        for pts in LR:
            if i - pts[0] > 0: dp[i] += cs[i-pts[0]] 
            if i - pts[1] > 0: dp[i] -= cs[i-pts[1] + 1] 
        dp[i] = dp[i] % CON
        cs[i] = (cs[i-1] + dp[i]) % CON

    print(dp[N])

solve()

Submission status: Wrong Answer

Solution code:
import math

CON = 998244353

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

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

def solve():
    dp[1] = 1
    cs[1] = 1

    for i in range(2, N + 1):
        for pts in LR:
            if i - pts[0] > 0: dp[i] += cs[i-pts[0]] 
            if i - pts[1] > 0: dp[i] -= cs[i-pts[1]] 
        dp[i] = dp[i] % CON
        cs[i] = (cs[i-1] + dp[i]) % CON

    print(dp[N])

solve()

Submission status: Wrong Answer

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

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

dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
    for j in s:
        dp[i] += dp[max(i - j, 0)]
    dp[i] %= mod
print(dp)

Submission status: Wrong Answer

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

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

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

print(dp[-1])

Submission status: Wrong Answer

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

LR = [map(int, input().split()) for _ in range(K)]
L, R = [list(i) for i in zip(*LR)]
L.extend(R)
LR = list(set(L))

DP = [0]*N
DP[0] = 1
for i in range(N):
  for s in LR:
    local = i + s
    if local < N:
      DP[local] += DP[i]
print(DP[N-1] % 998244353)

Submission status: Wrong Answer

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), 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):
    if a_list[i] > 998244353:
        a_list[i] %= 998244353
    if a_list[i] == 0:
        continue
    for l, r in s_list:
        if i + l > n:
            continue
        if i + r > n + 1:
            a_list[(i+l):(n+1)] += a_list[i]
        else:
            a_list[(i+l):(i+r)] += a_list[i]
print(a_list)
print(a_list[n] % 998244353)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n, k = map(int, input().split())
l = [0]*(n+10)
imos = [0]*(n+10)
mod = 998244353

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

s = []
for i in range(len(imos)):
    if i <= n and imos[i] == 1:
        s.append(i)
s.sort()
dp = [0]*(n+2)
dp[1] = 1

for i in range(1,n+1):
    for ss in s:
        if i+ss>n:continue
        if imos[i] == 1:
            dp[i+ss] += dp[i]
            imos[i+ss] = 1
            dp[i+ss] %= mod

print(dp[n]%mod)

Submission status: Wrong Answer

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


class FenwickTree:
    def __init__(self, n:int, mod:int = 0):
        self.__mod = mod
        self.__n = n
        self.__data = [0] * self.__n

    def add(self, p:int, x:int):
        assert (0 <= p) & (p < self.__n)
        if(self.__mod == 0):
            self.__add_mod0(p,x)
        else:
            self.__add_mod(p,x)

    def __add_mod0(self, p:int, x:int):
        p+=1
        while( p<= self.__n):
            self.__data[p-1] += x
            p += p & -p

    def __add_mod(self, p:int, x:int):
        p+=1
        while( p<= self.__n):
            self.__data[p-1] += x
            self.__data[p-1] %= self.__mod
            p += p & -p

    def sum(self, l:int, r:int):
        assert (0 <= l) & (l <= r) & (r <= self.__n)
        if(self.__mod == 0):
            return self.__sum_mod0(r) - self.__sum_mod0(l)
        else:
            return self.__sum_mod(r) - self.__sum_mod(l)

    def __sum_mod0(self, r:int):
        s = 0
        while(r > 0):
            s += self.__data[r-1]
            r -= r & -r
        return s

    def __sum_mod(self, r:int):
        s = 0
        while(r > 0):
            s += self.__data[r-1]
            s %= self.__mod
            r -= r & -r
        return s
    
    def get_data(self):
        return self.__data

dp = FenwickTree(n=N+1, mod=MOD)
dp.add(1, 1)
for i in range(2, N+1):
    for l, r in LR:
        ll = max(0, i - l)
        rr = max(0, i - r)
        dp.add(i, dp.sum(rr, ll+1))

print(dp.sum(N, N+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())
    s+=(list(range(l,r+1)))
S= set(s)

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

step[0]=1
for i in range(n):
    for s in S:
        if i+s<=n:
            step[i+s]=(step[i]+step[i+s])%mod
        else:
            break

print(step[n-1]%mod)

Submission status: Wrong Answer

Solution code:

def input_int():
    return(int(input()))

def input_int_list():
    return(list(map(int,input().split())))

def input_int_map():
    return(map(int,input().split()))

def run():
    n, k = input_int_map()

    ranges = []
    for _ in range(k):
        l, r = input_int_map()
        ranges.append((l, r))

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

    for i in range(0, n):
        dp[i] = dp[i - 1]

        for l, r in ranges:
            if i + l < n:
                dp[i + l] += dp[i]

            if i + r < n:
                dp[i + r] -= dp[i]

    result = dp[-1] % 998244353
    print(result)

run()

Submission status: Wrong Answer

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

mod = 998244353

m_list = []

for _ in range(k):
    m_list.append(list(map(int, input().split())))

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

dp_sum = [0]*n
dp_sum[0] = 1

for i in range(1, n):
    for j in range(k):
        l, r = m_list[j]
        dp[i] += dp_sum[i-l] - dp_sum[i-r-1]
        if dp[i] < 0:
            dp[i] = 0
    dp_sum[i] = dp_sum[i-1] + dp[i]

print(dp[n-1] % mod)

Submission status: Wrong Answer

Solution code:

def input_int():
    return(int(input()))

def input_int_list():
    return(list(map(int,input().split())))

def input_int_map():
    return(map(int,input().split()))

def run():
    n, k = input_int_map()

    ranges = []
    for _ in range(k):
        l, r = input_int_map()
        ranges.append((l, r))

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

    for i in range(1, n):
        dp[i] = dp[i - 1]

        for l, r in ranges:
            if i + l < n:
                dp[i + l] += dp[i]

            if i + r < n:
                dp[i + r] -= dp[i]

    result = dp[-1] % 998244353
    print(result)

run()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
cum = [0, 1]
dp = [0, 1]

lr = [list(map(int, input().split())) for _ in range(k)]    
mod = 998244353
# i: 目標のマス
def check(i):
    res = 0
    for l, r in lr:
        if i - l < 1:
            break
        res += cum[i-l] - cum[max(i-r-1,0)]
        res %= mod
    return res


for i in range(2,n+1):
    dp.append(check(i))
    cum.append((cum[-1]+dp[-1])%mod)

print(dp[-1])

Submission status: Wrong Answer

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

dp = [0]*(n+1)
dp[0] = 1
dp2 = [0]*(n+1)
for i in range(n):
    dp[i] = (dp[i]+dp2[i]+dp2[i-1])%mod
    dp2[i] = (dp2[i]+dp2[i-1])%mod
    for l,r in K:
        dp2[min(i+l,n)] = (dp[i]+dp2[min(i+l,n)])%mod
        dp2[min(i+r+1,n)] = (dp[i]+dp2[min(i+r+1,n)])%mod
print(dp[n-1]%mod)

Submission status: Wrong Answer

Solution code:
import itertools
import math

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)


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

kukan = []
for i in range(K):
    a,b=input().split()
    kukan.append((int(a), int(b)))

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

# 計N-1回の移動
# 集合Sから重複有りで数を選び，その和がN-1となればよい

i = 1
ans = 0

while True:
    h = itertools.product(S, repeat=i)
    flag = 0
    length = 0
    for v in h:
        length += 1
        s = sum(v)
        if s == N-1:
            print(v)
            ans += 1
        elif s > N-1:
            flag += 1
    if flag == length:
        break

    i += 1

print(ans%998244353)

Submission status: Wrong Answer

Solution code:
import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

def resolve():
    n, k = map(int, input().split())

    tree = SegmentTree([0] * n, lambda x, y:(x+y)%MOD, 0)
    tree.update(0, 1)
    D = [tuple(map(int, input().split())) for _ in range(k)]

    for i in range(1, n):
        for l, r in D: # [i - r, i - l]
            if i - l >= 0:
                tree.add(i, tree.sum(i - r, i - l + 1))
    print(tree[n - 1] % MOD)
resolve()

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    move_set = set([])

    for i in range(k):
        a, b = map(int, input().split())
        for j in range(a, b + 1):
            move_set.add(j)
    sorted_set = sorted(move_set)
    print(sorted_set)
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n+1):
        for num in sorted_set:
            if num + 1 > i:
                break
            else:
                dp[i] += dp[i - num]
    print(dp[-1] % 998244353)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def resolve():
    n, k = map(int, input().split())
    mod = 998244353
    dp = [0] * (3*n)
    imos = [0] * (3*n)
    lr = []
    for i in range(k):
        l, r = map(int, input().split())
        lr.append((l, r+1))
    for l, r in lr:
        imos[l] = 1
        imos[r] = -1
    for i in range(1, n+1):
        dp[i] = (dp[i-1] + imos[i]) %mod
        for l, r in lr:
            imos[min(i+l, n+2)] += dp[i]
            imos[min(i+r, n+2)] += -1*dp[i]
    print(dp[n-1]%mod)

resolve()

Submission status: Wrong Answer

Solution code:
n,k = input().split()
goal = int(n)
loup = int(k)
total = set()
dp = [0] * (goal + 1)
dp[0] = 1



#集合の作成
for k in range(loup):
	a,b = map(int, input().split())
	l = set(range(a,b+1))
	total = total | l

#main
for i in range(1,goal+ 1):
	for n in range(1,max(total) + 1):
		if n not in total:
			continue
        
		if i-n >= 0:
			dp[i] = dp[i] + dp[i-n]

print(dp[goal] % 998244353)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
lr=[]
for i in range(k):
  l_,r_=map(int,input().split())
  lr.append([l_,r_])
ans=[0]*n


from itertools import accumulate

pra=0
minus=0
for i in range(n):
  
  if i==0:
    for l,r in lr:
      if r<=n-2:
        ans[l]+=1
        ans[r+1]+=-1
      else:
        if l<=n-1:
          ans[l]+=1
  if ans[i]==1:
    pra+=1
  elif ans[i]==-1:
    minus+=1
  if pra-minus>=1:
    for l,r in lr:
      if i+r<=n-2:
        ans[i+l]+=1
        ans[i+r+1]+=-1
      else:
        if i+l<=n-1:
          ans[i+l]+=1
   
ans=list(accumulate(ans))
print(ans[n-1]%998244353)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
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()
steps = [0] * (n+1)
mod = 998244353

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

ans = 0
# heap = Heap([1])
# seen = set([1])
# cache = D(int)
# cache[1] = 1
cache = np.array([0] * (n+1))
cache[1] = 1

for i in range(1, n):
    if cache[i] == 0:
        continue
    now = np.array([0] * i + steps[:-i])
    cache = cache + (cache[i] * now)
    
print(cache[n] % mod)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
lr=[]
for i in range(k):
  l_,r_=map(int,input().split())
  lr.append([l_,r_])
ans=[0]*n


from itertools import accumulate

pra=0
minus=0
for i in range(n):
  print(ans)
  if i==0:
    for l,r in lr:
      if r<=n-2:
        ans[l]+=1
        ans[r+1]+=-1
      else:
        if l<=n-1:
          ans[l]+=1
  if ans[i]==1:
    pra+=1
  elif ans[i]==-1:
    minus+=1
  if pra-minus>=1:
    for l,r in lr:
      if i+r<=n-2:
        ans[i+l]+=1
        ans[i+r+1]+=-1
      else:
        if i+l<=n-1:
          ans[i+l]+=1
   
ans=list(accumulate(ans))
print(ans[n-1]%998244353)

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    move_set = set([])

    for i in range(k):
        a, b = map(int, input().split())
        move_set.add(a)
        move_set.add(b)
    sorted_set = sorted(move_set)
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(1, n+1):
        for num in sorted_set:
            if i + num <= n:
                dp[i + num] += dp[i]
            else:
                break
    print(dp[-1] % 998244353)


if __name__ == "__main__":
    main()