「XXI Opencup GP of Tokyo」 Count Min Ratio

link。


简单转化问题:求所有 \(x \in [1, \lfloor R / B\rfloor]\) 对应的合法方案数之和。

对于某一 \(x\),枚举左边的红蓝球数量,可得:

\[\begin{aligned} ans_x =& \sum_{b = 0}^{B}\sum_{r = bx}^{R - (B-b)x}\binom{r + b}{b}\binom{R - r + B - b}{B - b} \\ =& \sum_{b = 0}^{B}\sum_{d = 0}^{R - Bx}\binom{(bx + d) + b}{b}\binom{R - (bx + d) + B - b}{B - b} \\ =& \sum_{d = 0}^{R - Bx}\sum_{b = 0}^{B}\binom{(x + 1)b + d}{b}\binom{(x + 1)(B - b) + (R - Bx - d)}{B - b} \\ \end{aligned} \]

以下记 \(t = x + 1\)。


系数 \(\binom{tb + d}{b}\) 与广义二项级数 \(\mathcal B_t(z)\) 有关。

记 \(G(z) = \frac{z}{(1 + z)^t}\),则它的复合逆 \(F(z) = \mathcal B_t(z) - 1\)。于是:

\[\binom{tb + d}{b}z^b = (1 + F)^d\times\frac{1 + F}{1 - (t - 1)F} \]

关于广义二项级数的详细内容可见文末。


代入原式,可得:

\[\begin{aligned} & \sum_{d = 0}^{R - Bx}\sum_{b = 0}^{B}\binom{tb + d}{b}\binom{t(B - b) + (R - Bx - d)}{B - b} \\ =& \sum_{d = 0}^{R - Bx}\sum_{b = 0}^{B}\left([z^b](1 + F)^d\times\frac{1 + F}{1 + F - tF}\right)\left([z^{B-b}](1 + F)^{R - Bx - d}\times\frac{1 + F}{1 + F - tF}\right) \\ =& [z^B]\sum_{d = 0}^{R - Bx}\left((1 + F)^d\times\frac{1 + F}{1 + F - tF}\right)\left((1 + F)^{R - Bx - d}\times\frac{1 + F}{1 + F - tF}\right) \\ =& (R - Bx + 1)\left([z^B](1 + F)^{R - Bx}\times\left(\frac{1 + F}{1 + F - tF}\right)^2\right) \\ \end{aligned} \]

考虑对 \(H(F) = (1 + F)^{R - Bx}\times\left(\frac{1 + F}{1 - (t - 1)F}\right)^2\) 进行拉格朗日反演:

\[\begin{aligned} [z^B]H =&[z^0]zH\times G'G^{-B-1} \\ =&[z^0]z(1 + z)^{R - Bx}\times\left(\frac{1 + z}{1 - (t - 1)z}\right)^2\times\frac{1 - (t - 1)z}{(1 + z)^{t + 1}}\times\left(\frac{(1 + z)^{(B + 1)t}}{z^{B + 1}}\right) \\ =&[z^B]\frac{(1 + z)^{(R - Bx) + 2 - (t + 1) + (B + 1)t}}{1 - (t - 1)z} \\ =&[z^B]\frac{(1 + z)^{R + B + 1}}{1 - xz} \\ =&\sum_{i = 0}^{B}\binom{R + B + 1}{i}x^{B - i} \end{aligned} \]

那么答案为 \((R + 1)\sum_{i = 0}^{B}\binom{R + B + 1}{i}\left(\sum_{x = 1}^{\lfloor R / B\rfloor}x^{B - i}\right) - B\sum_{i = 0}^{B}\binom{R + B + 1}{i}\left(\sum_{x = 1}^{\lfloor R / B\rfloor}x^{B - i + 1}\right)\)。

多项式求逆算自然数幂和即可。


如果你是来找广义二项级数的详细内容。

很抱歉,它

上一篇:2016北京集训测试赛(十六)Problem A: 任务安排


下一篇:GYM 102978 | XXI Opencup GP of Tokyo