题意：度度熊最近很喜欢玩游戏。这一天他在纸上画了一个2行N列的长方形格子。他想把1到2N这些数依次放进去，但是为了使格子看起来优美，他想找到使每行每列都递增的方案。不过画了很久，他发现方案数实在是太多了。度度熊想知道，有多少种放数字的方法能满足上面的条件？
思路：
思路基本没有，看的其他人的题解才知道是应用卡特兰数的题
我们假设0代表这个数放在第一排，1代表这个数放在第二排，如果序列00001111
就是 1 2 3 4
5 6 7 8
序列01010101 就是 1 3 5 7
2 4 6 8
这个问题就转化成有几种满足题目条件的01序列，通过观察发现每个位置之前0的个数大于等于1的个数
如果把0看成入栈，1看成出栈,
这个问题变转化成n个数的入栈的出栈次序的种类数，也就是卡特兰数
代码：
#include <iostream> #include <cstdio> #define ll long long #define mod 1000000007 using namespace std; const int maxn=2000000; ll fact[maxn+5]; ll inv[maxn+5]; ll qmod(ll a,ll b) { ll ans=1; a=a%mod; while(b) { if(b&1) { ans=(ans*a)%mod; } b=b/2; a=(a*a)%mod; } return ans; } ll init() { fact[0]=1;inv[0]=1; for(ll i=1;i<=maxn;i++) { fact[i]=(fact[i-1]*i)%mod; inv[i]=qmod(fact[i],mod-2); } } ll catalan(ll n) { return (((((fact[2*n]*inv[n])%mod)*inv[n])%mod)*qmod(n+1,mod-2))%mod; } int main() { int t,cas=1; init(); cin>>t; while(t--) { ll n; scanf("%lld",&n); printf("Case #%d: %lld ",cas++,catalan(n)); } return 0; }