[AtCoder] M-SOLUTIONS プロコンオープン C – Best-of-(2n-1)

問題

方針

拡張ユークリッドの互除法

\( d = 10^9 + 7 \) とします。

\[ RQ \equiv P \ (\bmod d)\]

上記を満たすような \( R \) をどのように求めるかですが、次の方程式を考えます。

\[ ax \bmod d = b \bmod d \]

ここで、変数 \( s, t \) を用いて、

\[ as + dt = 1 \]

を満たす変数 \( s, t \) の組を一つ見つけます。これは拡張ユークリッドの互除法を用いて求めることができます。 上式の両辺に \( b \) を掛けて、\( d \) で \( \bmod \) を取ると、\( dbt \bmod d = 0 \) より、

\[ asb \bmod d = b \bmod d \]

となるので、\( x = sb \) となります。

また、あまり理解していないんですが、\( R \) は、

\[ R = \dfrac{P}{Q} \bmod d \]

と計算できるようです。\( \dfrac{1}{Q} \bmod d\) については、よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方が詳しいです。

高橋君が最終的に勝利するときのゲーム数の期待値を求める

高橋君が最終的に勝利するときのゲーム数の期待値を求めます。高橋君が勝利した時のゲーム数を \( L \) とします。ここで、\( N \leq L \) を満たすことに注意します。

高橋君が最終的に勝利するとき、青木君が勝つゲームの回数

高橋君が最終的に勝利するとき、青木君が勝つゲームの回数を \( k \ ( 0 \leq k \leq N – 1) \) とします。このとき、引き分けの回数は、\( 0 \) 以上の数となります。長さ \( L \) のゲームにおいて、\( L \) 回目のゲームでは必ず高橋君が勝つことに注意すると、青木君が \( k \) 回勝つときの期待値 \( E[X_k]\) は、

\[ E[X_k] = \left(\dfrac{A}{100} \right)^{N} \cdot  \sum_{i = k}^{\infty} (i + N) \cdot {}_{N + i – 1} \mathrm{ C }_k \cdot \left( \dfrac{B}{100} \right)^{k} \cdot  {}_{N + i – 1 – k} \mathrm{ C }_{i – k} \cdot \left ( \dfrac{C}{100}\right )^{i – k} \]

となります。これは、\( i + N \) 回のゲームに青木君が \( k \) 回勝ち、引き分けが \( i \) 回起きた時の期待値を意味します。無限等比級数の和が出てきてしまいましたが、Wolfram Alpha で次の計算を行うと、

\[
\begin{eqnarray}
f(k) &=& \sum_{i = k}^{\infty} (i + N) \cdot \ {}_{N + i – 1} \mathrm{ C }_k \cdot {}_{N + i – 1 – k} \mathrm{ C }_{i – k} \cdot p^{i – k}\\
&=& \dfrac{Np \cdot {}_{N + k} \mathrm{C}_{k} + (N + k)(1-p) \cdot {}_{N + k – 1} \mathrm{C}_{k}}{(1 – p)^{N + k + 1}}
\end{eqnarray}
\]

が得られます。具体的には、”[sum (i + N) * C(N + i – 1, k)* (q)^{k} * C(N + i – 1 – k, i – k ) * p^{i – k}, {i, k, infinity}]” を実行します。

高橋君が最終的に勝利するときのゲーム数の期待値

高橋君が最終的に勝利するときのゲーム数の期待値 を \( E[X] \) とすると、上記の結果から、

\[
\begin{eqnarray}
E[X] &=& \sum_{k = 0}^{N – 1} E[X_k]\\
&=& A^{N} \cdot \sum_{k = 0}^{N – 1} B^{k} \cdot \dfrac{NC \cdot {}_{N + k} \mathrm{C}_{k} + (N + k)(100 – C) \cdot {}_{N + k – 1} \mathrm{C}_{k}}{(100 – C)^{N + k + 1}}
\end{eqnarray}
\]

となります。計算としては、\( p = \dfrac{C}{100} \) としています。

ゲーム回数の期待値

同様にして、青木君が最終的に勝利するときを考慮すると、ゲーム回数の期待値 \( E[Y]\) は、

\[ E[Y] = A^{N} \cdot \sum_{k = 0}^{N – 1} B^{k} \cdot \dfrac{NC \cdot {}_{N + k} \mathrm{C}_{k} + (N + k)(100 – C) \cdot {}_{N + k – 1} \mathrm{C}_{k}}{(100 – C)^{N + k + 1}} \\ + B^{N} \cdot \sum_{k = 0}^{N – 1} A^{k} \cdot \dfrac{NC \cdot {}_{N + k} \mathrm{C}_{k} + (N + k)(100 – C) \cdot {}_{N + k – 1} \mathrm{C}_{k}}{(100 – C)^{N + k + 1}}\]

となります。

コード

提出したコード

逆元など (けんちょんさんのコード)