(n=m)时候经典的卡特兰
那(n!=m)呢,还是按照卡特兰的方式来推
首先总情况数就是(inom{n+m}{n}),在(n+m)个里选择(n)个(1)
显然有不合法的情况,减掉它们
对于一种不合法的情况,必然存在一个前缀(0)的个数比(1)多(1)
我们考虑构造出一个由(n+1)个(1)和(m-1)个(0)组成的序列,其必然存在一个前缀使得(1)的个数比(0)多(1)
于是就能一一对应了
也可以这样理解,对于每一个不合法的情况,找到第一个不合法的前缀,将其取反,之后就会得到一个(n+1)个(1)和(m-1)个(0)组成的字符串,还是可以一一对应
答案就是(inom{n+m}{n}-inom{n+m}{n+1})
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#define LL long long
#define re register
#define maxn 1000005
const LL mod=20100403;
LL n,m,fac[maxn*2];
inline int read()
{
char c=getchar();
int x=0;
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+c-48,c=getchar();
return x;
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b) return x=1,y=0,a;
LL r=exgcd(b,a%b,y,x);
y-=a/b*x;
return r;
}
inline LL inv(LL a)
{
LL x,y;
LL r=exgcd(a,mod,x,y);
return (x%mod+mod)%mod;
}
inline LL C(LL n,LL m)
{
if(m>n) return 0;
return (fac[n])*inv(fac[m]*fac[n-m]%mod)%mod;
}
int main()
{
n=read(),m=read();
fac[0]=1;
for(re int i=1;i<=n+m;i++) fac[i]=(fac[i-1]*i)%mod;
printf("%lld
",(C(n+m,n)-C(n+m,n+1)+mod)%mod);
return 0;
}