本文主要是介绍csu 1950: 谈笑风生 卡特兰数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接点这里
基佬出的毒瘤题啊。。。
看完题目我们很容易把第x个左括号和其右括号内的看成独立一部分设为Q,枚举这个里面的括号数。这里很简单,,
然后那?,,然后还剩下Q左右的2部分。。接下来该怎么考虑?。。一开始我是把2部分放在一起考虑的,结果非常复杂,考虑的东西非常多
其实那,我们只需要单独考虑2部份就可以了。
我们需要知道一个公式:Cm(i,j)=C(i+j,j)−C(i+j,j−m),其中Cm(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("input.txt","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;
}
这篇关于csu 1950: 谈笑风生 卡特兰数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!