• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

「XXI Opencup GP of Tokyo」 Count Min Ratio

开发技术 开发技术 2周前 (04-30) 3次浏览

link。


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

对于某一 (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)^dtimesfrac{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)^dtimesfrac{1 + F}{1 + F – tF}right)left([z^{B-b}](1 + F)^{R – Bx – d}timesfrac{1 + F}{1 + F – tF}right) \
=& [z^B]sum_{d = 0}^{R – Bx}left((1 + F)^dtimesfrac{1 + F}{1 + F – tF}right)left((1 + F)^{R – Bx – d}timesfrac{1 + F}{1 + F – tF}right) \
=& (R – Bx + 1)left([z^B](1 + F)^{R – Bx}timesleft(frac{1 + F}{1 + F – tF}right)^2right) \
end{aligned}
]

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

[begin{aligned}
[z^B]H
=&[z^0]zHtimes G’G^{-B-1} \
=&[z^0]z(1 + z)^{R – Bx}timesleft(frac{1 + z}{1 – (t – 1)z}right)^2timesfrac{1 – (t – 1)z}{(1 + z)^{t + 1}}timesleft(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 / Brfloor}x^{B – i}right) – Bsum_{i = 0}^{B}binom{R + B + 1}{i}left(sum_{x = 1}^{lfloor R / Brfloor}x^{B – i + 1}right))

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


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

很抱歉,它 🕊 了。


程序员灯塔
转载请注明原文链接:「XXI Opencup GP of Tokyo」 Count Min Ratio
喜欢 (0)