这是一道Catalan+Lucas+乘法逆元+容斥原理の题目

首先我们可以把题意转化为一张图片

如果我们把向右走看成选择一个 $1$ 那么向上走就要相应的看成选择一个 $0$

那么当我们从 $(0,0)$ 走到 $(n,m)$ 时我们就完成了字符串的生成

那么抛开题目的任意前缀中 $1$ 的个数必须 $\ge$ $0$ 的个数の条件

我们计算一下一共有多少种方案数

显然，对于每一步我们都可以向上或向右。

我们一共需要走 $n+m$ 步才能到达 $(n,m)$ 且其中 $n$ 步必须向右

剩余部分(即剩余 $m$ )步必须向上

所以总的方案数为 $\Large{C^n_{n+m}}$ 或 $\Large{C^m_{n+m}}$ (两者相等)

那么原题目的限制条件又怎么处理呢?

我们不难发现只要任一时刻向右走的次数大于等于向上走的次数

就可以判断该情况是否合法

我们可以把每个零界点标出来，即每个 $(x,x+1)$

that is 每个点的向上走的次数正好比向右走的次数多一(刚刚跨越条件)

我们把这条直线画出来(图中红线)

只要我们的点不经过红线且能到达点 $(n,m)$

则该路径生成的字符串一定为合法字符串

我们可以考虑用全部的到达 $(n,m)$ 的方案数减去经过红线但是到达 $(n,m)$ 的方案数

这样就可以求出不经过红线且到达 $(n,m)$ 的方案数了，即为题目所求

我们把经过红线的每条到达 $(n,m)$ 的路径记为 $l_i$

我们可以把每个 $l_i$ 经过红线后的部分翻转这样我们走到的终点不是 $(n,m)$

而是 $(m-1,n+1)$ 不懂可以再看看上面图片

那么我们依样画葫芦从点 $(0,0)$ 走到 $(m-1,n+1)$ 的方案数就为

$\Large{C^{n+1}_{n+m}}$ 或 $\Large{C^{m-1}_{n+m}}$ (两者相等)

那么 $ans$ = $\Large{C^n_{n+m}}-\Large{C^{n+1}_{n+m}}$

最后别忘记Lucas和乘法逆元处理取模结果(这里不详细展开了)

code:

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod=20100403;
ll n,m;
ll fpow(ll x,ll y){
    ll tot=1,base=x;
    for(;y;y>>=1){
        if((y&1))tot=(tot*base)%mod;
        base=(base*base)%mod;
    }
    return tot%mod;
}
ll C(int n,int m){
    ll sum=1,ni=1;
    for(int i=1;i<=m;++i){
        sum=(sum*(n-i+1))%mod;
        ni=(ni*i)%mod;
    }
    ni=fpow(ni,mod-2);
    return (sum*ni)%mod;
}
ll lcs(ll n,ll m){
    if(m==0)return 1;
    return C(n%mod,m%mod)*lcs(n/mod,m/mod)%mod;
}
int main(){
    scanf("%lld%lld",&n,&m);
    printf("%lld",((lcs(n+m,n)-lcs(n+m,n+1))%mod+mod)%mod);
    return 0;
}

#include<bits/stdc++.h> 
using namespace std;
typedef long long LL;

LL qpow(LL a, LL b, LL p)
{
	LL ans=1;
	for(;b;b>>=1)
	{
		if(b&1)ans=ans*a%p;
		a=a*a%p;
	}
	return ans;
}
LL C(LL n, LL m, LL p)
{
	LL tn=1, tm=1;
	for(int i=1;i<=m;i++)
	{
		tn=tn*(n-i+1)%p;
		tm=tm*i%p;
	}
	return tn*qpow(tm, p-2, p)%p;
}
int main()
{
	LL n, m;scanf("%lld%lld", &n, &m);
	LL p=20100403;
	LL ans=C(n+m, m, p)-C(n+m, m-1, p);
	ans=(ans+p)%p;
	printf("%lld\n", ans); 
	return 0;
}