传送门

一个单次回答$O(n)$的非正解，介于该题数据水所以能过。

总方案数为$C_{m+n}^n$，用总方案数减去不合法的即为答案。

枚举一下第一个不合法的位置$i$。换句话说，枚举一个位置$i$，在它前面的$0,1$数量相等，在该位上放一个$0$，就能产生一种不合法的情况。显然$i$为奇数。

前面$0,1$数量相等就是卡特兰数$C_{i-1}$，后面$n+m-i$个位置放$n-\frac{i-1}{2}$个$1$，有$C_{n+m-i}^{n-\frac{i-1}{2}}$种情况，乘起来就是答案。

其实这个式子应该能化成正解的式子，然而太复杂而且足以通过此题。

因为$n+m$超模数了所以还要再套个卢卡斯，不过这里只是个极小的小常数了。

这个思路还是蛮好想的$QwQ$

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 4000005
#define inf 0x3f3f3f3f

const int mod = 20100403;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int fac[maxn]={1},inv[maxn];
int INV(int x){return x==1?1:1ll*(mod-mod/x)*INV(mod%x)%mod;}
inline int C(int n,int m){
    if(n<m)return 0;
    if(n>=mod)return 1ll*C(n/mod,m/mod)*(n%mod,m%mod)%mod;
    return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
inline int Cat(int n){
    return 1ll*fac[n<<1]*inv[n]%mod*inv[n+1]%mod;
}
int main(){
    int n=read(),m=read();
    for(register int i=1;i<=n+m<<1;++i)fac[i]=1ll*fac[i-1]*i%mod;
    inv[n+m<<1]=INV(fac[n+m<<1]);
    for(register int i=(n+m<<1)-1;~i;--i)inv[i]=1ll*inv[i+1]*(i+1)%mod;
    int ans=0;
    for(register int i=1;i<=n+m;i+=2)
        (ans+=1ll*Cat(i-1>>1)*C(n+m-i,n-(i-1>>1))%mod)%=mod;
    printf("%d\n",(C(n+m,n)-ans+mod)%mod);
}