結果

問題 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
	}
}
0