卡特兰数中南大学OJ1320

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 void gcd(int a,int b,int &d,int &x,int &y)
 8 {
 9     if(!b)
10     {
11         d=a;
12         x=1;
13         y=0;
14     }
15     else
16     {
17         gcd(b,a%b,d,y,x);
18         y-=x*(a/b);
19     }
20 }
21 
22 //计算模n下a的逆元，如果不存在逆元，返回-1
23 int inv(int a,int n)
24 {
25     int d,x,y;
26     gcd(a,n,d,x,y);
27     return d==1? (x+n)%n: -1;
28 }
29 
30 long long arr[10010];
31 long long mod=1000000007;
32 
33 int main()
34 {
35     int n;
36     memset(arr,0,sizeof(arr));
37     arr[0]=1;
38     for(int i=1;i<=10000;i++)
39     {
40         arr[i]=((arr[i-1]*2*(2*i+1)%mod)*inv(i+2,mod))%mod;
41     }
42     while(scanf("%d",&n)!=EOF)
43     {
44         printf("%lld
",arr[n-1]);
45     }
46     return 0;
47 }

View Code

卡特兰数 中南大学OJ1320

卡特兰数中南大学OJ1320