题目:HDU 4336
给你N张卡片（和一张空白卡片），每张卡片抽到的概率为\(p_i\)，问抽齐所有卡片的期望抽卡次数（课课课，不课金还是人？）
一遍有两种做法，一为容斥原理，二为由后至前的概率DP
这里提供第三种做法，由前往后的概率DP（算贡献）
首先假设最开始的时候持有一张空白卡片
考虑当前状态为状态\(A\)，到达此状态的概率为\(P(A)\)，持有卡片集合\(S_A\)，剩下卡片集合\(S_A'\)
对于这个状态，它能够转移到下一个状态的抽卡期望为：
\[E = 1 + 2k + 3k^2 + \ldots + nk^{n - 1} + \ldots\]其中，k为持有卡片的概率之和，由等比差数列求和的方法，可以知道\(E = \frac{1}{(1 - k)^2}\)
接下来我们算贡献
设到达\(A\)状态的抽卡期望为\(DP_A\)，则对于\(A\)能转移到的状态\(A+C_i\)（即\(A\)状态抽到卡片\(C_i\)），\(DP_A\)的贡献为
\[\frac{p_iDP_a}{1 - k}\]即转移到下一状态中，这个状态的概率
而抽卡次数的贡献为
\[E\times P(A)\times p_i\]同时，可以计算出此状态的概率对到达下一状态的概率的贡献为
\[\frac{p_iP(A)}{1 - k}\]AC-Code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 20 + 5;
double p[maxn];
double dp[(1 << 20) + 5];
double w[(1 << 20) + 5];
int n;
double sqr(double x) {return x * x;}
void work()
{
p[0] = 1;
for (int i = 1 ; i <= n ; i ++)
{
scanf("%lf" , &p[i]);
p[0] -= p[i];
}
memset(w , 0 , sizeof(w));
memset(dp , 0 , sizeof(dp));
w[0] = 1;
for (int i = 0 ; i < (1 << n) ; i ++)
{
double k = p[0];
for (int j = 0 ; j < n ; j++)
k += p[j + 1] * ((i & (1 << j)) != 0);
for (int j = 0 ; j < n ; j++)
{
if ((i & (1 << j)) == 0)
{
w[i | (1 << j)] += w[i] * p[j + 1] / (1 - k);
dp[i | (1 << j)] += p[j + 1] * dp[i] / (1 - k) + w[i] * p[j + 1] / sqr(1 - k);
// 算贡献
}
}
}
printf("%.6lf\n",dp[(1 << n) - 1]);
}
int main()
{
while (~scanf("%d" , &n))
work();
return 0;
}