P1641 [SCOI2010]生成字符串

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

---

思路：模拟卡特兰数的推导过程，找到不合法情况的双射，用总情况-不合法情况即可

答案为\(C_{m+n}^m-C_{m+n}^{m-1}\)

---

Code:

#include 
    
     #define ll long longconst ll mod=20100403;ll fac[1000010];ll inv(ll b,ll k){    ll f=1;    while(k)    {        if(k&1) f=f*b%mod;        b=b*b%mod;        k>>=1;    }    return f;}ll C(ll n,ll m){    return fac[m]*inv(fac[n],mod-2)%mod*inv(fac[m-n],mod-2)%mod;}int main(){    ll n,m;    scanf("%lld%lld",&n,&m);    fac[0]=1;    for(int i=1;i<=n+m;i++)        fac[i]=fac[i-1]*i%mod;    printf("%lld\n",((C(m,m+n)-C(m-1,m+n))%mod+mod)%mod);    return 0;}
    

---

2018.8.9