题解 SP9507【MARIO2 - Mario and Mushrooms】

whiteqwq · 2021-04-05 10:41:05 · 题解

题意

给定m,k，一共有k个坏蘑菇，每遇到一个坏蘑菇需要掉m滴血，一共有mk+1个好蘑菇，每遇到一个好蘑菇可以加1滴血。若坏蘑菇和好蘑菇的顺序随机生成，一开始的血量为0，若血量在中途变为负数就死亡，求生还概率。（1\leqslant m,k\leqslant 1000）

分析

Raney引理的板子，其实就是P6672 [清华集训2016] 你的生命已如风中残烛的弱化板。

Raney引理：一个和为1的整数序列，有且仅有一种循环移位满足所有前缀和非负。

证明：设这一个序列a长度为n，构造一个函数f(x)=f(x-1)+a_{(x-1\bmod n)+1}，那么很容易可以知道可以用两条斜率为\frac{1}{k}的直线夹住函数，感性理解发现函数上每n个连续位置有且仅有一个地方与直线相交

我们发现序列长度为km+k+1，那么一个合法的序列一共对应km+k+1个循环移位，那么序列合法的几率就是\frac{1}{km+k+1}

代码

#include<stdio.h>
int T,n,m,cs;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        printf("Case #%d: %.8lf\n",++cs,1.0/(m*(n+1)+1));
    }
    return 0;
}