wannafly 挑战赛9 D 造一造 （卡特兰数）

链接：https://www.nowcoder.com/acm/contest/71/D

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

WYF正试图用一个栈来构造一棵树，现在他已经构造了n个元素作为树的节点，只要将这n个元素依次入栈出栈就可以形成一棵树了。当然，这个问题与树并没有关系，所以它叫做WYF的栈。每次你可以入栈一个新元素或者当栈非空时出栈一个元素，n个元素必须依次入栈，而WYF希望其中第m个元素入栈之后，栈中恰好有k个元素，现在他想知道一共有多少种入栈出栈顺序满足这个条件。

输入描述:

第一行一个正整数T，表示数据组数。(1<=T<=10000)对于每组数据包含一行三个正整数n,m,k。

输出描述:

对于每组数据输出一个正整数表示答案。 由于答案可能过大，所以只需要输出对109+7取模后的答案 

–>

输入例子:
2333332
输出例子:
12

–>

示例1

输入

2333332

输出

12

示例2

输入

510321022107510621076

输出

6864

11934

2200

3780

924

示例3

输入

2

5 4 4

5 2 1

输出

5

14

备注:

1<=n,m,k<=1e9

////////////////////////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////////////////////////////////////

很难受，结束完才ac

放一下自己看的卡特兰数的讲解 http://blog.csdn.net/qq_26525215/article/details/51453493 （侵删）
#include

#define mst(a,b) memset((a),(b), sizeof a)

#define lowbit(a) ((a)&(-a))

#define IOS ios::sync_with_stdio(0);cin.tie(0);

using namespace std;

typedef long long ll;

const int mod=1e9+;

const int maxn=2e6+;

ll jie[maxn],inv[maxn];

ll qpow(ll a,ll b){

ll ret=;

while(b){

if(b&)ret=ret*a%mod;

b>>=;

a=a*a%mod;

}

return ret;

}

void init(){

jie[]=inv[]=;

for(int i=;i

jie[i]=jie[i-]*i%mod;

inv[i]=qpow(jie[i],mod-);

}

}

ll C(int a,int b){

return jie[a]*inv[b]%mod*inv[a-b]%mod;

}

ll get(int a,int b){

return (C(a+b,b)-C(a+b,b-)+mod)%mod;

}

int main(){

#ifdef local

freopen(“in.txt”,”r”,stdin);

//freopen(“out.txt”,”w”,stdout);

#endif

init();

int t;scanf(“%d”,&t);

while(t–){

int n,m,k;scanf(“%d%d%d”,&n,&m,&k);

if(m

printf(“%d\n”,);continue;

}

ll ans=get(m-,m-k)*get(k+n-m,n-m)%mod;

printf(“%lld\n”,ans);

}

return ;

}