有 \(R\) 个红球，\(B\) 个蓝球和一个绿球，同色球之间无区别。将其任意排列，令 \(l_R,l_B,r_R,r_B\) 分别为绿球左 / 右边的红 / 蓝球数量。定义一个方案的权值为 \(\max\{x\in Z^+\mid l_R\geq l_B x\ \land\ r_R\geq r_Bx \}\)，求所有方案的权值和。
数据范围：\(R\leq 10^{18},B\leq 10^6\)。
考虑到答案为：
\[\begin{aligned} &\sum_{x=1}^{\lfloor\frac{R}{B}\rfloor}\sum_{b=0}^{B}\sum_{r=bx}^{R-(B-b)x}{r+b\choose b}{B-b+R-r\choose B-b}\\ &=\sum_{x=1}^{\lfloor\frac{R}{B}\rfloor}\sum_{b=0}^{B}\sum_{r=0}^{R-Bx}{b(x+1)+r\choose b}{(B-b)(x+1)+R-Bx-r\choose B-b}\\ \end{aligned} \]接着记 \(t=x+1\) 。我们发现系数都是 \({tb+r\choose b}\) 形式的，可以想到 广义二项级数 \(\mathcal{B}_t(z)\) 。
考虑到 \([z^n]\frac{\mathcal{B}_t(z)^r}{1-t+t\mathcal{B}_t(z)^{-1}}={tn+r\choose n}\)，取 \(G(z)=\frac{z}{(z+1)^{t}}\) 的复合逆 \(F(z)\) 满足 \(F(z)=\mathcal{B}_t(z)-1\) 。此时 \([z^n](F(z)+1)^r\frac{1+F(z)}{1-(t-1)F(z)}={tn+r\choose n}\)
\[\begin{aligned} &\sum_{x=1}^{\lfloor\frac{R}{B}\rfloor}\sum_{b=0}^{B}\sum_{r=0}^{R-Bx}{b(x+1)+r\choose b}{(B-b)(x+1)+R-Bx-r\choose B-b}\\ \rightarrow\;& \sum_{x=1}^{\lfloor\frac{R}{B}\rfloor}\sum_{b=0}^{B}\sum_{r=0}^{R-Bx}\left([z^b](F(z)+1)^{r}\frac{1+F(z)}{1-(t-1)F(z)}\right)\left([z^{B-b}](F(z)+1)^{R-Bx-r}\frac{1+F(z)}{1-(t-1)F(z)}\right)\\ \rightarrow\;& \sum_{x=1}^{\lfloor\frac{R}{B}\rfloor}(R-Bx+1)\left([z^B](F(z)+1)^{R-Bx}\left(\frac{1+F(z)}{1-(t-1)F(z)}\right)^2\right)\\ \end{aligned} \]后面这一部分，因为知道 \(F(z)\) 的复合逆，考虑用另类拉格朗日反演提取系数：令 \(H(y)=(y+1)^{R-Bx}\left(\frac{1+y}{1-(t-1)y}\right)^2\)，有：
\[\begin{aligned} [][z^B]H(F(z))&=[z^B](z+1)^{R-Bx}\left(\frac{1+z}{1-(t-1)z}\right)^2\frac{1+z-tz}{(z+1)^{t+1}}(z+1)^{t(B+1)}\\ &=[z^B]\frac{(z+1)^{R+B+1}}{1-xz}\\ &=\sum_{i=0}^{B}{R+B+1\choose i}x^{B-i} \end{aligned} \]因此答案为：
\[\begin{aligned} &\sum_{i=0}^{B}{R+B+1\choose i}\sum_{x=1}^{\lfloor\frac{R}{B}\rfloor}(R-Bx+1)x^{B-i}\\ =&\sum_{i=0}^{B}{R+B+1\choose i}\left((R+1)\sum_{x=1}^{\lfloor\frac{R}{B}\rfloor}x^{B-i}-B\sum_{x=1}^{\lfloor\frac{R}{B}\rfloor}x^{B-i+1}\right) \end{aligned} \]问题变成求自然数幂和，对于 \(\sum\limits_{i=1}^{n}i^k\) 求 \([\frac{x^k}{k!}]\frac{e^{(n+1)x}-e^{x}}{e^{x}-1}\) 即可。
提交记录：Submission #175318493 - Codeforces 。
标签：Count,lfloor,frac,Min,题解,sum,choose,aligned,Bx From： https://www.cnblogs.com/qiulyqwq/p/16776839.html