1856: [Scoi2010]字符串(Catalan数)

1856: [Scoi2010]字符串

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 2117 Solved: 1211
[Submit][Status][Discuss]

Description

lxhgww最近接到了一个生成字符串的任务，任务需要他把n个1和m个0组成字符串，但是任务还要求在组成的字符串中，在任意的前k个字符中，1的个数不能少于0的个数。现在lxhgww想要知道满足要求的字符串共有多少个，聪明的程序员们，你们能帮助他吗？

Input

输入数据是一行，包括2个数字n和m

Output

输出数据是一行，包括1个数字，表示满足要求的字符串数目，这个数可能会很大，只需输出这个数除以20100403的余数

Sample Input

2 2

Sample Output

HINT

【数据范围】
对于30%的数据，保证1<=m<=n<=1000
对于100%的数据，保证1<=m<=n<=1000000

Source

Day2

/*

LuoguAC，bzoj总是CE我也很绝望啊

Catelan数。

等价于画一个坐标系从(0,0)到n-m且不越过y=-1(即1的个数>=0)这条线的方案数。

把y=n-m关于y=-1对称。则每一个不合法的解都对应一条从(0,0)到y=m-n-2的路径(画图可知)

答案就是总方案数减去不合法的路径条数。

考虑放x个1,则有 x-(n+m-x)=m-n-2 (到达y=m-n-2) 解得x=m-1。

不合法的路径条数就是C(m+n,m-1)

*/

#include<bits/stdc++.h>

#define N 2000002

#define M 20100403

#define ll long long

using namespace std;

ll n,m,ans;

ll inv[N]={,},fac[N]={,},f[N]={,};

int ll C(ll a,ll b)

{

    return ((fac[a]*inv[b])%M*inv[a-b]%M)%M;

}

inline void init()

{

    fac[]=;

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

    {

        fac[i]=(fac[i-]%M*i)%M;

        f[i]=((M-M/i)*f[M%i])%M;

        inv[i]=(inv[i-]*f[i])%M;

    }

}

int main()

{

    cin>>n>>m;

    init();

    ans=(C(n+m,n)%M-C(m+n,m-)%M+M)%M;

    cout<<ans<<endl;

    return ;

}

#include<cstdio>

#include<cstring>

#include<algorithm>

#define mod 20100403

#define ll long long

using namespace std;

ll n,m;

ll mul[],inv[];

ll c(ll x,ll y)

{

    return (((mul[x]*inv[x-y])%mod)*inv[y])%mod;

}

int main()

{

    scanf("%lld%lld",&n,&m);

    mul[]=mul[]=inv[]=inv[]=;

    ll tot=m+n;

    for(ll i=;i<=tot;i++)mul[i]=mul[i-]*i%mod;

    for(ll i=;i<=tot;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;

    for(ll i=;i<=tot;i++)inv[i]=inv[i]*inv[i-]%mod;

    ll ans=((c(tot,n)-c(tot,n+))%mod+mod)%mod;

    printf("%lld\n",ans);

    return ;

}

秒客网