一个二项式式子的推导 兼 CF1716F – Bags with Balls 题解与思路重现

Educational Codeforces Round 133 F – Bags with Balls

题目中存在高次项的和。则我们分别计算有 $p=1,2,\cdots,n$ 个袋子选择奇数号球时的方案。对于选择了奇数号球的袋子，每个有 $\lceil \frac{m}{2} \rceil$ 种选择；偶数的则有 $\lfloor \frac{m}{2} \rfloor$ 种。因此答案为： $$\sum_{p=0}^{n}p^k\dbinom{n}{p}\Big\lceil\frac{m}{2}\Big\rceil^p\Big\lfloor \frac{m}{2} \Big\rfloor^{n-p}$$

由于 $n\leq 10^9$，这式子看起来非常棘手。但我们注意到，有 $k\leq 2000$，这提示我们或许应该转变对答案的贡献方式：从高次幂入手，找到 $\mathrm{O}(\operatorname{poly} k)$ 而非 $\mathrm{O}(n)$ 的算法。

引理

有非负整数 $x, k,n$，则 $$\sum_{p=0}^{n} \dbinom{n}{p}x^pp^k=\sum_{t=1}^{k}n^{\underline{t}}x^t(x+1)^{n-t}\operatorname{S_2}(k,t)$$

其中 $n^{\underline{t}}=\prod_{i=0}^{t-1}n-i$ 表示 $n$ 的 $t$ 次下降幂，$\operatorname{S_2}(k,t)$ 表示第二类斯特林数。

证明

对于 $k=0$，该式子的解是平凡的：$\sum_{p=0}^{n}\dbinom{n}{p}x^p$ 是 $(x+1)^n$ 的展开形式。

对于 $k=1$，我们考虑拆分二项式系数： $$\begin{aligned} & \sum_{p=0}^{n}\dbinom{n}{p}px^p\\ =& \sum_{p=0}^{n}\dfrac{n!}{(n-p)!{\color{blue}p!}}{\color{blue}p}x^p\\ =& \sum_{p=0}^{n}\dfrac{n\cdot (n-1)!}{{\color{red}(n-p)!}{\color{blue}(p-1)!}}x^p\\ =& \sum_{p=0}^{n}n\dfrac{(n-1)!}{{\color{red}[(n-1)-(p-1)]!}(p-1)!}x^p\\ =& \sum_{p=0}^{n}nx\dbinom{n-1}{p-1}x^{p-1} & (1)\\ =& nx(x+1)^{n-1} \end{aligned}$$

对于 $k=2$，我们故技重施： $$\begin{aligned} & \sum_{p=0}^{n}\dbinom{n}{p}p^2x^p\\ =& \sum_{p=0}^{n}\dbinom{n}{p}px^p\cdot p\\ =& \sum_{p=0}^{n}nx\dbinom{n-1}{p-1}x^{p-1}p & \text{（由式(1)得）}\\ =& \sum_{p=0}^{n}{\color{green}nx\dbinom{n-1}{p-1}x^{p-1}}[1+\underline{\color{green}(p-1)}]\\ =& \sum_{p=0}^{n}nx\dbinom{n-1}{p-1}x^{p-1}+{\color{green}n(n-1)x^2\dbinom{n-2}{p-2}x^{p-2}}\\ =& nx(x+1)^{n-1}+n(n-1)x^2(x+1)^{n-2} \end{aligned}$$

情况变得明朗了。可以发现，$k$ 每自增 $1$，也即将原式乘上因数 $p$，我们都会将上一代式子的所有二项式系数再度拆分，并且结果可以表示成 $k$ 个特定二项式系数、$n$ 的下降幂和 $x$ 的高次幂的乘积式之和。同时，更一般地，有$$\dbinom{n-t}{p-t}p={\color{red}t}\dbinom{n-t}{p-t}+{\color{blue}(n-t)}\dbinom{n-t-1}{p-t-1}\quad (2)$$，这就是 $n$ 的下降幂产生的原因。

现在使用数学归纳法：假如对于 $k=k_0$，有 $$\sum_{p=0}^{n} \dbinom{n}{p}x^pp^{k_0}=\sum_{t=1}^{k_0}c_{k_0,t}n^{\underline{t}}x^{t}(x+1)^{n-t}\dbinom{n-t}{p-t}$$成立（$c_{k,t}$ 为给定的 $k,t$ 下该项的正整数系数，目前还没有发现其内在联系），那么对于 $k=k_0+1$，有 $$\begin{aligned} &\sum_{p=0}^{n} \dbinom{n}{p}x^pp^{k_0+1}\\ =& \sum_{t=1}^{k_0}c_{k_0,t}n^{\underline{t}}x^{t}(x+1)^{n-t}\dbinom{n-t}{p-t}\cdot p\\ =& \sum_{t=1}^{k_0}c_{k_0,t}\left[n^{\underline{t}}x^{t}(x+1)^{n-t}\dbinom{n-t}{p-t}{\color{red}t}+\left(n^{\underline{t}}{\color{blue}(n-t)}\right)x^{t+1}(x+1)^{n-t-1}\dbinom{n-(t+1)}{p-(t+1)}\right] &\text{（由式(2)得）}\\ =& \sum_{t=1}^{k_0+1}({\color{red}t}c_{k_0,t}+c_{k_0,t-1})n^{\underline{t}}x^{t}(x+1)^{n-t}\dbinom{n-t}{p-t} \end{aligned}$$

令 $c_{k_0+1,t}=c_{k_0,t}\cdot {\color{red}t}+c_{k_0,t-1}$，则对于 $k=k_0+1$ 也成立。

$c$ 的转移方式，不正是第二类斯特林数的递推式么？！同时具有 $c_{1,1}=1$。故原式成立。$\quad\square$

现在回到本题。我们令 $x=\dfrac{\big\lceil\frac{m}{2}\big\rceil}{\big\lfloor\frac{m}{2}\big\rfloor}$，则答案为 $$\Big\lfloor \frac{m}{2} \Big\rfloor^n\sum_{t=1}^{k}n^{\underline{t}}x^t(x+1)^{n-t}\operatorname{S_2}(k,t)$$

以 $\mathrm{O}({k_{\operatorname{max}}}^2)$ 的时间计算好第二类斯特林数，预处理好逆元和幂次等，单次询问时间复杂度 $\mathrm{O}(k)$。

Submission #167165456