广义二项级数还是太有用了

QOJ 3084：XXI Open Cup named after E.V. Pankratiev. Grand Prix of Tokyo C: Count Min Ratio

以此题为例，说明广义二项级数的一点应用。官方题解使用了组合意义，这里就用代数推导来做。

特别感谢 joke3579，本题的主要推导都是他做的。
（要不然我都忘了有广义二项级数这东西了！）

首先我们容易列出一个暴力计算的式子：

\text{ans}=\sum_{i=0}^R \sum_{j=0}^B\binom{i+j}{i}\binom{R+B-i-j}{R-i}\min\left( \left \lfloor \frac{i}{j} \right \rfloor, \left \lfloor \frac{R-i}{B-j}\right \rfloor \right)

先不要急着把

\min

分段，不妨枚举

d \leq \min

：

\begin{aligned}\text{ans}&=\sum_{i=0}^R \sum_{j=0}^B\binom{i+j}{i}\binom{R+B-i-j}{R-i} \sum_{d\geq 1} [dj \leq i][(R-i)\geq (B-j)d] \\ &=\sum_{d \geq 1} \sum_{j=0}^B \sum_{i=jd}^{R-d(B-j)}\binom{i+j}{i}\binom{R+B-i-j}{R-i} \\&=\sum_{d \geq 1}\sum_{j=0}^B \sum_{i=0}^{R-dB}\binom{i+j(d+1)}{j}\binom{R+B-(i+dj)-j}{B-j} \\ &= \sum_{d \geq 1}\sum_{j=0}^B \sum_{i=0}^{R-dB}\binom{i+j(d+1)}{j} \binom{(R-dB-i)+(d+1)(B-j)}{B-j}\end{aligned}

广义二项级数是一类常数项为

1

的形式幂级数，定义如下：

\mathcal B_t(z)=1+z\mathcal B_t(z)^t

它有这样一个重要性质（证明参考此文）：

[z^k]\frac{\mathcal B_t(z)^r}{1-t+t\mathcal B_t(z)^{-1}}=\binom{tk+r}{k}

结合此性质，答案可以表示为

\sum_{d \geq 1}\sum_{j=0}^B \sum_{i=0}^{R-dB}\left( [z^j] \frac{\mathcal B_{d+1}(z)^i}{1-(d+1)+(d+1)\mathcal B_{d+1}(z)^{-1}}\right)\left( [z^{B-j}] \frac{\mathcal B_{d+1}(z)^{R-dB-i}}{1-(d+1)+(d+1)\mathcal B_{d+1}(z)^{-1}}\right)

=\sum_{d \geq 1}[z^B]\sum_{i=0}^{R-dB} \frac{\mathcal B_{d+1}(z)^{R-dB}}{(1-(d+1)+(d+1)\mathcal B_{d+1}(z)^{-1})^2}

i

被神奇地消掉了，让我们沿此方向继续推导。

现在我们知道答案为

\text{ans}=[z^B] \sum_{d=1}^{\lfloor R/B \rfloor} \frac{(R-dB+1)\mathcal B_{d+1}(z)^{R-dB}}{(1-(d+1)+(d+1)\mathcal B_{d+1}(z)^{-1})^2}

使用另类 Lagrange 反演大力做一下，注意

\mathcal B_t(z)

的常数项为

1

，套公式前需要将其常数项去掉：

\begin{aligned}\text{ans} &=[z^B] \sum_{d=1}^{\lfloor R/B \rfloor} \left(\frac{(R-dB+1)(z+1)^{R-dB}}{(1-(d+1)+(d+1)\mathcal (z+1)^{-1})^2}\circ (\mathcal B_{d+1}(z)-1) \right) \\ &=[z^B] \sum_{d=1}^{\lfloor R/B \rfloor} \left(\frac{(R-dB+1)(z+1)^{R-dB}}{(1-(d+1)+(d+1)\mathcal (z+1)^{-1})^2}\frac{1-dz}{(1+z)^{d+2}}(1+z)^{(d+1)(B+1)} \right)\end{aligned}

然后就是一通展开化简，虽然麻烦但并不难：

\text{ans} =[z^B] (1+z)^{R+B+1} \sum_{d=1}^{\lfloor R/B \rfloor} \frac{R-dB+1}{1-dz}

最后和式的展开其实也容易计算：

\sum_{d=1}^{\lfloor R/B \rfloor} \frac{R-dB+1}{1-dz}=\sum_{i=0}^\infty z^i\sum_{d=1}^{\lfloor R/B \rfloor}(R+1)d^i-B d^{i+1}

这就是自然数幂和，可以直接

\Theta(B \log B)

处理。

文章操作