2019牛客暑期多校训练营（第一场）E-ABBA（卡特兰数）
题目大意
一段长度为2(n+m)的字符串其中只有A和B，其中有(n+m)个A，（n+m）个B，可以将其拆成n个‘AB’，m个’BA’问有多少种满足这个条件的字符串。
解题思路
假设一段字符串的前缀中a为A的数量b为B的数量，a-b就是匹配了的之后剩余的待匹配的a或者b的数量，如果剩余a则后面的会匹配为ab如果剩余b则剩下的会匹配为ba因为要保证只有n个ab所以只要保证对于所有的前缀都有待匹配的a的数量小于等于n，ba同理。故满足所有前缀中a的数量减去b的数量≥-m，≤n就是答案。而这点应用卡特兰数求解即可
AC代码
#include<bits/stdc++.h>
using namespace std
;
typedef long long LL
;
const int mod
=1e9+7;
const int size
=4e3+5;
int fac
[size
],invfac
[size
];
int quick_pow(int a
,int b
)
{
int ans
=1;
while(b
)
{
if(b
&1) ans
=1LL*ans
*a
%mod
;
a
=1LL*a
*a
%mod
;
b
>>=1;
}
return ans
%mod
;
}
void init()
{
fac
[0]=1;
for(int i
=1;i
<size
;i
++) fac
[i
]=1LL*fac
[i
-1]*i
%mod
;
invfac
[size
-1]=quick_pow(fac
[size
-1],mod
-2);
for(int i
=size
-2;i
>=0;i
--) invfac
[i
]=1LL*invfac
[i
+1]*(i
+1)%mod
;
}
int combi(int a
,int b
)
{
if(a
<0) return 0;
if(a
==0) return 1;
return 1LL*fac
[b
]*invfac
[a
]%mod
*invfac
[b
-a
]%mod
;
}
int main()
{
int n
,m
;
init();
while(~scanf("%d%d",&n
,&m
))
{
printf("%d\n",(1LL*fac
[2*(n
+m
)]*invfac
[n
+m
]%mod
*invfac
[n
+m
]%mod
-combi(n
-1,2*(n
+m
))+mod
-combi(m
-1,2*(n
+m
))+mod
)%mod
);
}
}
