結果

問題 No.1696 Nonnil
ユーザー 已经死了
提出日時 2025-08-05 23:54:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 223 ms / 3,500 ms
コード長 1,831 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 92,368 KB
最終ジャッジ日時 2025-08-05 23:54:23
合計ジャッジ時間 6,781 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda: sys.stdin.readline().rstrip()

mod = 998244353
INF = 10**18

# 1. 读入 n, k, m
n, k = map(int, input().split())  # n: 序列长度, k: 值域上界
m = int(input())                  # 区间个数

# 2. 预处理每个起点 i 最晚要打点的位置 g[i]
g = [INF]*k
for _ in range(m):
    l, r = map(int, input().split())
    l -= 1
    if r < g[l]:
        g[l] = r

# 从右往左做一个前缀最小化
for i in range(k-2, -1, -1):
    if g[i+1] < g[i]:
        g[i] = g[i+1]

# 3. 初始化 dp 和前缀和 sumv
# dp[j][r] = 选了 j 个点，最后一个打在 r 的方案数
dp = [[0]*(k+1) for _ in range(k+1)]
sumv = [0]*(k+1)

dp[0][0] = 1   # 还没开始就选了 0 个点，算 1 种
sumv[0] = 1

# 4. 逐个位置 i（对应 C++ 里 0..k-1）
for i in range(k):
    # 如果 g[i] != INF，强制在 [i, g[i]) 之间至少打一个点
    if g[i] != INF:
        for j in range(k+1):
            # 把所有还没在 [i, g[i]) 打点的方案扣掉
            dp[j][g[i]] = (dp[j][g[i]] - sumv[j]) % mod
            sumv[j] = 0

    # 普通的“选 / 不选”转移
    for j in range(k-1, -1, -1):
        v = dp[j][i]  # 当前位置 i, 已打 j 个点的方案数
        # 如果在 i 打第 j+1 个点
        sumv[j+1] = (sumv[j+1] + v) % mod
        # 如果不在 i 打，保持 j 个点
        sumv[j]   = (sumv[j]   - v) % mod
        # 状态从 dp[j][i] 迁移到 dp[j+1][i+1]
        dp[j+1][i+1] = (dp[j+1][i+1] + v) % mod
        # 清空旧状态
        dp[j][i] = 0

# 5. 把“打了 i 个点的方案数” 转成 “序列数” 并累加
res = 0
for i in range(k+1):
    # dp[i][k] 就是选了 i 个点且走完所有位置的方案数
    cnt = dp[i][k]
    # i^n % mod
    pw = pow(i, n, mod)
    res = (res + cnt * pw) % mod

# 6. 输出结果
print(res)
0