以下の内容はhttps://kanpurin.hatenablog.com/entry/2023/12/17/170322より取得しました。

ABC333 F - Bomb Game 2

問題はこちら

目次

問題概要

${N}$ 人の人が一列に並んでいる．先頭の人を ${\frac{1}{2}}$ の確率で列から取り除き， ${\frac{1}{2}}$ の確率で列の末尾に移す．人 ${i}$ が最後の1人になる確率を求めよ．

${2\leq N\leq 3000}$

解説

${i}$ 人の列で先頭から ${j}$ 番目の人が最後に残る確率を ${P_{i,j}}$ とします．
先頭の人がどうなるかで場合分けを行います．

先頭の人が取り除かれるとき： ${1}$ 番目だった人は取り除かれ， ${j}$ 番目だった人は ${j-1}$ 番目になる．
先頭の人が末尾に移されるとき： ${1}$ 番目だった人は ${i}$ 番目になり， ${j}$ 番目だった人は ${j-1}$ 番目になる．

したがって ${P_{i,j}}$ は以下のようになります．

${P_{1,1}=1}$
${P_{i,1}=\frac{1}{2}P_{i,i} (i\geq 2)}$
${P_{i,j}=\frac{1}{2}P_{i-1,j-1}+\frac{1}{2}P_{i,j-1} (i\geq j\geq 2)}$

${P_{i,1}=\frac{1}{2}P_{i,i}}$ のせいで遷移に循環があります．
${x=P_{i,i}}$ と置くと ${P_{i,j}}$ は ${x}$ の一次式 ${ax+b}$ で表すことができるので， ${j}$ の昇順に ${a,b}$ を持ってDPを行うと ${P_{i,i}=x=ax+b}$ となるため， ${x=\frac{b}{1-a}}$ となります．今回の制約では ${(1-a)\bmod 998244353}$ が ${0}$ になることは無いため正しく求めることができます．時間計算量は ${O(N^2)}$ で，空間計算量は ${O(N)}$ です．

提出プログラム

https://atcoder.jp/contests/abc333/submissions/48609390 (見やすさのため空間計算量O(N^2)で書いてます)

感想

以上の内容はhttps://kanpurin.hatenablog.com/entry/2023/12/17/170322より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます

不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14