扩展的卡特兰数

用数形结合推一遍

这是一个普通的二维平面直角坐标系

我们让斜向上为奶牛，斜向下为公牛，就有：

因此可以推断出，如果碰到了 $y=-1$ 这条红线，奶牛就会moomoo叫

通过一些小学二年级的数学知识，我们可以得知：终点位于 $(m+n, n-m)$

因此，当 $n<m$ 时，直接输出 $0.000000$ 就好

从 $(0, 0)$ 走到 $(m+n, n-m)$ 的合法路径为 $总路径 - 不合法路径$ ，就考虑计算不合法路径

举一个例子：这是一个不合法情况：

我们考虑一下转化：将它第一次接触红线时的点的上半部分翻转到下面

就可以看做是一个普通的从 $(-2, 0)$ 走到 $(m+n, n-m)$ 的路径

易知，这两条路径是一一映射的关系，所以就有

现在开始用组合数学了！！

对于合法路径，相当于向上有 $n$ 步，向下有 $m$ 步，就有

对于不合法路径，因为你翻转了一下，所以向上有 $n+1$ 步，向下有 $m-1$ 步，所以：

因此有总合法路径数：

稍微同分花间一下，有:

因为求的是概率，就除掉那个 $C_{m+n}^{n}$ ，就有这个超级无敌螺旋上天看一眼就绷不住的超级短柿子：

但是我还是想给篇代码，来增加我的字数：

#include<iostream>
#include<cstdio>

using namespace std;

inline int read(){
	int x=0,f=1; char c=getchar();
	while (c<'0' || c>'9'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}

int T,n,m;

int main(){
	T=read();
	while (T--){
		n=read(); m=read();
		if (n<m) printf("0.000000\n");
		else{
			double a=n-m+1;
			double b=n+1;
			double ans=a/b;
			printf("%.6lf\n",ans);
		}
		
	}
	return 0;
}