題意
給你有n個(gè)英雄简烘，每抽一次卡可得等概率得到一個(gè)英雄亏狰，問(wèn)將n個(gè)英雄抽全的期望桦沉，和第m次抽全n個(gè)英雄的概率每瞒。
題解
考慮當(dāng)前已得到k個(gè)不同的英雄，在抽一次得到新英雄的概率是(n-k)/n,抽到重復(fù)的概率是k/n,所以由幾何分布的期望得出纯露，抽出新英雄的期望次數(shù)為n/(n-k),現(xiàn)在有k+1個(gè)英雄了剿骨，按上面的方法繼續(xù)，綜上總的期望是n/n+n/(n-1)+n/(n-2)+...+n/1
現(xiàn)在考慮第二個(gè)問(wèn)題
- 首先m肯定是>=n的
- 如果m>n肯定是存在抽重的情況埠褪，我們把每個(gè)英雄最先出現(xiàn)的位置確定出來(lái)浓利，這些位置之間的區(qū)間的元素就是抽重的,我們不關(guān)心抽重的是那張卡挤庇，也不關(guān)心抽出的新卡是那張卡，而是當(dāng)前區(qū)間究竟是抽重還是抽新贷掖。
設(shè)這種長(zhǎng)度為m的二元序列是最基本的情況單元 - 最后一個(gè)抽中的英雄不可能抽重嫡秕，只有一個(gè)，還有第一次抽到的一定是新英雄苹威，所以有n-1個(gè)抽重區(qū)間(可以為空)昆咽，且區(qū)間之和為m-n，所以可以把情況單元簡(jiǎn)化成n-1的自然數(shù)序列牙甫，和為m-n.
- 考慮一個(gè)基本情況掷酗，設(shè)為{e1,e2,e3,...,en-1} 如果已抽i個(gè)不同英雄，抽重ei個(gè):概率為(k/n)ei, 抽張新卡概率為(n-i)/n,乘起來(lái)就是當(dāng)前情況的概率
- 把所有的情況找到腹暖，把每個(gè)情況的概率加起來(lái)就是總的概率
