题意
给定\(n,m\)，有\(n\)张好牌，\(m\)张坏牌。
每轮游戏如下：
一开始将牌打乱，然后从前往后抓牌，若抓到坏牌，退出此轮，如果所有的好牌都抓过，则结束游戏，否则开启一轮新游戏。
注意之前的某轮抓的牌也称其抓过。
求抓的牌的期望次数。
做法一
\(\begin{aligned} E(抓牌次数)&=\sum\limits_{i=1}^{\infty}E(第i轮的贡献)\\ &=\sum\limits_{i=1}^{\infty}P(前i-1轮没有抓过所有的好牌)\cdot E(第i轮的抓牌次数)\\ &=E(某一轮的抓牌次数)\cdot \sum\limits_{i=1}^{\infty}P(前i-1轮没有抓过所有的好牌)\\ &=E(某一轮的抓牌次数)\cdot E(进行的轮数)\\ \end{aligned}\)
令\(E_1=E(某一轮的抓牌次数)\)，有很多种计算的方式，这里给出一种较为简单的方法。
一定会抓一张坏牌，这里贡献为\(1\)，而一张好牌被抓，概率为在所有坏牌的前面。
故\(E_1=1+\frac{n}{m+1}\)
考虑计算\(E(进行的轮数)\)
令\(f_i\)为：以还有\(i\)张好牌没抓过的状态开始，期望还要抓多少轮
还有\(i\)张好牌没抓过，那么其实\(n-i\)张已经抓过的好牌可以完全忽略了。
那么现在只需要考虑好牌（抓过的全部忽略掉，现在在的均为未抓过的），与坏牌。好牌则继续抓，坏牌则开启下一轮。
即\(f_i=m+1+\sum\limits_{k=2}^i \frac{m}{k}\)
做法二
这里算\(E(进行的轮数)\)有点不同
考虑\(\text{min-max}\)容斥
答案为\(\sum\limits_{i=1}^n {n\choose i}(-1)^{i+1}g_i\)，其中\(g_i\)为钦定\(i\)张好牌，最小的出现轮数的期望
显然\(g_i=\frac{m+i}{i}\)
做法三
来复读一下一个nb做法
考虑\(\text{min-max}\)反演，单独看一个集合\(T\)，令\(k=|T|\)
令\(g_i\)为一轮进行了\(i+1\)次抓牌（即抓了\(i\)张好牌），没有抓过集合\(T\)中牌的概率，令\(G_k(x)\)为生成函数，显然有：
令\(f_i\)为结束时抓了\(i\)次牌的概率，令\(F(x)\)为生成函数，显然有：
\(ans=\frac{dF(x)}{dx}\)，由于\(G_0(1)=1\)，得到：
\(G_0'(1)\)容易在线性时间内求得
考虑\(G_k(1)\)的组合意义：\(T\)集合内的数在第一次出现坏牌的位置后，其余的任意，这种概率，容易得到：\(G_k(1)=\frac{m{n+m\choose n-k}(n-k)!(m+k-1)!}{(n+m)!}\)