CF#844 F - Bracket Insertion

概要

以下の操作を$ N回行う時、正しい括弧列になる確率は？

・確率$ pで() 、$ 1-pで)(をランダムな位置に挿入する

$ N \leq 500

下の方に解法↓

解法

「()と[]を挿入していき、どの部分のネストも()の方が多い」と言い換える

dp[s][i] = ()の方がs個多いネストの中でi個の括弧を挿入できる確率みたいな感じのdp

遷移は(A)Bと[A]B （先頭の開き括弧とそれに対応する閉じ括弧を取っていく的な）

確率の計算は「まず括弧列を作ってから()か[]を後で決める」と考え、validなものについて以下を掛け合わせる

その括弧の割り当てになる確率

$ p^{（）の個数} * (1-p)^{［］の個数}

dpの遷移時に掛けていけばいい

その括弧の並びになる確率

分子：括弧列を決めてから挿入順を数える

根付き木のトポロジカル順を数えるやつ

$ \frac{N!}{\prod |T_v|}

dpの遷移時に部分木サイズで割っていって$ N!は後で掛ける

分母：挿入出来る場所の個数をかけ合わせる（$ 1*3*5*...）