题解 | #抽卡#

(f[st]+1)∗∑p[j]=∑j​p[j]∗f[st∣(1<<j)] 看不懂的话就展开来

#include<bits/stdc++.h>
using namespace std;

const int N = 21;

int n;
double f[1<<N],p[N]; //f[st]表示集齐st状态的卡的期望包数

void solve(){
    f[(1<<n)-1]  = 0;
    for(int i = (1<<n) - 2; i>=0 ;i--)
    {
        int st = i;double p_v = 0;
        for(int j=0;j<n;j++){
            if((st >> j & 1) == 0)
                p_v += p[j] , f[i] += p[j] * f[i | (1<<j)];
        }
        f[i] = (f[i]+1.0)/p_v;
    }
    cout << f[0] << endl;
}

int main(){
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> p[i];
    //cout << p[0] << endl;
    solve();
    return 0;
}