兔子前辈的套装收集——容斥算法的疑问

看看世界

地址1：《懒人蛋痛笨办法》中的附件
地址2：《懒人蛋痛笨办法》中的附件

主要是方法三——容斥算法中的递归推导过程看得不太明白：

已知条件：有一个套装由n件装备组成：A={a1,a2,...,an},击杀boss后每次只掉落一件（互斥），各个装备掉落概率P={p1,p2,...,pn}（不全相等）

推导过程：

1 设要求的次数期望为F(A)，根据第一次掉落的结果分为两种：
a 第一次收集到装备ai，剩余的装备A-{ai}需要的收集次数：pi*F(A-{ai})
这个pi*F(A-{ai})是怎么得来的？ai的概率*剩余装备收集次数期望=？
b 第一次没有收集到任何装备，那么之后还需进行的收集次数为：（1-∑Pk）*F(A)

2 根据数学期望的线性特性，可得F(A)=1 + ∑[pi*F(A-{ai})] + （1-∑Pk）*F(A), 化解得F(A)的求值表达式
这又是怎么得来的呢？

3 设置n=1,2,3...得到F(A)，然后归纳得到F(A)=.....

麻烦大家解答下，O(∩_∩)O谢谢

llzn2012

1 设要求的次数期望为F(A)，根据第一次掉落的结果分为两种：
a 如果第一次收集到装备ai，剩余的装备A-{ai}需要的收集次数：pi*F(A-{ai})
收集次数应该是：F(A-{ai})
b 如果第一次没有收集到任何装备，那么之后还需进行的收集次数为：（1-∑Pk）*F(A)
之后还需进行的收集次数应该是：F(A)
2 根据数学期望的线性特性，可得F(A)=1 + ∑[pi*F(A-{ai})] + （1-∑Pk）*F(A), 化解得F(A)的求值表达式
这是遍历这一次会出现的各种情况，情况出现的概率*情况出现后还需要多少次，再累加就是这一次后还需要次数的期望，再加1就是总共需要多少次的期望F(A)。

3 设置n=1,2,3...得到F(A)，然后归纳得到F(A)=.....