排序

根据输入的线段，按l排序

n,m = map(int,input().strip().split())
 
arr = []
for _ in range(m):
    l,r = map(int,input().strip().split())
    arr.append((l,r))
 
arr.sort()

dp

# dp[j] = Counter()
# Counter key (a,b)
#         value 情况数
'''
到第j条线段
[1,a]    覆盖了 2 次数
[a+1,b] 覆盖了 1 次
[b,n]  覆盖了 0 次
'''

枚举第j条线段，对覆盖情况进行状态转移，类似01背包

from collections import Counter
dp = [Counter() for _ in range(m+1)]
 
dp[0][(0,0)] = 1
 
 
for j in range(m):
    l,r = arr[j]
    dp[j+1] = dp[j].copy()
     
    for (la,lb),lt in dp[j].items():
        if l <= la+1:
            a = max(la,min(lb,r))
            b = max(lb,r)
            dp[j+1][(a,b)] += lt

结果获取

枚举dp[-1]即可

res = 0
 
for (a,b),t in dp[-1].items():
    if a == n:
        res += t
        res %= mod
print(res)

python3 代码

n,m = map(int,input().strip().split())

arr = []
for _ in range(m):
    l,r = map(int,input().strip().split())
    arr.append((l,r))

arr.sort()

mod = 998244353
# dp[j] = Counter()
# (a,b)
'''
到第j条线段
[1,a]    覆盖了 2 次数
[a+1,b] 覆盖了 1 次
[b,n]  覆盖了 0 次
'''
from collections import Counter
dp = [Counter() for _ in range(m+1)]

dp[0][(0,0)] = 1


for j in range(m):
    l,r = arr[j]
    dp[j+1] = dp[j].copy()
    
    for (la,lb),lt in dp[j].items():
        if l <= la+1:
            a = max(la,min(lb,r))
            b = max(lb,r)
            dp[j+1][(a,b)] += lt

res = 0

for (a,b),t in dp[-1].items():
    if a == n:
        res += t
        res %= mod
print(res)

呵呵

E题反而没做出来