CF1392H ZS Shuffles Cards Solution

· · 题解

有 n+m 张牌，其中前 n 张牌上分别标着 1,2,\cdots,n 的数字，后 m 张牌是鬼牌。现在我们打乱这些牌，然后开始抽牌游戏，每一轮你可以抽一张牌：

  • 如果抽到了一张标有数字 x 的牌，就移除这张牌，并将数字 x 加入一个集合 S；

  • 如果抽到了鬼牌，就把移除的牌重新加入牌堆，再次打乱所有牌的顺序，重新开始抽牌，所以洗完牌后牌堆里仍然有 n+m 张牌。如果你抽到了鬼牌，并且集合 S 已经包括了 1,2,\cdots,n 中全部 n 个数，那么抽牌游戏结束。

询问抽牌游戏结束的期望轮数（即抽出的牌数）。

特别提醒：抽到鬼牌不会清空数字集合 S。

NOIP 模拟赛 T3 出 3000 是什么构式场。

可能是作为原来 第一篇题解 的补充，也可能是写给我自己看的。

首先，我们发现，每一轮抽到的牌数，即第一步执行的次数，它是和集合 S 无关的，也就是说，每一轮你抽到的牌数和当前是哪一轮，集合 S 包含什么都无关。所以抽卡游戏期望的抽牌数为：

E=E_{\text{rounds}} \times E_{\text{cards in every round}}.

然后考虑分别怎么求这两个。首先求后者吧。

我们发现，数字牌和数字牌之间是互不影响的。我们记 P_0 表示数字牌之前没有出现鬼牌的概率，那么他等于 \frac{1}{m+1}。原因如下：

数字牌间不干扰，所以我们只考虑这张数字牌和其他 m 张鬼牌，一共有 A_{m+1}^{m+1} 种排列，而数字牌之前没有鬼牌，即数字牌在第一个，一共有 A_m^m 种，则概率 P_0 等于两者之商就是 \frac{1}{m+1}。这里第一篇题解貌似没讲为什么，导致我想了好久，大概是我太菜了。

一张牌在这一轮种被抽到当且仅当它之前没有鬼牌，则抽到牌数的期望是：

E_0=nP_0=\frac{n}{m+1}.

所以每轮抽到牌数的期望是数字牌的期望加上一张鬼牌。

E_{\text{cards in every round}}=E_0+1=\frac{n}{m+1}+1.

然后求前者，轮数的期望。

我们记 E_i 表示还有 i 张数字牌没抽到时抽到一张新牌的期望轮数。则：

E_{rounds}=\sum_{i=1}^n E_i+1。

最后加一是因为抽到最后一张新牌以后还要一直抽到鬼牌结束这一轮。

考虑求解 E_i。首先已经抽到的牌不考虑，则一共还有 m+i 张牌，其中新数字牌 i 张，则抽到新牌的概率是 \frac{i}{m+i}，那么抽新牌的期望抽牌数就是倒数，为 \frac{m+1}{i}=1+\frac{m}{i}。然后它对应的轮数就是抽牌数减一，原因是除了最后一张牌是新牌以外，前面抽到的肯定是鬼牌，标志开启新一轮，所以开启的轮数是：

E_i=1+\frac{m}{i}-1=\frac{m}{i}.

所以：

E_{\text{rounds}}=\sum_{i=1}^n\frac{m}{i}+1=m\sum_{i=1}^n\frac{1}{i}+1=mH_n+1.

其中 H_n 是调和级数和。

再把 E_{\text{rounds}},E_{\text{cards in every round}} 回带入一开始的式子得到：

E=(mH_n+1)\left(\frac{n}{m+1}+1\right).

时间复杂度 O(n\log n)，瓶颈是求调和级数和以及快速幂求逆元。