1856: [Scoi2010]字符串
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 1301 Solved: 719[][][]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<=1000000Source
分析：如果题目仅仅给出了例如n,m的几个大数据，让你求几乎“毫不相干”的数据，那么可能就要用到递推或者公式（也就是数学方法啦）.这道题感觉可以用dp做，但是时间承受不了，而能神奇地降低时间复杂度的也就只有数学方法了.
如果直接用数学方法做看起来并不好做，转换一下，在一个平面直角坐标系中，从点(0,0)到点(n + m,n - m),一个1相当于从(0,0)向(1,1)的方向走，一个0相当于(0,0)向(1,-1)的方向走，同时不能走到直线y = -1上，可以证明，如果要走n个1，m个0必然要走到(n + m, n - m),求方案数，可以想到用dp或者直接组合数搞起,先考虑没有限制条件的,可以发现n个1是必须取完的一共要取n + m个数，那么要在n + m个数中取n个数，自然方案数就是C(n + m,n)，符合条件的方案数=总方案数-不符合条件的方案数，那么我们求出不符合条件的方案数,怎么求呢？可以想象一下把直线y = -1上面的翻折下来，即从点(0,-2)到点(n + m, n - m)经过直线y = -1的方案数，显而易见，肯定经过直线y=-1,关键就是怎么求方案数,走到(n+m,n-m)需要向上走n-m+2次，一共要走n+m次。设向上向下各走x,y，那么x+y=n+m,x-y=n-m+2得到x=n+1,y=m-1，所以不合法的方案为C(n+m,n + 1)。然后就是求组合数的过程.因为组合数只需要用到1次，显然不需要递推，那么就直接算，但是要涉及到取模，除法取模运算不成立！怎么办？用逆元！若，b*b1 % c == 1则，b1称为b模c的乘法逆元。 ( a/b ) % c == ( a*b1 ) % c ，那么问题就是怎么求b1, -k*c + b*b1 == 1，不是扩展欧几里得算法吗？那么直接算就好了.
#include#include #include #include #include using namespace std;const int mod = 20100403;long long ans;int n, m;void exgcd(long long a, long long b, long long & x, long long &y){ if (b == 0) { x = 1; y = 0; } else { exgcd(b, a%b, x, y); long long t = x; x = y; y = t - a / b * y; }}long long niyuan(long long a, long long p){ long long x, y; exgcd(a, p, x, y); x = (x + mod) % mod; return x;}long long Sum(long long x){ long long temp = 1; for (int i = 1; i <= x; i++) { temp = (temp * i) % mod; } return temp;}long long C(long long x, long long y){ long long a, b, c; a = Sum(x); b = Sum(y); c = Sum(x - y); return a * niyuan(b, mod) % mod * niyuan(c, mod) % mod;}int main(){ scanf("%d%d", &n, &m); ans = (C(n + m, n) - C(n + m, n + 1) + mod) % mod; printf("%lld", ans); return 0;}