川大校赛的一道概率题

题意

给你有n个英雄，每抽一次卡可得等概率得到一个英雄，问将n个英雄抽全的期望，和第m次抽全n个英雄的概率。

题解

考虑当前已得到k个不同的英雄，在抽一次得到新英雄的概率是(n-k)/n,抽到重复的概率是k/n,所以由几何分布的期望得出，抽出新英雄的期望次数为n/(n-k),现在有k+1个英雄了，按上面的方法继续，综上总的期望是n/n+n/(n-1)+n/(n-2)+...+n/1
现在考虑第二个问题

• 首先m肯定是>=n的
• 如果m>n肯定是存在抽重的情况，我们把每个英雄最先出现的位置确定出来，这些位置之间的区间的元素就是抽重的,我们不关心抽重的是那张卡，也不关心抽出的新卡是那张卡，而是当前区间究竟是抽重还是抽新。
  设这种长度为m的二元序列是最基本的情况单元
• 最后一个抽中的英雄不可能抽重，只有一个，还有第一次抽到的一定是新英雄，所以有n-1个抽重区间(可以为空)，且区间之和为m-n，所以可以把情况单元简化成n-1的自然数序列，和为m-n.
• 考虑一个基本情况，设为{e₁,e₂,e₃,...,e_n-1} 如果已抽i个不同英雄，抽重e_i个:概率为(k/n)^e_i, 抽张新卡概率为(n-i)/n,乘起来就是当前情况的概率
• 把所有的情况找到，把每个情况的概率加起来就是总的概率