結果

問題 No.1696 Nonnil
コンテスト
ユーザー lam6er
提出日時 2025-04-09 20:58:15
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,679 bytes
コンパイル時間 219 ms
コンパイル使用メモリ 82,968 KB
実行使用メモリ 305,436 KB
最終ジャッジ日時 2025-04-09 21:00:37
合計ジャッジ時間 6,818 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 5 TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N = int(data[ptr])
    ptr += 1
    K = int(data[ptr])
    ptr += 1
    M = int(data[ptr])
    ptr += 1

    intervals = []
    for _ in range(M):
        L = int(data[ptr])
        ptr += 1
        R = int(data[ptr])
        ptr += 1
        intervals.append((L, R))

    dp = {}
    dp[tuple()] = 1  # empty coverage

    for (L, R) in intervals:
        new_dp = {}
        for coverage, weight in dp.items():
            coverage_list = list(coverage)
            # Option 1: do not take this interval
            key = tuple(coverage_list)
            new_dp[key] = (new_dp.get(key, 0) + weight) % MOD

            # Option 2: take this interval, merge with existing coverage
            merged = []
            i = 0
            added = False
            new_L, new_R = L, R
            while i < len(coverage_list):
                s, e = coverage_list[i]
                if e < new_L - 1:
                    merged.append((s, e))
                    i += 1
                elif new_R < s - 1:
                    if not added:
                        merged.append((new_L, new_R))
                        added = True
                    merged.append((s, e))
                    i += 1
                else:
                    new_L = min(new_L, s)
                    new_R = max(new_R, e)
                    i += 1
            if not added:
                merged.append((new_L, new_R))
            # Now, merged may have overlaps, need to merge again
            if not merged:
                final_merged = []
            else:
                final_merged = []
                merged_sorted = sorted(merged)
                current_s, current_e = merged_sorted[0]
                for s, e in merged_sorted[1:]:
                    if s <= current_e:
                        current_e = max(current_e, e)
                    else:
                        final_merged.append((current_s, current_e))
                        current_s, current_e = s, e
                final_merged.append((current_s, current_e))
            key_new = tuple(final_merged)
            new_dp[key_new] = (new_dp.get(key_new, 0) - weight) % MOD
        dp = new_dp

    result = 0
    for coverage, weight in dp.items():
        total_len = 0
        for (s, e) in coverage:
            total_len += e - s + 1
        remaining = K - total_len
        if remaining < 0:
            continue
        power = pow(remaining, N, MOD)
        term = (weight * power) % MOD
        result = (result + term) % MOD

    print(result % MOD)

if __name__ == "__main__":
    main()
0