AcWing 889. 满足条件的01序列（卡特兰数）

题目连接

https://www.acwing.com/problem/content/891/

思路

因为有n个1和n个0，那么最后一定能走到点(n,n)，我们正面去想不太好想，所以我们可以看看中间出现1的数量比0多的情况，对于这个放法我们可以化成一个平面图，1表示向右走一步，0表示向上走一步，那么对于我们现在要求的反面就是要经过 y = x + 1 y=x+1 y=x+1这一条线的方案数，我们可以对这条线做(n,n)的一个对称图形也就是(n-1,n+1)，我们会发现这个一个位置的方案数为： C 2 n n − 1 C_{2n}^{n-1} C2nn−1​，对于走到(n,n)的所有方案数为: C 2 n n C_{2n}^{n} C2nn​,那么我们直接做一个差就好啦，化简后就是： C 2 n n n + 1 \frac{C_{2n}^{n}}{n+1} n+1C2nn​​这个数也被称为卡特兰数

代码

#include
using namespace std;
#define ll long long
#define mod 1000000007

ll ksm(ll a,ll b){
    ll res = 1;
    for(;b;b>>=1,a=a*a%mod) if(b & 1) res = res * a % mod;
    return res;
}

ll C(ll a,ll b){
    b = min(a-b,b);
    ll ansL = 1,ansR = 1;
    for(int i = 1;i