BZOJ 3907: 网格 [Catalan数 高精度]

时间：2021-01-06 14:37:36

3907: 网格

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 402  Solved: 180
[Submit][Status][Discuss]

Description

某城市的街道呈网格状，左下角坐标为A(0, 0)，右上角坐标为B(n, m)，其中n >= m。现在从A(0, 0)点出发，只能沿着街道向正右方或者正上方行走，且不能经过图示中直线左上方的点，即任何途径的点(x, y)都要满足x >= y，请问在这些前提下，到达B(n, m)有多少种走法。
BZOJ 3907: 网格 [Catalan数 高精度]

Input

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

Output

输出文件中仅有一个整数和一个换行/回车符，表示不同的方案总数。

100%的数据中，1 <= m <= n <= 5 000
你们出题人有意思吗，变式套上高精度又一道题.....
问题在于我这个傻叉横纵坐标竟然搞混了
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=1e4+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m;

bool notp[N];

int p[N],lp[N];

void sieve(int n){

    for(int i=;i<=n;i++){

        if(!notp[i]) p[++p[]]=i,lp[i]=p[];

        for(int j=;j<=p[]&&i*p[j]<=n;j++){

            notp[i*p[j]]=;

            lp[i*p[j]]=j;

            if(i%p[j]==) break;

        }

    }

}

struct Big{

    int d[N],l;

    Big():l(){memset(d,,sizeof(d));d[]=;}

    int& operator[](int x){return d[x];}

}a,b;

void Mul(Big &a,int b){

    int g=;

    for(int i=;i<=a.l;i++){

        g+=a[i]*b;

        a[i]=g%;

        g/=;

    }

    for(;g;g/=) a[++a.l]=g%;

}

void Minus(Big &a,Big &b){

    for(int i=;i<=b.l;i++){

        if(a[i]<b[i]) a[i]+=,a[i+]--;

        a[i]-=b[i];

    }

    int p=b.l+;

    while(a[p]<) a[p]+=,a[p+]--;

    while(a[a.l]==) a.l--;

}

void Print(Big &a){

    for(int i=a.l;i>=;i--) printf("%d",a[i]);

}

int e[N];

inline void add(int x,int d){

    while(x!=){

        e[lp[x]]+=d;

        x/=p[lp[x]];

    }

}

void C(int n,int m,Big &ans){

    memset(e,,sizeof(e));

    for(int i=n;i>=n-m+;i--) add(i,);

    for(int i=;i<=m;i++) add(i,-);

    for(int j=;j<=p[];j++) for(;e[j];e[j]--) Mul(ans,p[j]);

}

int main(){

    freopen("in","r",stdin);

    n=read();m=read();

    sieve(n+m);

    C(n+m,n,a);

    C(n+m,n+,b);

    Minus(a,b);

    Print(a);

}
 

相关文章