結果
問題 |
No.2137 Stairs of Permutation
|
ユーザー |
![]() |
提出日時 | 2022-11-28 13:42:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 938 ms / 2,000 ms |
コード長 | 647 bytes |
コンパイル時間 | 354 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 216,244 KB |
最終ジャッジ日時 | 2024-10-05 11:32:33 |
合計ジャッジ時間 | 11,601 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 23 |
ソースコード
mod = 998244353 N = int(input()) N1 = max(N + 1, 4) inv = [1] * N1 for i in range(2, N1): inv[i] = mod - mod // i * inv[mod % i] % mod invpow = [1] * (N + 1) invpow[0] = 0 # Newton's Identities p = [0] * 4 p[0] = N for k in range(1, 4): for i in range(2, N + 1): invpow[i] = invpow[i] * inv[i] % mod p[k] = sum(invpow) % mod e = [1] * 4 for k in range(1, 4): tmp = 0 flag = -1 for i in range(1, k + 1): flag = -flag tmp = (tmp + flag * e[k - i] * p[i]) % mod e[k] = tmp * inv[k] % mod ans = (e[1] + 3 * 2 * e[2] + 6 * e[3]) % mod for k in range(1, N + 1): ans = ans * k % mod print(ans)