卡特兰数的应用

依据卡塔兰数的推导，找出$(n,m)$关于$y=x+1$的对称点$(m-1,n+1)$，每一条非法路径都对应一条$(0,0)$到$(m-1,n+1)$的路径，因此合法路径=总路径数-非法路径，即$C_{n+m}^{n} - C_{n+m}^{m-1}$

#include <iostream>

using namespace std;

const int N = 10010;

int primes[N] , cnt;
bool st[N];
int a[N] , b[N];

void init(int n)
{
    for(int i = 2 ; i <= n ; i++)
    {
        if(!st[i]) primes[cnt++] = i;

        for(int j = 0 ; primes[j] <= n / i ; j++)
        {
            st[primes[j] * i] = true;

            if(i % primes[j] == 0) break;
        }
    }
}

int get(int n , int p)//n!中p的次数
{
    int res = 0;
    for(int i = n ; i ; i /= p) res += i / p;
    return res;
}

void mul(int a[] , int &len , int b)//a = a * b 高精度*低精度
{
    int t = 0;
    for(int i = 0  ; i < len ; i++)
    {
        t += a[i] * b;
        a[i] = t % 10;
        t /= 10;
    }

    while(t)
    {
        a[len++] = t % 10;
        t /= 10;
    }

}

int C(int a , int b , int c[])//把$C_{a}^{b}$存到c数组中
{
    int len = 1;
    c[0] = 1;

    for(int i = 0 ; i < cnt ; i++)
    {
        int p = primes[i];
        int s = get(a , p) - get(b , p) - get(a - b , p);
        while(s--) mul(c , len , p);
    }

    return len;
}

void sub(int a[] , int al , int b[] , int bl)
{
    for(int i = 0 , t = 0; i < al ; i++)
    {
        a[i] -= t + b[i];
        if(a[i] < 0) t = 1 , a[i] += 10;
        else t = 0;//t代表前一位是否要减一
    }
}

int main()
{
    init(N - 1);

    int n , m;
    cin >> n >> m;
    int al = C(n + m , m , a);
    int bl = C(n + m , m - 1 , b);

    sub(a , al , b , bl);

    int i = al - 1;
    while(!a[i] && i) i--;
    while(i >= 0) cout << a[i--];
    return 0;
}