CF1392H ZS Shuffles Cards

约瑟夫用脑玩 · 2021-10-06 16:51:41 · 题解

发现这道题和我自己出的一道题很像但还是差一点做出来。

我们可以简单的手玩出抽到一张没抽到过的牌的期望，但此时并不会结束，还可能在此基础上再抽到没抽到过的牌，比如说你欧皇第一轮就把 n 张牌都抽了一次，所以走不通。

换个角度出发，考虑抽到一张鬼牌的期望，这样的好处是所有牌都会被恢复，我们可以考虑恢复前的过程能否抽到没抽过的牌。

手玩一下，发现抽到鬼牌的概率大概长这样：\dfrac{m}{n+m}+\dfrac{n}{n+m}\cdot \dfrac{m}{n+m-1}+\dfrac{n}{n+m}\cdot \dfrac{n-1}{n+m-1}\cdot \dfrac{m}{n+m-2}

写成人看的式子就是 P=\sum_t\dfrac{m\cdot n^{\underline{t-1}}}{(n+m)^{\underline{t}}}

意义也很好解释，枚举选了 t 次时恰好选中，由于要算期望再乘个 t，即 E=\sum_t\dfrac{m\cdot n^{\underline{t-1}}}{(n+m)^{\underline{t}}}t。

考虑在抽到鬼牌前抽的数字牌，发现是这样一个过程：将抽到过的数字牌设为 1 类牌，没抽到过的数字牌设为 2 类牌。

• 抽到 1 类牌忽略

• 抽到 2 类牌则其个数减一

• 抽到鬼牌恢复。

那么每次恢复前执行二操作（使 2 类牌减一）的概率，和执行三操作的概率与一操作始终无关。

而一操作对于每次恢复进行的期望也无关，那么我们用恢复次数期望代替操作期望，就可以在直接忽略一操作的同时计数使 2 类牌减少的期望。

此时过程转化为：

• 抽到 2 类牌使个数减一

• 抽到鬼牌使恢复次数加一

手玩一下可以写出其期望，设 f_k 表示还剩 k 张 2 类牌的期望恢复数，有：

手动消一下元可得： f_k=f_{k-1}+\dfrac{m}{k}

考虑边界有 f_0=1，结束条件恰为抽到一张鬼牌，即恢复一次。

设调和级数 H_n=\sum\limits_{i=1}^n\frac1i，有 f_x=1+mH_x，答案就为 ans=f_nE=(1+mH_n)E。

附代码：

    int i,s;
    n=read();m=read();s=n+m;
    for(fac[0]=i=1;i<=s;i++)fac[i]=Ml(fac[i-1],i);
    for(inv[s]=Inv(fac[s]),i=s-1;~i;i--)inv[i]=Ml(inv[i+1],i+1);
    for(i=1;i<=n+1;i++)
    {
        Add(E,Ml(i,Ml(Ml(fac[n],inv[n-i+1]),Ml(inv[n+m],fac[n+m-i]))));
        if(i>n)break;Add(H,Ml(inv[i],fac[i-1]));
    }
    Mul(E,m);
    writenum(Ml(Ad(1,Ml(m,H)),E),10);