思路
我们发现直接求不好求,把问题转化为走格子,0表示向右走一格,1表示向上走一个,问题就转化为了走到n点的路径
所有前缀中0的个数大于1的个数都在红线以下,我们发现,把经过红线的路径进行对称,那么他们的终点都会被映射到$(n - 1,n + 1)$,所以我们只要计算终点是$(n - 1,n + 1)$的路径有多少个,再用总数减去就是我们想要的答案
代码的话,直接套用公式就可以了
$$C^n_{2n} = C^n_{2n} - C^{n-1}_{2n}= \dfrac{C^n _2n}{n+1}= [(2n \sim n)!*n!^{-1}] * (n+1)^{-1}$$
快速幂求逆元可行性证明
如果一个模数为质数,另一个数不是它的倍数,我们就可以用快速幂求逆元
本题中$mod = 1e9 + 7$,mod是一个质数,而n的范围是$1≤n≤105$,n不可能为mod的倍数,所以是可以用快速幂求逆元的
java代码
import java.util.Scanner;
public class Main{ //0的个数大于1的个数
static int mod = 1000000007;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
long res = 1;
for(int i = 1,j = 2 * n; i <= n;i ++,j--) //i循环1 ~ n,j循环2n ~ n分子
{
res = res * j % mod; //2n ~ n的阶乘
res = res * qmi(i,mod - 2,mod) % mod; //n阶乘的逆元
}
res = res * qmi(n + 1, mod - 2, mod) % mod;
System.out.println(res);
}
private static long qmi(long a, int b, int mod) //快速幂模板
{
long res = 1;
while(b != 0)
{
if((b & 1) != 0) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
}
这个[(2n−n)!公式推错了吧,不应该是2n(2n-1)(2n-2).....*(2n-n+1)
已修正,感谢指出!!