题意:
找出由n个1,m个0组成的字符串，且任意前几个字符中1的个数不能比0的个数少，询问满足要求的字符串个数。
解析:
很容易转化一下题意，转化到从一个矩阵的左下走到右上不能过某条线的方案数。
如果我们把1看作走一个向量（1,1）,0看作走一个向量（1,-1），那么我们可以把模型转化成从（0,0）走到（n+m,n-m）并且不能经过直线y=-1的方案数。
暂且不考虑限制答案显然为C(n+m,m)，如果考虑限制的话，我们看图发现经过y=-1的情况可以看作从（0,-2）出发到（n+m,n-m）的方案数。
![bzoj1856: [Scoi2010]字符串](http://www.daimami.com/img/2023/09/30/4ffb80a2-b867-4701-9047-0fd8b90e2a7f.jpg)
Submit: 1347 Solved: 742
[Submit][Status][Discuss]
找出由n个1,m个0组成的字符串，且任意前几个字符中1的个数不能比0的个数少，询问满足要求的字符串个数。
解析:
很容易转化一下题意，转化到从一个矩阵的左下走到右上不能过某条线的方案数。
如果我们把1看作走一个向量（1,1）,0看作走一个向量（1,-1），那么我们可以把模型转化成从（0,0）走到（n+m,n-m）并且不能经过直线y=-1的方案数。
暂且不考虑限制答案显然为C(n+m,m)，如果考虑限制的话，我们看图发现经过y=-1的情况可以看作从（0,-2）出发到（n+m,n-m）的方案数。
所以不合法的方案数恰好为C(n+m,m-1)（原来能选m个0，但是现在由于纵坐标下降了2，所以只好少走一个0，多走一个1转化成m-1，当然也可以看做是(n+m-(n-m+2))>>1）
1856: [Scoi2010]字符串
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 1347 Solved: 742
[Submit][Status][Discuss]
Description
lxhgww最近接到了一个生成字符串的任务，任务需要他把n个1和m个0组成字符串，但是任务还要求在组成的字符串中，在任意的前k个字符中，1的个数不能少于0的个数。现在lxhgww想要知道满足要求的字符串共有多少个，聪明的程序员们，你们能帮助他吗？
Input
输入数据是一行，包括2个数字n和m
Output
输出数据是一行，包括1个数字，表示满足要求的字符串数目，这个数可能会很大，只需输出这个数除以20100403的余数
Sample Input
2 2
Sample Output
2
HINT
【数据范围】
对于30%的数据，保证1<=m<=n<=1000
对于100%的数据，保证1<=m<=n<=1000000
附本蒟蒻代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<climits>
#define N 4000001
#define mod 20100403
using namespace std;
typedef long long ll;
ll A[N],n,m,fac[N];
void init()
{A[1]=fac[1]=1;for(ll i=2;i<=n+m;i++)fac[i]=fac[i-1]*i%mod;for(ll i=2;i<=n+m;i++)A[i]=(mod-mod/i)*A[mod%i]%mod; }
int main()
{scanf("%lld%lld",&n,&m);init();ll tmp=fac[n+m],txp=fac[n+m];for(int i=1;i<=n;i++)tmp=tmp*A[i]%mod;for(int i=1;i<=m;i++)tmp=tmp*A[i]%mod;for(int i=1;i<=m-1;i++)txp=txp*A[i]%mod;for(int i=1;i<=n+1;i++)txp=txp*A[i]%mod;printf("%lld\n",(tmp-txp+mod)%mod);
}