题解均表示这种做法会出现冲突。我尝试了,也发现输出始终对不上。
设 E(k) 表示第 k 轮的伤害期望,那么有:
ans=∑k=1rE(k)
其中,也有:
E(k)=∑x=1n(qk(x)×px×dx)
qk(x) 表示考虑到第 k 轮,卡牌 x 被遍历到的概率。即它没有因为自己之前发动过技能或是本轮前面的卡牌发动技能而被跳过。在此基础上乘 px,即为它在第 k 轮被发动的概率。
为了求 qk(x),我们需要 Pk(x),它的定义为在第 k 轮时,第 x 张卡牌仍未发动过技能的概率。
于是设初值
P1(∗)=1
表示在第 1 轮时,所有卡牌一定均未发动。
可得转移:
{qk(x)=Pk(x)×∏i=1x−1(Pk(i)×(1−pi)+1×(1−Pk(i)))Pk+1(x)=Pk(x)×(1−qk(x)×px)
对于第一个公式的解释:此处计算被遍历到的概率。
- 首先它自己之前不能被发动过,使用 Pk(x)。
- 其次本轮它之前的卡牌不能被发动。
对于卡牌 i,它没有被发动,共有两种可能:
- 它之前没被发动,但是本轮发动失败。概率为 Pk(i)×(1−pi)。
- 它之前已经被发动,概率为 1−Pk(i)。
由于互斥,两者相加即为总概率。
连乘所有的 i,就是之前的卡牌一个也没发动的概率。
对于第二个公式的解释:此处计算下一轮该卡牌仍未发动技能的概率。
根据容斥原理,如果它发动技能的概率为 qk(x)×px,那么这一轮没有发动的概率就是 1−pk(x)×px。直接乘进上一轮没有被发动的概率里即可。
就是这样计算,但是对于样例 1,程序输出偏小(3.1832193750)。经过手算,得到的也是这个值。所以究竟是哪里漏/重了情况呢?