[AtCoder] ABC 184 D – increment of coins

問題

方針

\( d(i, j, k) \) を金貨が \( i \) 枚、銀貨が \( j\) 枚、銅貨が \( k \) 枚であるときの確率とします。初期値は、\( d(A, B, C) = 1 \) で、その他は \( 0 \) で初期化します。ここで、\( d(i, j, k) \) の遷移先を考えます。ある操作で、増える硬貨は \( 1 \) 種類なので、

\begin{eqnarray}
d(i + 1, j, k) &\leftarrow& d(i + 1, j, k) + \dfrac{i}{i + j + k} d(i, j, k)\\
d(i, j + 1, k) &\leftarrow& d(i, j + 1, k) + \dfrac{j}{i + j + k} d(i, j, k)\\
d(i, j, k + 1) &\leftarrow& d(i, j, k + 1) + \dfrac{k}{i + j + k} d(i, j, k)
\end{eqnarray}

となります。

したがって、答えは

\[ \sum_{i = 0}^{99} \sum_{j = 0}^{99} (100 + i + j – A – B – C)(d(100, i, j) + d(i, 100, j) + d(i, j, 100))\]

となります。

コード