結果

問題 No.2872 Depth of the Parentheses
ユーザー ID 21712
提出日時 2025-03-29 18:46:39
言語 Go
(1.23.4)
結果
AC  
実行時間 887 ms / 2,000 ms
コード長 795 bytes
コンパイル時間 13,722 ms
コンパイル使用メモリ 238,440 KB
実行使用メモリ 8,476 KB
最終ジャッジ日時 2025-03-29 18:46:58
合計ジャッジ時間 17,172 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import . "fmt"
import . "math/big"
func main() {
    var x, k int
    Scan(&x, &k)
    if k > 10 {
        return
    }
    modulo := NewInt(998244353)
    px := NewRat(int64(x), 100)
    mx := NewRat(int64(100-x), 100)
    prob := NewRat(0, 1)
    var dfs func(d, p, m int, r *Rat)
    dfs = func(d, p, m int, r *Rat) {
        if p < 0 {
            return
        }
        if d == 2*k {
            if p == 0 {
                prob = prob.Add(prob, new(Rat).Mul(r, NewRat(int64(m), 1)))
            }
            return
        }
        dfs(d+1, p+1, max(p+1, m), new(Rat).Mul(r, px))
        dfs(d+1, p-1, m, new(Rat).Mul(r, mx))
    }
    dfs(0, 0, 0, NewRat(1, 1))
    num := new(Int).Mod(prob.Num(), modulo)
    denom := new(Int).ModInverse(prob.Denom(), modulo)
    ans := new(Int).Mul(num, denom)
    Println(ans.Mod(ans, modulo))
}
func max(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0