BZOJ1856 - Click Here
Description
lxhgww最近接到了一个生成字符串的任务，任务需要他把n个1和m个0组成字符串，但是任务还要求在组成的字符串中，在任意的前k个字符中，1的个数不能少于0的个数。现在lxhgww想要知道满足要求的字符串共有多少个，聪明的程序员们，你们能帮助他吗？
Input
输入数据是一行，包括2个数字n和m
Output
输出数据是一行，包括1个数字，表示满足要求的字符串数目，这个数可能会很大，只需输出这个数除以20100403的余数
Solutions
把0看做(+1,-1)，1看做(+1,+1)，答案即为从(0,0)走到(n+m,n-m)，且不经过y=-1直线的方案数。
至于具体的求法，就是利用总方案-不合法方案。而不合法方案可以利用对称，转换为从(0,-2)走到(n+m,n-m)的方案数。
所以答案就是$C^{n}_{n+m} - C^{n+1}_{n+m}$(其实就是卡特兰数)
另外，由于数字很大还要求出乘法逆元，防止爆long long。(20100403为质数，保证存在逆元)
CODE
CODE - Click Here