結果
問題 | No.2872 Depth of the Parentheses |
ユーザー |
![]() |
提出日時 | 2024-09-06 21:43:36 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 848 bytes |
コンパイル時間 | 13,119 ms |
コンパイル使用メモリ | 297,208 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-06 21:43:51 |
合計ジャッジ時間 | 13,709 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 WA * 5 |
ソースコード
MOD = 998244353i64x, k = read_line.split.map(&.to_i)if k > 200exitenddp0 = Array.new(k + 1) { Array.new(k + 1, 0i64) }dp1 = Array.new(k + 1) { Array.new(k + 1, 0i64) }dp0[0][0] = 1(2 * k).times do |_|dp1.each { |r| r.fill(0i64) }0.upto(k) do |i|0.upto(k) do |j|if i > 0dp1[i - 1][j] += dp0[i][j] * (100 - x)dp1[i - 1][j] %= MODendif i < kdp1[i + 1][{j, i + 1}.max] += dp0[i][j] * xdp1[i + 1][{j, i + 1}.max] %= MODendendenddp0, dp1 = dp1, dp0endans = (k + 1).times.sum { |i| dp0[0][i] * i } % MODans *= pow(inv(100i64), 2 * k)puts ans % MODdef inv(v : Int64)pow(v, MOD - 2)enddef pow(v : Int64, p)ret = 1i64while p > 0if (p & 1i64) != 0ret *= vret %= MODendv *= vv %= MODp >>= 1endretend