gmoj 7009. 2021.03.13【2021省赛模拟】抽卡（card） 题解

题解"/>

gmoj 7009. 2021.03.13【2021省赛模拟】抽卡（card） 题解

题目

题解

考场上的思路（未实现）

考场上的思路是设 f i f_{i} fi​ 表示集齐 i i i 个角色后，要再收集一个角色的期望次数。

然后再设 g i g_i gi​ 表示连续 i i i 次抽五星角色的期望抽卡次数。

那么就有
g i + 1 = ∑ j = 1 m − 1 ( 1 − p ) j − 1 p ( g i + j ) + ( 1 − p ) m − 1 ( g i + m ) = [ ( 1 − p ) m − 1 + ∑ j = 1 m − 1 ( 1 − p ) j − 1 p ] g i + ( 1 − p ) m − 1 m + ∑ j = 1 m − 1 ( 1 − p ) j − 1 p ⋅ j f i = ∑ j = 1 + ∞ ( i n ) j − 1 n − i n ⋅ g j = n − i n ∑ j = 1 + ∞ ( i n ) j − 1 g j \begin{aligned} g_{i+1}&=\sum_{j=1}^{m-1} (1-p)^{j-1}p(g_i +j)+(1-p)^{m-1}(g_i +m)\\ &=\left[(1-p)^{m-1} +\sum_{j=1}^{m-1} (1-p)^{j-1}p \right]g_i + (1-p)^{m-1}m + \sum_{j=1}^{m-1} (1-p)^{j-1} p\cdot j \\ f_i &=\sum_{j=1}^{+\infty} \left(\frac{i}{n} \right)^{j-1}\frac{n-i}{n}\cdot g_j\\ &= \frac{n-i}{n} \sum_{j=1}^{+\infty}\left(\frac{i}{n} \right)^{j-1} g_j \end{aligned} gi+1​fi​​=j=1∑m−1​(1−p)j−1p(gi​+j)+(1−p)m−1(gi​+m)=[(1−p)m−1+j=1∑m−1​(1−p)j−1p]gi​+(1−p)m−1m+j=1∑m−1​(1−p)j−1p⋅j=j=1∑+∞​(ni​)j−1nn−i​⋅gj​=nn−i​j=1∑+∞​(ni​)j−1gj​​
但是那个 ∑ j = 1 + ∞ ( i n ) j − 1