题解：SP9507 MARIO2 - Mario and Mushrooms

Cake_W · 2025-07-11 23:42:06 · 题解

题目传送门

分析

如有错误，还请各位大佬指正！

虽然这道题可以使用动态规划来完成，但是因为这道题目中空间限制比较特殊，使用动态规划的话并不现实，所以不考虑。在这道题目中，正解是 Raney 引理。

Raney 引理：如果有一个整数序列的所有数字之和为一，则在这个序列中有且仅有一种循环移位满足所有前缀和非负。而这道题目中，如果马里奥最终剩下了一点生命值，则马里奥可以存活，反之则不能。刚好满足了 Raney 引理的构成条件。所以这道题目使用 Raney 引理。

思路

因为序列长度就等于好蘑菇的个数加上坏蘑菇的个数，所以整个序列的长度就等于 {k\times m + 1 + k}。因为 Raney 引理中有一句很重要的话：在这个序列中有且仅有一种循环移位满足所有前缀和非负。所以在这道题目中，合法序列对应着 {k\times m + 1 + k} 个循环移位，所以序列合法的概率（也就是马里奥生还的概率）是 \frac{1}{k\times m + 1 + k}。

代码

#include<bits/stdc++.h>  
using namespace std;
int main()  
{  
    int m,k,t;  
    double f;
    cin>>t;  
    for(int i=1;i<=t;i++) 
    {  
        cin>>m>>k;
        f=1.0/(k*m+k+1);
        printf("Case #%d: %.8lf\n",i,f);
    }  
    return 0;  
}