字符串

 

【題目描述】

lxhgww最近接到了一個(gè)生成字符串的任務(wù)，任務(wù)需要他把n個(gè)1和m個(gè)0組成字符串，但是任務(wù)還要求在組成的字符串中，在任意的前k個(gè)字符中，1的個(gè)數(shù)不能少于0的個(gè)數(shù)。現(xiàn)在lxhgww想要知道滿足要求的字符串共有多少個(gè)，聰明的程序員們，你們能幫助他嗎？

【輸入】

輸入數(shù)據(jù)是一行，包括2個(gè)數(shù)字n和m

【輸出】

輸出數(shù)據(jù)是一行，包括1個(gè)數(shù)字，表示滿足要求的字符串?dāng)?shù)目，這個(gè)數(shù)可能會(huì)很大，只需輸出這個(gè)數(shù)除以20100403的余數(shù)

【樣例輸入】

2 2

【樣例輸出】

2

【數(shù)據(jù)范圍】

對(duì)于30%的數(shù)據(jù)，保證1<=m<=n<=1000

對(duì)于100%的數(shù)據(jù)，保證1<=m<=n<=1000000

=================================================================
。。。這題是最悲劇的一題。。。以前做過原題。。。然后考試的時(shí)候緊張的啥都不知道了。。。數(shù)學(xué)不過關(guān)啊！！T_T
一種推導(dǎo)是這樣的：
總的01串的數(shù)量為C(n+m,n)，考慮除去不符合條件的。
對(duì)于一個(gè)不符合條件的01串，一定有某個(gè)位置使得0的個(gè)數(shù)第一次超過1的個(gè)數(shù)，比如：
1010011010
      |
設(shè)該位置是p，在1~p中1的個(gè)數(shù)為a，0的個(gè)數(shù)為a+1
則在p~n+m中，1的個(gè)數(shù)為n-a，0的個(gè)數(shù)為m-a-1
如果對(duì)p~n+m中的0和1取反，則在p~n+m中，1的個(gè)數(shù)為m-a-1，0的個(gè)數(shù)為n-a
對(duì)于這樣一個(gè)變換后的串，共有m-1個(gè)1，n+1個(gè)0。
由于每一個(gè)不符合條件的有n個(gè)1，m個(gè)0的01串都可以唯一確定對(duì)應(yīng)一個(gè)有m-1個(gè)1，n+1個(gè)0的01串，
并且每一個(gè)有m-1個(gè)1，n+1個(gè)0的01串一定有一個(gè)位置開始0的個(gè)數(shù)第一次多于1的個(gè)數(shù)，把這個(gè)位置之后的串取反后得到的01串可以唯一確定對(duì)應(yīng)一個(gè)有n個(gè)1，m個(gè)0的不符合條件的01串，所以這兩種串是一一對(duì)應(yīng)的。
所以不符合條件的串的個(gè)數(shù)為C(n+m,n+1)
所以最后的答案為C(n+m,n) - C(n+m,n+1)
PS：算這個(gè)的時(shí)候可以分解質(zhì)因數(shù)（hyf神牛神做法），也可以用逆元解決除法的問題。因?yàn)?span lang=EN-US>20100403是質(zhì)數(shù)，所以逆元就可以不用解方程算了，直接取a^(p-2)次方即可。