一个奇妙的斯特林数推导

~~大概没啥人来看这个咸鱼的博客了吧。~~ 虽然一直没更新，但时不时还会回来看。有些偶然的感想，或者被以前自己高妙的想法震惊到的，还会放在这里。因为很长时间没搞OI了，数学的内容应该会多一点。

给定 $n, m, k$ ，求：

\sum_{i = 0}^{m} (\binom{m}{i}) (\binom{n - m + 2 i}{k})

$n, m \leq 10^{9}, k \leq 10^{3}$

多组询问，组数 $\leq 100$

\sum_{i = 0}^{m} (\binom{m}{i}) (\binom{n - m + 2 i}{k})

= \frac{1}{k!} \sum_{i = 0}^{m} (\binom{m}{i}) (n - m + 2 i)^{\underset{―}{k}}

= \frac{1}{k!} \sum_{i = 0}^{m} (\binom{m}{i}) (\sum_{j = 0}^{k} (\binom{k}{j}) (n - m)^{\underset{―}{k - j}} (2 i)^{\underset{―}{j}})

= \frac{1}{k!} \sum_{j = 0}^{k} (\binom{k}{j}) (n - m)^{\underset{―}{k - j}} (\sum_{i = 0}^{m} (\binom{m}{i}) (2 i)^{\underset{―}{j}})

考虑如何计算 $\sum_{i = 0}^{m} (\binom{m}{i}) (2 i)^{\underset{―}{j}}$ ：

= \sum_{i = 0}^{m} (\binom{m}{i}) (\sum_{p = 0}^{j} (- 1)^{j - p} [\begin{matrix} j \\ p \end{matrix}] (2 i)^{p})

= \sum_{i = 0}^{m} (\binom{m}{i}) (\sum_{p = 0}^{j} (- 1)^{j - p} [\begin{matrix} j \\ p \end{matrix}] 2^{p} i^{p})

= \sum_{p = 0}^{j} (- 1)^{j - p} [\begin{matrix} j \\ p \end{matrix}] 2^{p} (\sum_{i = 0}^{m} (\binom{m}{i}) i^{p})

= \sum_{p = 0}^{j} (- 1)^{j - p} [\begin{matrix} j \\ p \end{matrix}] 2^{p} (\sum_{i = 0}^{m} (\binom{m}{i}) (\sum_{o = 0}^{p} {\begin{matrix} p \\ o \end{matrix}} o! (\binom{i}{o})))

= \sum_{p = 0}^{j} (- 1)^{j - p} [\begin{matrix} j \\ p \end{matrix}] 2^{p} (\sum_{o = 0}^{p} {\begin{matrix} p \\ o \end{matrix}} o! (\sum_{i = 0}^{m} (\binom{m}{i}) (\binom{i}{o})))

= \sum_{p = 0}^{j} (- 1)^{j - p} [\begin{matrix} j \\ p \end{matrix}] 2^{p} (\sum_{o = 0}^{p} {\begin{matrix} p \\ o \end{matrix}} o! (\binom{m}{o}) 2^{m - o})

= \sum_{p = 0}^{j} (- 1)^{j - p} [\begin{matrix} j \\ p \end{matrix}] 2^{p} (\sum_{o = 0}^{p} {\begin{matrix} p \\ o \end{matrix}} m^{\underset{―}{o}} 2^{m - o})

直接计算是 $O (k^{3})$ 的，但考虑 $j, o$ 之间的贡献：

\sum_{p = o}^{j} (- 1)^{j - p} [\begin{matrix} j \\ p \end{matrix}] 2^{p} {\begin{matrix} p \\ o \end{matrix}}

是常数，可以用 $O (k^{3})$ 预处理，就可以做到 $O (k^{2})$ 回答询问。

$P . S .$ 听说这题有纯组合数做法，有没有人教教我啊

2020.12.28 至少，我们都曾经闪耀过。

2021.10.11

突然回看博客，会推组合数做法了。

太弱小了没有力量。

$(\binom{n - m + 2 i}{k})$ 实际上是 $i$ 的 $k$ 次多项式，将其拆分为若干 $(\binom{i}{k})$ 的线性叠加，分别求解题中的和式。

\sum_{i = 0}^{m} (\binom{m}{i}) (\binom{i}{k}) = (\binom{m}{k}) 2^{m - k}

可以用组合数公式证明上面的式子，但组合意义更快：式子就是统计 $m$ 个元素先选任意个再选 $k$ 个的方案，那么首先枚举最后选出的 $k$ 个，剩下的是否出现在第一次选择中随意。