首先，抽到一次鬼牌视作一次迭代，那么每次迭代的期望长度是一样的，即
[\begin{aligned} E(x)&=1\times\frac{m}{n+m}+2\times\frac{n}{n+m}\times\frac{m}{n+m-1}+\ldots+(n+1)\times(\prod_{j=0}^{n-1} \frac{n-j}{n+m-j})\times\frac{m}{n+m-n}\ &=\sum_{i=1}^{n+1}\frac{im}{n+m-i+1}\prod_{j=0}^{i-2}\frac{n-j}{n+m-j} \end{aligned} ]
后面那个式子可以预处理，加上求逆元总复杂度是 (O(n\log p))。
然后现在考虑设 (f_i) 表示还有 (i) 个数不在集合里，期望进行的 迭代次数。这个可以递推计算，即
[f_i=\frac{m}{m+k}(f_i+1)+\frac{k}{m+k}f_{i-1} ]
化简得
[f_i=f_{i-1}+\frac{m}{k}]
边界是 (f_0=1)，可以求得 (f_n=1+m\sum_{i=1}^{n}\frac{1}{i})，可以直接 (O(n)) 求出。
最后的答案期望可以直接相乘，就做完了。
点击查看代码
const int N=2e6+13;
int n,m,a[N],inv[N];
int main(){
//file();
read(n),read(m);
a[1]=1;
for(int i=2;i
Original: https://www.cnblogs.com/winterfrost/p/cf1392h-solution.html
Author: cunzai_zsy0531
Title: CF1392H ZS Shuffles Cards 题解
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604295/
转载文章受原作者版权保护。转载请注明原作者出处！