组合数学——网格

网格

某城市的街道呈网格状，左下角坐标为 A(0,0)，右上角坐标为 B(n,m)，其中 n≥m。

现在从 A(0,0) 点出发，只能沿着街道向正右方或者正上方行走，且不能经过图示中直线左上方的点，即任何途径的点 (x,y) 都要满足 x≤y，请问在这些前提下，到达 B(n,m) 有多少种走法。

输入格式
仅有一行，包含两个整数 n 和 m，表示城市街区的规模。

输出格式
输出一个整数，表示不同的方案总数。

数据范围
1≤m≤n≤5000
输入样例：
6 6
输出样例：
132

题解：

这道题显然是关于卡特兰数的题。我们走到(n,m)这个点的方案数是$C_{m+n}^m$Cm+nm​
对于任意一种走出边界的终点都相当于(n,m)点关于直线y=x+1对称。那么我们就可以先把坐标系向下移动一格，然后现在就是关于y=x对称了。这样我们最后再向上提一格，最后我们不合法的终点就是(m-1,n+1)方案数也就是$C_{m+n}^{n+1}$Cm+nn+1​
然后这道题需要用高精度。

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int prime[N],cnt,n,m;
bool st[N];
struct HP{
    int w[3005], len;
    HP operator - (const HP &b) const {
        HP c; c.len = 0;
        memset(c.w, 0, sizeof c.w);
        for (int i = 1, t = 0; i <= len; i++) {
            t = w[i] - b.w[i] - t;
            c.w[++c.len] = (t + 10) % 10;
            t = (t < 0) ? 1 : 0;
        }
        while (!c.w[c.len] && c.len > 1) c.len--;
        return c;
    }
    HP operator * (const int &b) const {
        HP c; c.len = 0;
        memset(c.w, 0, sizeof c.w);
        for (int i = 1, t = 0; i <= len || t; i++) {
            t += w[i] * b;
            c.w[++c.len] = t % 10;
            t /= 10;
        }
        return c;
    }
};
void init()
{
    for(int i=2;i<N;i++){
        if(!st[i]) prime[cnt++]=i;
        for(int j=0;prime[j]*i<N;j++){
            st[prime[j]*i]=1;
            if(i%prime[j]==0) break;
        }
    }
}
int get(int n,int p)
{
    int s=0;
    while(n) s+=n/p,n/=p;
    return s;
}
HP C(int a,int b){
    HP res; res.len=1;
    memset(res.w,0,sizeof res.w);
    res.w[1]=1;
    for(int i=0;i<cnt&&prime[i]<=a;i++){
        int k=get(a,prime[i])-get(b,prime[i])-get(a-b,prime[i]);
        while(k--) res=res*prime[i];
    }
    return res;
}
void print(HP res)
{
    for(int i=res.len;i;i--) printf("%d",res.w[i]);
    cout<<endl;
}
int main()
{
    init();
    scanf("%d%d",&n,&m);
    print(C(m+n,m)-C(m+n,n+1));
}