分析：打表以后就能发现时卡特兰数， 但是有除法取余。
f[i] = f[i-1]*(4*i - 2)/(i+1);
看了一下网上的题解，照着题解写了下面的代码，不过还是不明白，为什么用扩展gcd, 不是用逆元吗。。
网上还有别人的解释，没看懂，贴一下：
(a / b) % m = ( a % (m*b)) / b
笔者注：鉴于ACM题目特别喜欢M=1000000007,为质数：
当gcd(b,m) = 1, 有性质: (a/b)%m = (a*b^-1)%m, 其中b^-1是b模m的逆元.
求出b相对于m的逆元b^(-1)，即b*(b^(-1)) = 1 (mod m)。有b*b^(-1) - km = 1，其中k是一整数. 用Extended Euclid算法可以求出`b^(-1)。然后计算a*b^(-1) mod m = ( (a%m) * (b^(-1)%m ) % m; 其值与(a/b) mod m相同
推导：a/b = x (mod m) --两边同乘一个数--> a = bx (mod m) ---x=b^-1a-> a = (b^-1) ba (mod m)
再利用b^-1*b = 1(mod m) . 所以可以得出 x = b^-1*a是成立的。
所以 (a/b) mod m 的解与 (a*b^-1)%m的解是一样的。 而后着可以利用模对乘法的线性性
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL __int64
using namespace std;
const int mo = + ;
const int maxn = + ;
LL f[maxn]; LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(b==)
{
x=; y=; return a;
}
LL d = exgcd(b,a%b,x,y);
LL t=x;
x=y;
y=t-a/b*y;
return d;
}
void init()
{
int i;
LL x, y;
f[] = f[] = ;
for(i = ; i < maxn-; i++)
{
f[i] = f[i-]*(*i-)%mo;
exgcd(i+, mo, x, y);
f[i] = (f[i]*((x+mo)%mo))%mo;
}
}
int main()
{
int t, n, ca = ;
init();
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
printf("Case #%d:\n", ca++);
printf("%I64d\n", f[n]);
}
return ;
}
扩展gcd:
//扩展 GCD
//求x, y使得gcd(a, b) = a * x + b * y; int extgcd(int a, int b, int & x, int & y)
{
if (b == ) { x=; y=; return a; }
int d = extgcd(b, a % b, x, y);
int t = x; x = y; y = t - a / b * y;
return d;
}