卡特兰数：
一个2*n的序列，其中每一个元素为+1或-1，
- 任意一点左边元素累加和必须>=0.
- 最后所有元素加和必须是0
很容易想到用动态规划来求卡特兰数，优点是方便调试，而且可以定制其中一些参数。
- 方法一：递推状态和方程:
a[i][j]为状态，i为当前的串长度。j为当前的累加和(从element[0]加到element[i-1]），显然根据条件1，有j>=0.
另外有i+j<=len.原因是根据条件2，如果后面的len-i个元素都是-1，则要保证j+(len-i)<=0。否则，显然最后的累加和肯定会>0.
a[i][j]= a[i-1][j-1] (当前元素取+1。注意要保证j>0，否则j-1<0越界且不合法) + a[i-1][j+1]（当前元素取-1。）
下面实现了采用dp解出 卡特兰剩余序列的种类数。注意delta是什么意思呢，就是起始累加和 j0 的意思。
- 方法二：组合公式：
也能够想到用公式，对一个长度为2*n的卡特兰序列，其计数为C（2*n,n)-C(2*n,n+1). 下面也实现了公式法。
- 实现：
下面ca（n,k）实现了组合计数，但没有考虑取模的情况。如果考虑，需要用费马定理。caCatelan（n) 获取长度2*n的卡特兰序列的计数。
然后dpCatelan用动态规划，计算起始累加和为delta，剩余长度为len的卡特兰剩余序列的计数。优点是取模更方便了。
#include <iostream>
#include <vector>
using namespace std;
typedef long long int ll;
// dp to get catelan number
ll dpCatelan(int len,int delta){
if(delta>len) return 0;//@error: should judge this to prevent over-flow of a[][]
//@error: specially, when delta==len,the following will all be ')', return 1
vector<vector<ll> > a(len+1,vector<ll>(len+1,0));
a[0][delta]=1;//here is very important for katelan number. Delta is the initial sum of catelan remaining series.
// j=lc-rc+delta>=0 , it is the basic feature of katalan series
for(int i=1;i<=len;i++){
for(int j=0;i+j<=len;j++){
//j=lc-rc+delta>=0,
a[i][j]=a[i-1][j+1];
if(j>0) a[i][j]+=a[i-1][j-1];
}
}
return a[len][0];
}
// another way to cal catelan number
ll ca(int n,int k){
ll res=1;
k=k>n-k?n-k:k;
for(int i=0;i<k;i++){
//res*=(n-i)/(i+1);//@error: here n-i/i+1 may be 0
res=res*(n-i)/(i+1);
}
return res;
}
ll caCatelan(int n){//@error: this n is the number of pairs, not the same with get(len,delta)'s len
return ca(2*n,n)-ca(2*n,n+1);
}
int main(){
for(int n=1;n<30;n++)
cout<<dpCatelan(2*n,0)<<":"<<caCatelan(n)<<endl;
return 0;
}
回到本题，长度为2*n的卡特兰括号序列，求第k个。
Problem D. Parentheses Order
An n parentheses sequence consists of n "("s
and n ")"s.
A valid parentheses sequence is defined as the following:
You can find a way to repeat erasing adjacent pair of parentheses "()" until it becomes empty.
For example, "(())" is a valid parentheses, you can erase the pair on the 2nd and 3rd position and it becomes "()", then you can make it empty.
")()(" is not a valid parentheses, after you erase the pair on the 2nd and 3rd position, it becomes ")(" and you cannot erase any more.
Now, we have all valid n parentheses sequences. Find the k-th
smallest sequence in lexicographical order.
For example, here are all valid 3 parentheses sequences in lexicographical order:
and n ")"s.
A valid parentheses sequence is defined as the following:
You can find a way to repeat erasing adjacent pair of parentheses "()" until it becomes empty.
For example, "(())" is a valid parentheses, you can erase the pair on the 2nd and 3rd position and it becomes "()", then you can make it empty.
")()(" is not a valid parentheses, after you erase the pair on the 2nd and 3rd position, it becomes ")(" and you cannot erase any more.
Now, we have all valid n parentheses sequences. Find the k-th
smallest sequence in lexicographical order.
For example, here are all valid 3 parentheses sequences in lexicographical order:
3 2 2 3 4 3 6
Case #1: ()() Case #2: ()(()) Case #3: Doesn't Exist!
注意本题大数据很坑爹！ 不管采用方法一、二，求卡特兰剩余序列的计数tmp都有可能把long long int爆掉!!!!
幸好md k没有超过long long int,考虑本题的逻辑，当遇到tmp爆掉long long int的时候，只需要返回tmp=-1,然后检查tmp就知道了！
另外，遇到的问题是判断语句中，ll a,b. if(a+b<k), 这个加号+也是分分钟爆掉ll的节奏啊！！果断用减号代替！ if(k-a<b)，这样就不会ll溢出了！
#include <iostream>
#include <vector>
using namespace std;
typedef long long int ll;
// get the possible catelan series' count
// in condition when remains len while the sum is currently delta
ll get(int len,int delta){
if(delta>len) return 0;//@error: should judge this to prevent array-over-index of a[][]
//@error: specially when delta==len,the following will all be ')', return 1
vector<vector<ll> > a(len+1,vector<ll>(len+1,0));
a[0][delta]=1;
// j=lc-rc+delta>=0
for(int i=1;i<=len;i++){
for(int j=0;i+j<=len;j++){
//j=lc-rc+delta>=0,
a[i][j]=a[i-1][j+1];
if(a[i][j]<0){ a[i][j]=-1;continue;}// @error: the result can be overflow! since catelan[100] is really big! so use -1 as overflow flag here!
if(j>0) {
a[i][j]+=a[i-1][j-1];
if(a[i][j]<0){ a[i][j]=-1;continue;}//overflow flag as above
}
}
}
//if(a[len][0]<0) cout<<"overflow in catelan[len,delta]!!!"<<endl;
return a[len][0];
}
bool loop(int n,ll k,char *buf){
if(n==0||n%2) return false;
int lc=0,rc=0;//
ll cnt=0;
for(int i=0;i<n;i++){
buf[i]='(';
lc++;
ll tmp=get(n-1-i,lc-rc);
//cout<<n-1-i<<":"<<lc-rc<<":"<<cnt<<":"<<tmp<<endl;
//if(cnt+tmp<k) {//@error: be careful for every operator, especially when using long long type
// here tmp can be very large! so big data should always care for int-or-ll-overflow
if(tmp>=0&&tmp<k-cnt){//@error: as solution, avoid using +, instead using - in case of overflow ! and tmp >=0 means no overflow in tmp!
buf[i]=')';
lc-=1,rc+=1;
if(lc<rc) return false;
cnt+=tmp;
}
}
buf[n]=0;
return true;
}
int main(){
int n;cin>>n;char buf[1000];
for(int i=0;i<n;i++){
int N; ll K;cin>>N>>K; //@error: k should be long long int
cout<<"Case #"<<i+1<<": ";
if(loop(2*N,K,buf)){
cout<<buf<<endl;
}
else cout<<"Doesn't Exist!"<<endl;
}
return 0;
}