给定 $n$ 张卡牌以及每次开出某张卡牌的概率,保证他们相加的概率不大于 1 (也就是说可能有一定概率什么都开不出来,如果开出来了就会按照上述概率出现某一种),求集齐所有牌的期望开卡次数。
设状态 $s$ 是已经抽到的卡的状态, $f_s$ 是 $s$ 要到达都开出来的状态还需要开卡的期望数。显然初始状态有 $f_{2^n-1}=0$ ,然后每一个状态需要看他的二进制位有多少 $0$ ,他可以进行转移的总期望为:抽卡之后可以到达的状态的期望乘以抽到该卡的概率再除以抽到未出现卡片概率的总和。
而在这些转移状态的期望之上,需要当前状态抽出一张从未出现过的卡,需要的期望抽卡次数为 1 除以这些卡片概率的总和。加上即可。复杂度为 $O(n2^n)$ 。
一个类似的题目可以看 CSP202109-4 收集卡牌 ,但是状态稍微复杂一些,写记忆化搜索可能更好想。然后那个题的爆率概率总和是 1 ,而且抽到重复卡之后状态转移是会变的,所以很多细节其实不如这题要考虑的多。
如果这题还考虑重复状态的话,就会非常复杂,可能还得用上高斯消元,但是另一方面,只考虑抽到不同卡的期望就简单了。
#include <stdio.h>
const int N = 1 << 20, LOG_N = 20;
int n, lim;
double p[LOG_N], sum_p;
double dp[N];
void solve()
{
for (int i = 0; i < n; ++i) scanf("%lf", &p[i]);
lim = (1 << n) - 1;
dp[lim] = 0;
for (int s = lim - 1; s >= 0; --s)
{
dp[s] = 0, sum_p = 0;
for (int i = 0; i < n; ++i) if (!(s & (1 << i))) sum_p += p[i];
for (int i = 0; i < n; ++i) if (!(s & (1 << i))) dp[s] += dp[s | (1 << i)] * p[i] / sum_p;
dp[s] += 1.0 / sum_p;
}
printf("%.10f\n", dp[0]);
}
int main() { while (~scanf("%d", &n)) solve(); }