SP4672 FUNPROB – Yanu in Movie theatre 题解

发布于 2020-08-18  575 次阅读


题意

一个长度为 $N+M$ 的 $01$ 串,包含 $N$ 个 $0$ 和 $M$ 个 $1$。

现在随机生成这个 $01$ 串,要求在它的每个前缀中,$0$ 的个数都要不多于 $1$ 的个数。

求生成合法串的概率。

解析

首先我们知道,若 $M<N$ ,答案显然为 $0$。

然后我们发现,在 $M \ge N$时,这个题面是非常难求的,我们考虑对题目进行一些转化。

我们作出这样一张图,点 $A(0,0)$ 为我们的出发点,点 $B(M+N,M-N)$ 为终点,我们从 $A$ 点出发走 $M+N$ 步,其中有 $M$ 步为向右移动一格,再向上移动一格,另有 $N$ 步为向右移动一格,再向下移动一格。

由于我们不论怎么走都能到达 $B$ 点,因此显然总方案数为 $C_{M+N}^{N}$。

而想要求有多少种方案合法,我们考虑求有多少种方案非法。

显然,在任何时刻,若$0$ 的个数都要多于 $1$ 的个数,转化到此图中,即为到达 $y=-1$ 这条直线,该方案就是非法的。所以非法的方案数就转化为了到达终点的总方案数中,会经过 $y=-1$ 这条直线的方案数。

我们接着看这张图。

如果我们找到了一种方案,使得路径会经过 $y=-1$ ,那么我们可以将其到达 $y=-1$ 之前的路径以 $y=-1$ 做对称,于是我们惊奇的发现,我们所要求的非法方案数就是从 $E$ 点出发,到达 $B$ 的方案数。

我们设有 $x$ 步会向右上移动, $y$ 步会向右下移动,则由图显然有:

$\begin{cases}x+y=M+N\x-y=M-N+2\end{cases}$

两式相减可得 $y=N-1$,于是不合法的方案数就为$C_{M+N}^{N-1}$。

显然,合法的概率为 $1$ 减去不合法的概率。所以答案为:

$1-\dfrac{C_{M+N}^{N-1}}{C_{M+N}^{N}}$

即:

$\dfrac{m-n+1}{m+1}$

别忘了考虑 $M<N$ 时答案为 $0$ 哦!!!

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int m,n;
int main(){
    while(scanf("%d%d",&n,&m)==2&&(n||m)){
        printf("%.6lf\n",max(0.0,1.0*(m-n+1)/(m+1)));
    }
    return 0;
} 

月流华 岁遗沙 万古吴钩出玉匣