結果
問題 | No.2872 Depth of the Parentheses |
ユーザー |
![]() |
提出日時 | 2024-09-06 22:20:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 61 ms / 2,000 ms |
コード長 | 998 bytes |
コンパイル時間 | 310 ms |
コンパイル使用メモリ | 82,488 KB |
実行使用メモリ | 63,704 KB |
最終ジャッジ日時 | 2024-09-06 22:21:23 |
合計ジャッジ時間 | 9,473 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 MLE * 5 |
ソースコード
def extgcd(a, b):if b:d, y, x = extgcd(b, a % b)y -= (a // b) * xreturn d, x, yreturn a, 1, 0# 以下modinvdef mod_inv(a, m):g, x, y = extgcd(a, m)if g != 1:raise Exception()if x < 0:x += mreturn xx, K = map(int, input().split())p = 998244353"""dp[i個目まで選んだ][深さj][最大の深さ]"""inv = x*mod_inv(100, p)%pinv2=(100-x)*mod_inv(100,p)%pdp = [[[0 for _ in range(K + 1)] for _ in range(K + 1)] for _ in range(2 * K + 1)]dp[0][0][0]=1for i in range(2 * K):for j in range(K + 1):for k in range(K + 1):# (を選ぶif j < K:dp[i + 1][j + 1][max(j + 1, k)] += dp[i][j][k] * invdp[i + 1][j + 1][max(j + 1, k)] %= pif j != 0:dp[i + 1][j - 1][k] += dp[i][j][k] * inv2dp[i + 1][j - 1][k] %= pans = 0for i in range(K + 1):ans += dp[-1][0][i] * ians%=pprint(ans)