题目大意：给出n个‘1’，m个‘0’，求用这些组成的串中，满足“前k个字符中1数不小于0数”的串的个数。（对20100403取模）

同学互测题出了原题，当时蒙蔽。除了一眼看出的dp:dp[ i ][ j ] = dp[ i-1 ][ j ] + dp[ i ][ j-1 ];

然后就是持续蒙蔽。。。

最后同学讲题，讲了一个非常nb的构造算法：

将串想象成一个巨大的表格中的一条折线，其中1代表45度向上，0代表45度向下。

要控制1>=0，只需要控制这条线保持在第一象限。

怎么计算不合法情况呢？我们只需要将折线的一部分对称下来，形成一条从( -2 , 0 )到终点的折线，此时有映射。

（下面是结论：）

ans = C( n , n+m ) - C( n+1 ， n+m);

代码：

#include
     
      #include
      
       using namespace std;#define MOD 20100403#define ll long long#define N 1000050ll n,m;ll ny[N<<1],jc[N<<1],jny[N<<1];void init(){    jc[0]=jc[1]=ny[1]=jny[0]=jny[1]=1;    for(ll i=2;i<=n+m;i++)    {        ny[i]=((MOD-MOD/i)*ny[MOD%i]%MOD+MOD)%MOD;        jc[i]=(jc[i-1]*i)%MOD;        jny[i]=(jny[i-1]*ny[i])%MOD;    }}ll C(ll a,ll b){    ll ret = jc[b];    ret = (ret * jny[a])%MOD;    ret = (ret * jny[b-a])%MOD;    return ret;}int main(){    scanf("%lld%lld",&n,&m);    init();    ll ans = ((C(n,n+m)-C(n+1,n+m))%MOD+MOD)%MOD;    printf("%lld\n",ans);    return 0;}