字符串

 

【題目描述】

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;
}