AC代碼

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

題意：

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

1的個數不能少于0的個數。 求符合條件字符串 個數。

題解：

排列組合 + 整數乘法逆元

可以考慮把1的個數與0的個數的和看成x坐標，

1的個數與0的個數的差看成y坐標 ：

向右上走（x坐標加1，y坐標加1）就表示這個字符選擇1。

向右下走（x坐標加1，y坐標減1）就表示這個字符選擇0。

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

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

考慮限制條件，任意前綴中1的個數不少于0的個數，也就是這條路徑不能經過直線y=-1。

可以通過對稱性發(fā)現，從(0,0)走到直線y=-1上的一點，相當于從(-2, 0)走到該點。

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

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