Gym102978C Count Min Ratio 题解

标签：Count frac 题解 sum mathcal Ratio binom aligned Bx

赛时无人场切。震撼，震撼。学到许多。全程贺 zak。

首先我们套路推下式子。枚举左边的红蓝球个数，答案即为

\[\begin{aligned} &\sum_{b=0}^B\sum_{r=0}^R\binom{b+r}b\binom{B-b+R-r}{B-b}\min(\frac rb,\frac{R-r}{B-b})\\ =&\sum_{x=1}^{\frac RB}\sum_{b=0}^B\sum_{r=0}^R\binom{b+r}b\binom{B-b+R-r}{B-b}[bx\le r][(B-b)x\le R-r]\\ =&\sum_{x=1}^{\frac RB}\sum_{b=0}^B\sum_{r=0}^R\binom{b+r}b\binom{B-b+R-r}{B-b}[r-bx\ge 0][r-bx\le R-Bx]\\ =&\sum_{x=1}^{\frac RB}\sum_{b=0}^B\sum_{i=0}^{R-Bx}\binom{b+bx+i}b\binom{B-b+R-bx-i}{B-b} \end{aligned} \]

有两种推法，组合意义天地灭，代数推导保平安。使用广义二项级数：

\[\begin{aligned} =&\sum_{x=1}^{\frac RB}\sum_{b=0}^B\sum_{i=0}^{R-Bx}\binom{b(x+1)+i}b\binom{(B-b)(x+1)+R-Bx-i}{B-b}\\ =&\sum_{x=1}^{\frac RB}\sum_{i=0}^{R-Bx}\sum_{b=0}^B[z^b]\frac{\mathcal B_{x+1}(z)^i}{1-(x+1)-(x+1)\mathcal B_{x+1}(z)^{-1}}[z^{B-b}]\frac{\mathcal B_{x+1}(z)^{R-Bx-i}}{1-(x+1)-(x+1)\mathcal B_{x+1}(z)^{-1}}\\ =&\sum_{x=1}^{\frac RB}\sum_{i=0}^{R-Bx}[z^B]\frac{\mathcal B_{x+1}(z)^{R-Bx}}{(1-(x+1)-(x+1)\mathcal B_{x+1}(z)^{-1})^2}\\ =&\sum_{x=1}^{\frac RB}(R-Bx+1)[z^B]\frac{\mathcal B_{x+1}(z)^{R-Bx}}{(1-(x+1)-(x+1)\mathcal B_{x+1}(z)^{-1})^2} \end{aligned} \]

把后边的拿出来：

\[\begin{aligned} &[z^B]\frac{\mathcal B_{x+1}(z)^{R-Bx}}{(1-(x+1)-(x+1)\mathcal B_{x+1}(z)^{-1})^2}\\ =&[z^B]\frac 1{1-(x+1)(1-\mathcal B_{x+1}(z)^{-1})}\frac{\mathcal B_{x+1}(z)^{R-Bx}}{1-(x+1)-(x+1)\mathcal B_{x+1}(z)^{-1}}\\ =&[z^B]\sum_{i=0}^B(x+1)^i(1-\mathcal B_{x+1}(z)^{-1})^i\frac{\mathcal B_{x+1}(z)^{R-Bx}}{1-(x+1)-(x+1)\mathcal B_{x+1}(z)^{-1}}\\ =&[z^B]\sum_{i=0}^B(x+1)^i\sum_{j=0}^i\binom ij(-1)^j\frac{\mathcal B_{x+1}(z)^{R-Bx-j}}{1-(x+1)-(x+1)\mathcal B_{x+1}(z)^{-1}}\\ =&\sum_{i=0}^B(x+1)^i\sum_{j=0}^i\binom ij(-1)^j\binom{R+B-j}B \end{aligned} \]

后边的工作就是我们熟悉的了：不断把组合数卷积写成生成函数即可。

\[\begin{aligned} =&\sum_{i=0}^B(x+1)^i\sum_{j=0}^i[x^j](1-x)^i[x^{B-j}]\frac 1{(1-x)^{B+1}}\\ =&\sum_{i=0}^B(x+1)^i[x^R]\frac 1{1-x}^{B+1-i}\\ =&\sum_{i=0}^B(x+1)^i\binom{B+R-i}R\\ =&\sum_{i=0}^B\sum_{j=0}^i\binom ijx^j\binom{B+R-i}R\\ =&\sum_{j=0}^Bx^j\sum_{i=j}^B\binom ij\binom{B+R-i}R\\ =&\sum_{j=0}^Bx^j\binom{B+R+1}{R+j+1} \end{aligned} \]

扔回去：

\[\begin{aligned} &\sum_{x=1}^{\frac RB}(R-Bx+1)\sum_{j=0}^Bx^j\binom{B+R+1}{R+j+1}\\ =&\sum_{j=0}^B\binom{B+R+1}j(R-Bx+1)\sum_{x=1}^{\frac RB}x^{B-j} \end{aligned} \]

那随便做就行了。代码看 zak 的去。

标签：Count,frac,题解,sum,mathcal,Ratio,binom,aligned,Bx
From： https://www.cnblogs.com/gtm1514/p/17437763.html