csu 1950: 谈笑风生 卡特兰数

csu 1950: 谈笑风生 卡特兰数

题目链接点这里

基佬出的毒瘤题啊。。。

看完题目我们很容易把第x个左括号和其右括号内的看成独立一部分设为Q，枚举这个里面的括号数。这里很简单，，

然后那？，，然后还剩下Q左右的2部分。。接下来该怎么考虑？。。一开始我是把2部分放在一起考虑的，结果非常复杂，考虑的东西非常多

其实那，我们只需要单独考虑2部份就可以了。

我们需要知道一个公式：C​m​​(i,j)=C(i+j,j)−C(i+j,j−m),其中C_m(n,k)C​m​​(i,j)表示一个序列中有i个X和j个Y，满足对于这个序列的任何前缀,Y出现的次数-X的出现的次数< m的方案数。

我们可以看到当m等于1时就是合法括号序列前缀的方案数。

这个公式怎么来的那？

其实这个公式可以转化为：从（0,0）点走到（i,j）点（每一步只能往上和往右），路径不接触y=x+m这条直线的方案数。

这个方案数=全部的方案数（C（i+j,j））-不合法的方案数。

如何计算不合法路径有个ppt上讲的很清楚，，我盗个图。。

他是计算(1,0)到(n,n-1)的不接触y=x的路径数。

所以我们可以得到，不合法的方案数就是C(i+j,j-1)。

就是这个题的公式了。。

然后我们就枚举左部分有多少右括号（左括号固定为x-1个），

最后:

#include<iostream>
#include<cstdio>
#include<math.h>
#include<algorithm>
#include<map>
#include<set>
#include<bitset>
#include<unordered_map>
#include<stack>
#include<queue>
#include<string.h>
#include<cstring>
#include<vector>
#include<time.h>
#include<stdlib.h>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define FIN freopen(&#","r",stdin)
#define mem(x,y) memset(x,y,sizeof(x))
typedef unsigned long long ULL;
typedef long long LL;
#define fuck(x) cout<<"q"<<endl;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef pair<pair<int,int>,int> PIII;
typedef pair<int,int> PII;
const double eps=1e-8;
const int MX=1111;
const int P=1e9+7;
int n,x,y;
int Cat[MX],C[MX][MX];
int F[MX],invF[MX];
int inv[MX]= {0,1};
int quick_power(int a,int x)
{int ans=1;while(x){if(x&1)ans=(LL)a*ans%P;a=(LL)a*a%P;x>>=1;}return ans;
}
void init()
{for(int i=2; i<MX; ++i)inv[i]=(LL)inv[P%i]*(P-P/i)%P;Cat[1]=1;for(int i=2; i<MX; i++) Cat[i]=(LL)(4*i-2)*Cat[i-1]%P*inv[i+1]%P;F[0] = 1;for(int i = 1; i < MX; i++)  F[i] = ((LL)F[i - 1] * i) % P;invF[MX - 1] = quick_power(F[MX - 1],P - 2);for(int i = MX - 2; i >= 0; i--)  invF[i] = (LL)invF[i + 1] * (i + 1) % P;for(int i=0; i<505; i++)for(int j=0; j<505; j++)C[i][j]=((LL)F[i+j]*invF[j]%P*invF[i]%P-(LL)F[i+j]*invF[j-1]%P*invF[i+1]%P+P)%P;
}
int main()
{init();//cout<<C[1][1]<<" "<<C[2][1]<<" "<<C[3][1]<<endl;int T;cin>>T;while(T--){cin>>n>>x>>y;int ans=0;for(int i=y-x; i<=n-x; i++){int t=0;for(int j=0; j<=x-1; j++) t=(t+(LL)C[x-1][j]*C[n-j-i-1][n-x-i]%P)%P;//cout<<Cat[i]<<endl;t=(LL)t*Cat[i]%P;ans=(ans+t)%P;}cout<<ans<<endl;}return 0;
}