字符串

 

【题目描述】

lxhgww最近接到了一个生成字符串的任务，任务需要他把n个1和m个0组成字符串，但是任务还要求在组成的字符串中，在任意的前k个字符中，1的个数不能少于0的个数。现在lxhgww想要知道满足要求的字符串共有多少个，聪明的程序员们，你们能帮助他吗？

【输入】

输入数据是一行，包括2个数字n和m

【输出】

输出数据是一行，包括1个数字，表示满足要求的字符串数目，这个数可能会很大，只需输出这个数除以20100403的余数

【样例输入】

2 2

【样例输出】

2

【数据范围】

对于30%的数据，保证1<=m<=n<=1000

对于100%的数据，保证1<=m<=n<=1000000

=================================================================
。。。这题是最悲剧的一题。。。以前做过原题。。。然后考试的时候紧张的啥都不知道了。。。数学不过关啊！！T_T
一种推导是这样的：
总的01串的数量为C(n+m,n)，考虑除去不符合条件的。
对于一个不符合条件的01串，一定有某个位置使得0的个数第一次超过1的个数，比如：
1010011010
      |
设该位置是p，在1~p中1的个数为a，0的个数为a+1
则在p~n+m中，1的个数为n-a，0的个数为m-a-1
如果对p~n+m中的0和1取反，则在p~n+m中，1的个数为m-a-1，0的个数为n-a
对于这样一个变换后的串，共有m-1个1，n+1个0。
由于每一个不符合条件的有n个1，m个0的01串都可以唯一确定对应一个有m-1个1，n+1个0的01串，
并且每一个有m-1个1，n+1个0的01串一定有一个位置开始0的个数第一次多于1的个数，把这个位置之后的串取反后得到的01串可以唯一确定对应一个有n个1，m个0的不符合条件的01串，所以这两种串是一一对应的。
所以不符合条件的串的个数为C(n+m,n+1)
所以最后的答案为C(n+m,n) - C(n+m,n+1)
PS：算这个的时候可以分解质因数（hyf神牛神做法），也可以用逆元解决除法的问题。因为20100403是质数，所以逆元就可以不用解方程算了，直接取a^(p-2)次方即可。

#include <iostream>
#define ll long long
#define MOD 20100403
#define MAXN 2100000
 
using namespace std;

/**//*
   C(n+m,n) - C(n+m,n+1)
 */
ll n, m;
ll fact[MAXN+1];

ll PowerMod(ll a, int b){
   if (b == 0) return 1;
   ll t = PowerMod(a, b>>1);
   t = (t * t) % MOD;
   if (b&1) t = (t * a) % MOD;
   return t;
}
ll Rev(ll a){
   return PowerMod(a, MOD-2);
}
void Init(){
     cin >> n >> m;
}

ll C(int n, int m){
   return fact[n] * Rev(fact[m]) % MOD * Rev(fact[n-m]) % MOD;
}
void Solve(){
     fact[0] = 1;
     for (ll i = 1; i<=n+m; i++)
         fact[i] = (fact[i-1] * i) % MOD;
     cout << ((C(n+m,n) - C(n+m,n+1)) % MOD + MOD) % MOD;
}

int main(){
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    Init();
    Solve();
    return 0;
}