题目：BZOJ1856、洛谷P1641、codevs2418。
题目大意：给你n个1和m个0，让你用它们组成长度为n+m的串，问有多少串满足，它的任意前缀中的1总是不少于0（答案mod20100403）。
解题思路：这题和字符串一点关系也没有！！
首先我们可以把题目转化为：从0,0走到n+m,n-m，每次可以走(1,1)或(1,-1)，求不经过直线y=-1的方案数。
我们先不考虑“不经过直线y=-1”的限制，那么方案数为$C^{m}_{n+m}$。
现在我们考虑不满足条件的方案数，其实就相当于从-2,0走到n+m,n-m的方案数，所以方案数为$C^{m-1}_{n+m}$。
所以答案就为“总方案数-不满足条件的方案数”。
$$egin{align}C^m_{n+m}-C^{m-1}_{n+m}&=&frac{(n+m)!}{n!m!}-frac{(n+m)!}{(n+1)!(m-1)!}\&=&frac{(n+m)!(n+1)-(n+m)!m}{(n+1)!m!}\&=&frac{(n-m+1)(n+m)!}{(n+1)!m!}\&=&(n-m+1)frac{(n+2)(n+3)...(n+m)}{m!}\&=&(n-m+1)(n+2)(n+3)...(n+m)÷1÷2÷...÷mend{align}$$
由于用到取模运算，还要除以1~m，所以需要用到逆元。
既然需要1~m的所有逆元，而且模数是个质数，那就用线性推逆元好了。
可惜的是，在推逆元的时候乘法超int，没有转化为long long，导致没有一发AC。
C++ Code：
#include<cstdio>
using namespace std;
#define p 20100403
int n,m,fact,inv[1000005];
int main(){
scanf("%d%d",&n,&m);
int ans=1;
inv[1]=1;
for(int i=2;i<=m;++i)
inv[i]=(long long)(p-p/i)*inv[p%i]%p;
for(int i=2;i<=m;++i)ans=(long long)ans*(i+n)%p;
ans=(long long)ans*(n-m+1)%p;
for(int i=1;i<=m;++i)
ans=(long long)ans*inv[i]%p;
printf("%d
",ans);
return 0;
}