CS Academy Ball Sampling

リンク : https://csacademy.com/contest/archive/task/ball-sampling/

問題概要

N色のボールがあり、箱にそれぞれA_i個入っている。同様に確からしいとき、すべての色のボールを一回以上取り出す期待値を求めよ。

解説

いわゆる、コンプリート問題と言われる、期待値と言えばの典型である。tsutajさんの下のスライドにとてもよくまとめられている。
http://compro.tsutajiro.com/archive/180220_probability_dp.pdf
dp[mask]を1回でも取った色の情報をmaskとして、maskから全色集めるまでの期待値とする。最終的な答えはdp[0]となる。

LL n, a[1100], sum;
double dp[1 << 20];
int main() {
    cin >> n;
    rep(i, n) {
        cin >> a[i];
        sum += a[i];
    }
    Rrep(mask, (1LL << n)) {
        LL cur = 0;
        rep(i, n)if ((mask&(1LL << i)) == 0)cur += a[i];
        double p = sum;
        p /= cur;
        rep(i, n) {
            if ((mask&(1LL << i)) == 0) {
                double q = a[i];
                q /= cur;
                dp[mask] += (dp[mask | (1LL << i)] + p) * q;
            }
        }
    }
    printf("%.15f\n", dp[0]);
    return 0;
}