满足条件的01序列 Java
卡特兰数 = C2n n - C2n n-1 = C2n n / n + 1
用扩展欧求逆元
import java.io.*;
import java.util.*;
public class Main{
static int n,p = 1000000007,x,y;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args)throws IOException{
n = Integer.parseInt(br.readLine());
int a = 2 * n;int b= n;
long res = 1;
for(int i = a; i > a - b;i--){
res = res * i % p;
}
for(int i = 2; i<= b;i ++){
exgcd(i,p);
res = (res * x % p + p) % p;
}
exgcd(n+1,p);
res = (res * x % p + p ) % p;
pw.println(res);
pw.flush();br.close();pw.close();
}
static int exgcd(int a,int b){
if(b == 0){
x = 1;y = 0;
return a;
}
int d = exgcd(b , a % b);
int temp = x;
x = y;
y = temp - a / b * y;
return d;
}
}
用快速幂求逆元
import java.io.*;
import java.util.*;
public class Main{
static int n,p = 1000000007;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args)throws IOException{
n = Integer.parseInt(br.readLine());
long res =1;
for(int i = 1,j = 2 * n;i <= n;i++ ,j--){
res = res * j % p;
res = res * qmi(i,p-2,p) % p;
}
res = res * qmi(n + 1,p-2,p) % p ;
pw.println(res);
pw.flush();br.close();pw.close();
}
//快速幂求逆元
/*
用快速幂有两个条件
①模数是一个质数
②被模数不是模数的倍数
*/
static long qmi(long a,long b,long p){
long res =1;
while(b > 0){
if((b & 1) == 1) res = res * a % p;
b >>= 1;
a = a * a % p;
}
return res;
}
}
测试结果
扩展欧几里得是第一个,目前来看是快了一倍,但是快速幂写的快一点,各有长短吧