「联合省选 2020 A」组合数问题 题解

前言

这题算是我斯特林数的入门题，顺便安利大佬的博客，我是从这篇博客中学的斯特林数。

前置知识：

• 二项式定理：

  $(a+b)^n=\sum_{i=0}^n{\dbinom ni a^ib^{n-i}}\tag1$

• 斯特林数相关知识：

  • 斯特林数定义：

    • 第一类斯特林数： 第一类斯特林数 $\begin{bmatrix}n\\m\end{bmatrix}$ 表示将 $n$ 个不同元素划分为 $m$ 个轮换的方案数。

    • 第二类斯特林数： 第二类斯特林数 $\begin{Bmatrix}n\\m\end{Bmatrix}$ 表示把 $n$ 个不同小球放入 $m$ 个相同盒子，盒子不能空的方案数。

    • 相关递推式：

      $\begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\m\end{bmatrix}\tag2$

      $\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\m\end{Bmatrix}\tag3$

• 上升下降幂相关知识：

  • 定义：$a^{\bar{b}}=\prod_{i=0}^{b-1}{(a+i)}$ 称为上升幂，$a^{\underline{b}}=\prod_{i=0}^{b-1}{(a-i)}$ 称为下降幂，而 $a^b$ 称为普通幂。

  • 普通幂与上升下降幂之间的转换：

    $x^n=\sum_{k=0}^n{\begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline{k}}}\tag4$

    $x^{\underline{n}}=\sum_{k=0}^n{(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}x^k}\tag5$

    $x^n=\sum_{k=0}^n{(-1)^{n-k}\begin{Bmatrix}n\\k\end{Bmatrix}x^{\bar{k}}}\tag6$

    $x^{\bar{k}}=\sum_{k=0}^n{\begin{bmatrix}n\\k\end{bmatrix}x^k}\tag7$

  • 下降幂与组合数之间的关系：

    $\dbinom nm m^{\underline{k}}=\dbinom {n-k}{m-k}n^{\underline{k}}\tag 8$

题解

$\begin{aligned}\sum_{k=0}^n f(k) \times x^k \times \dbinom n k&=\sum_{k=0}^n{\left(\sum_{i=0}^m{a_ik^i} \right)x^k\dbinom nk}\texttt{$\big($由定义$\big)$}\\ & = \sum_{k=0}^n{\left(\sum_{i=0}^m{a_i\sum_{j=0}^i{\begin{Bmatrix}i\\j\end{Bmatrix}k^{\underline{j}}}} \right) x^k\dbinom nk}\texttt{$\big($由$\,(4)\big)$}\\&=\sum_{k=0}^n{\left(\sum_{j=0}^m{k^{\underline{j}}\sum_{i=0}^j{a_i\begin{Bmatrix}i\\j\end{Bmatrix}}} \right)x^k\dbinom nk}\texttt{$\big($交换求和顺序$\big)$}\\&=\sum_{j=0}^m{q_j}\sum_{k=j}^n{x^kk^{\underline{j}}\dbinom nk}\texttt{$\bigg($记$\,q_j=\sum_{i=0}^j{a_i}\begin{Bmatrix}i\\j\end{Bmatrix}\bigg)$}\\&=\sum_{j=0}^m{q_j\sum_{k=j}^n{x^k}n^{\underline{j}}\dbinom {n-j}{k-j}}\texttt{$\big($由$\,(8)\big)$}\\&=\sum_{j=0}^m{q_jx^{j}n^{\underline{j}}\sum_{k=0}^{n-j}{x^k\dbinom {n-j}{k}}}\texttt{$\big($提取公因式$\big)$}\\&=\sum_{j=0}^m{q_jx^jn^{\underline{j}}(x+1)^{n-j}}\texttt{$\big($由$(1)\big)$} \end{aligned}$

显然 $\{q_j\}$ 可以在 $O(m^2)$ 的时间内预处理出来，剩下的直接套上面的式子就可以 $O(m\log n)$ 计算。

时间复杂度为 $O(m^2+m\log n)$，空间复杂度为 $O(m^2)$。