1856: [Scoi2010]字符串

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 2117  Solved: 1211

[][][]

Description

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

Input

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

Output

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

Sample Input

2 2

Sample Output

2

HINT

【数据范围】

对于30%的数据，保证1<=m<=n<=1000

对于100%的数据，保证1<=m<=n<=1000000

Source

 

/*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
      
       #define N 2000002#define M 20100403#define ll long longusing namespace std;ll n,m,ans;ll inv[N]={
    1,1},fac[N]={
    1,1},f[N]={
    1,1};int ll C(ll a,ll b){    return ((fac[a]*inv[b])%M*inv[a-b]%M)%M;}inline void init(){    fac[1]=1;    for(int i=2;i<=n+m+1;i++)    {        fac[i]=(fac[i-1]%M*i)%M;        f[i]=((M-M/i)*f[M%i])%M;        inv[i]=(inv[i-1]*f[i])%M;    }}int main(){    cin>>n>>m;    init();    ans=(C(n+m,n)%M-C(m+n,m-1)%M+M)%M;    cout<
       
        <
       
      

 

 

#include
       
        #include
        
         #include
         
          #define mod 20100403#define ll long longusing namespace std;ll n,m;ll mul[2000005],inv[2000005];ll c(ll x,ll y){    return (((mul[x]*inv[x-y])%mod)*inv[y])%mod;}int main(){    scanf("%lld%lld",&n,&m);    mul[0]=mul[1]=inv[0]=inv[1]=1;    ll tot=m+n;    for(ll i=2;i<=tot;i++)mul[i]=mul[i-1]*i%mod;    for(ll i=2;i<=tot;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;    for(ll i=2;i<=tot;i++)inv[i]=inv[i]*inv[i-1]%mod;    ll ans=((c(tot,n)-c(tot,n+1))%mod+mod)%mod;    printf("%lld\n",ans);    return 0;}