結果
問題 | No.1856 Mex Sum 2 |
ユーザー |
|
提出日時 | 2022-02-28 18:00:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,571 ms / 3,000 ms |
コード長 | 904 bytes |
コンパイル時間 | 132 ms |
コンパイル使用メモリ | 82,356 KB |
実行使用メモリ | 77,104 KB |
最終ジャッジ日時 | 2024-07-06 21:13:27 |
合計ジャッジ時間 | 40,001 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 64 |
ソースコード
def main(): MOD = 998244353 N, M = map(int, input().split()) f = [0] * (min(N, M+1) + 1) DP = [1] + [0] * min(N, M+1) C = 1 for iter in range(1, N+1): C = C * (N-iter+1) * pow(iter, -1, MOD) % MOD mult = pow(M+1, N-iter, MOD) * C % MOD for i in range(min(N, M+1), -1, -1): DP[i] = ( i * DP[i] + (DP[i-1] if i != 0 else 0) ) % MOD f = [(f[i] + mult * DP[i]) % MOD for i in range(min(N, M+1)+1)] ans = 0 for mex in range(1, min(N, M+1)+1): mult = 1 for j in range(1, mex): mult = mult * j % MOD for i in range(mex, min(N, M+1)+1): mult = mult * i % MOD if i != mex: mult = mult * (M-i+1) * pow(i-mex, -1, MOD) % MOD ans = (ans + mex * mult * f[i]) % MOD print(ans) if __name__ == '__main__': main()