题意

• 把n个1，m个0组成字符串，要求任意前k个字符中，1的个数不少于0的个数
• 求解满足要求的字符串有多少个

思路

• 总保证前缀和大于0
• 卡特兰数板子题
• 求解f(n)
• 组合数求解要开逆元，x%p的逆元和x的逆元相等

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=20100403;

int f[2010101];
void cal(int x){
    f[1]=1;
    for(int i=2;i<=x;i++){
        f[i]=i*f[i-1]%p;
    }
}
int C(int x,int y){
    int up=p-2;
    int res=1;
    int bas=f[y]*f[x-y]%p;
    while(up){
        if(up&1){
            res=res*bas%p;
        }
        bas=bas*bas%p;
        up>>=1;
    }
    return (f[x]*res%p);
}
signed main(){
    int n,m;
    cin >> n >> m;
    if(n<m) cout << 0 << endl;
    else{
        cal(n+m);
        cout << ((C(n+m,n)-C(n+m,n+1)+p)%p) << endl;
    }
    return 0;
}