AC代碼

https://www.luogu.com.cn/record/90637978

題意：

把n個(gè)1和m個(gè)0組成字符串，但是任務(wù)還要求在組成的字符串中，在任意的前k個(gè)字符中，

1的個(gè)數(shù)不能少于0的個(gè)數(shù)。 求符合條件字符串 個(gè)數(shù)。

題解：

排列組合 + 整數(shù)乘法逆元

可以考慮把1的個(gè)數(shù)與0的個(gè)數(shù)的和看成x坐標(biāo)，

1的個(gè)數(shù)與0的個(gè)數(shù)的差看成y坐標(biāo) ：

向右上走（x坐標(biāo)加1，y坐標(biāo)加1）就表示這個(gè)字符選擇1。

向右下走（x坐標(biāo)加1，y坐標(biāo)減1）就表示這個(gè)字符選擇0。

這樣子，如果不考慮限制條件，就表示從(0,0)走n+m步到達(dá)(n+m,n-m)，

這相當(dāng)于從n+m步中選出m步向右下走，也就是組合數(shù)C(n+m,m)。

考慮限制條件，任意前綴中1的個(gè)數(shù)不少于0的個(gè)數(shù)，也就是這條路徑不能經(jīng)過直線y=-1。

可以通過對(duì)稱性發(fā)現(xiàn)，從(0,0)走到直線y=-1上的一點(diǎn)，相當(dāng)于從(-2, 0)走到該點(diǎn)。

也就是說，路徑經(jīng)過直線y=-1的方案數(shù)就是從(-2, 0)走n+m步到達(dá)(n+m,n-m)，

這個(gè)方案數(shù)可以用組合數(shù)表示為C(n+m,m-1),? 右下走的步數(shù)減一