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

· · 个人记录

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} **** ### Lagrange 反演收尾 现在我们知道答案为 $$\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)$ 处理。