BZOJ 1856 字符串（组合）

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1856

题意：有n个1和m个0组成的串，使得任意前k个中1的个数不少于0的个数。有多少种这样的串？

思路：设1为向(1,1)方向走，0为向(1,-1)方向走。那么题意可转化为从(0,0)走到(n+m,n-m)且不能跨过y=0的方案数。总方案数C(n+m,n)，然后要减去不合法的即线路通过y=-1的。将线路与y=-1交点的左边沿着y=-1做对称操作，则最后等价于从(0,-2)走到(n+m,n-m)的方案数。因为从(0,-2)

走到(n+m,n-m)需要向上走n-m+2次，一共要走n+m次。设向上向下各走x,y，那么x+y=n+m,x-y=n-m+2得到x=n+1,y=m-1，所以不合法的方案为C(n+m,m-1)。

 

 
i64 n,m;


i64 exGcd(i64 a,i64 b,i64 &x,i64 &y)
{
    if(b==0)
    {
        x=1; y=0;
        return a;
    }
    i64 temp=exGcd(b,a%b,x,y);
    i64 t=x;
    x=y;
    y=t-a/b*y;
    return temp;
}


i64 reverse(i64 a,i64 b)
{
    i64 x,y;
    exGcd(a,b,x,y);
    return (x%b+b)%b;
}


i64 get(i64 n)
{
    i64 ans=1,i;
    FOR1(i,n) ans=ans*i%mod;
    return ans;
}


i64 cal(i64 n,i64 m)
{
    i64 x=get(n),y=get(m),z=get(n-m);
    return x*reverse(y,mod)%mod*reverse(z,mod)%mod;
}


int main()
{
    RD(n,m);
    i64 ans=cal(n+m,n)-cal(n+m,n+1);
    ans=(ans%mod+mod)%mod;
    PR(ans);
}