結果

問題 No.1696 Nonnil
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:30:25
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,219 bytes
コンパイル時間 184 ms
コンパイル使用メモリ 82,024 KB
実行使用メモリ 53,504 KB
最終ジャッジ日時 2025-06-12 21:30:56
合計ジャッジ時間 7,004 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 5 TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 998244353

def main():
    N, K = map(int, sys.stdin.readline().split())
    M = int(sys.stdin.readline())
    intervals = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
    
    intervals.sort()
    
    from itertools import combinations
    total = 0
    for m in range(1, M+1):
        for S in combinations(intervals, m):
            current = []
            for L, R in S:
                if not current:
                    current.append([L, R])
                else:
                    if L > current[-1][1]:
                        current.append([L, R])
                    else:
                        merged_L = current[-1][0]
                        merged_R = max(current[-1][1], R)
                        current[-1] = [merged_L, merged_R]
            total_union = 0
            for L, R in current:
                total_union += R - L + 1
            X = K - total_union
            term = pow(X, N, MOD)
            if m % 2 == 1:
                total = (total + term) % MOD
            else:
                total = (total - term) % MOD
    ans = (pow(K, N, MOD) - total) % MOD
    print(ans if ans >= 0 else ans + MOD)

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