結果

問題 No.1856 Mex Sum 2
ユーザー qwewe
提出日時 2025-04-24 12:20:44
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 897 ms / 3,000 ms
コード長 1,209 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 82,548 KB
実行使用メモリ 92,892 KB
最終ジャッジ日時 2025-04-24 12:22:23
合計ジャッジ時間 25,343 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 64
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353
max_n = 2000

# Precompute combinations C(n, m) modulo MOD
C = [[0] * (max_n + 1) for _ in range(max_n + 1)]
C[0][0] = 1
for n in range(1, max_n + 1):
    C[n][0] = 1
    for m in range(1, n + 1):
        C[n][m] = (C[n-1][m-1] + C[n-1][m]) % MOD

# Read input
N, M = map(int, input().split())

total = 0
K = min(M, N)

# Handle k from 1 to K
for k in range(1, K + 1):
    current_sum = 0
    for s in range(0, k + 1):
        term = (2 * M - s + 1) % MOD
        term_pow = pow(term, N, MOD)
        sign = (-1) ** s
        comb = C[k][s]
        if sign < 0:
            comb = (-comb) % MOD
        current_sum = (current_sum + comb * term_pow) % MOD
    contribution = k * current_sum % MOD
    total = (total + contribution) % MOD

# Handle k = M+1 if applicable
if M + 1 <= N:
    k = M + 1
    current_sum = 0
    for s in range(0, k + 1):
        term = (2 * (M + 1) - s) % MOD
        term_pow = pow(term, N, MOD)
        sign = (-1) ** s
        comb = C[k][s]
        if sign < 0:
            comb = (-comb) % MOD
        current_sum = (current_sum + comb * term_pow) % MOD
    contribution = (M + 1) * current_sum % MOD
    total = (total + contribution) % MOD

print(total % MOD)
0