斯特林数
第一类斯特林数
定义
第一类斯特林数 $\begin{bmatrix}n\\ k\end{bmatrix}$ 表示将 $n$ 个不同元素构成 $m$ 个圆排列的数目。
性质一
$$\begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}$$
考虑新加入的数 $n$，要么单独成环，要么插入到其他环中，其中插入方式有 $n-1$ 种。
性质二
$$x^{\overline n}=\sum_{i=0}^n \begin{bmatrix}n\\ i\end{bmatrix}x^i$$
其中 $x^{\overline n}$ 表示上升幂。
考虑归纳证明，有
$$x^{\overline {n+1}}=x^{\overline n}(x+n)=(x+n)\sum_{i=0}^n \begin{bmatrix}n\\ i\end{bmatrix}x^i=\sum_{i=0}^{n+1} \left(\begin{bmatrix}n\\ i-1\end{bmatrix}+n\begin{bmatrix}n\\ i\end{bmatrix}\right)x^i=\sum_{i=0}^{n+1} \begin{bmatrix}n+1\\ i\end{bmatrix}x^i$$
性质三
$$x^{\underline n}=\sum_{i=0}^n \begin{bmatrix}n\\ i\end{bmatrix}(-1)^{n-i}x^i$$
其中 $x^{\underline n}$ 表示下降幂。
考虑归纳证明，有
$$x^{\underline {n+1}}=x^{\underline n}(x-n)=(x-n)\sum_{i=0}^n \begin{bmatrix}n\\ i\end{bmatrix}(-1)^{n-i}x^i=\sum_{i=0}^{n+1} \left(-\begin{bmatrix}n\\ i-1\end{bmatrix}-n\begin{bmatrix}n\\ i\end{bmatrix}\right)(-1)^{n-i}x^i=\sum_{i=0}^{n+1} \begin{bmatrix}n+1\\ i\end{bmatrix}(-1)^{n+1-i}x^i$$
运算
第一类斯特林数$\cdot$行
$$\begin{bmatrix}n\\ i\end{bmatrix}(0\le i\le n)$$
考虑倍增法，假设已知 $x^{\overline n}$，显然可以 $O(n)$ 计算出 $x^{\overline {n+1}}=(x+n)x^{\overline n}$。
接下来考虑求解 $x^{\overline {2n}}$，有 $x^{\overline {2n}}=x^{\overline n}(x+n)^{\overline n}$。设 $x^{\overline n}=\sum_{i=0}^n a_ix^i$，于是有
$$(x+n)^{\overline n}=\sum_{i=0}^n a_i(x+n)^i=\sum_{i=0}^n a_i\sum_{j=0}^i{i\choose j}n^{i-j}x^j=\sum_{j=0}^n x^j\sum_{i=j}^n a_i{i\choose j}n^{i-j}$$
展开组合数，有
$$\sum_{j=0}^n x^j\sum_{i=j}^n a_i{i\choose j}n^{i-j}x^j=\sum_{j=0}^n \frac {x^j}{j!}\sum_{i=j}^n a_ii!\frac {n^{i-j}}{(i-j)!}=\sum_{j=0}^n \frac {x^j}{j!}\sum_{i=0}^{n-j} a_{i+j}(i+j)!\frac {n^i}{i!}$$
设 $b_i=a_ii!,c_i=\cfrac {n^{n-i}}{(n-i)!}$，于是有
$$\sum_{j=0}^n \frac {x^j}{j!}\sum_{i=0}^{n-j} a_{i+j}(i+j)!\frac {n^i}{i!}=\sum_{j=0}^n \frac {x^j}{j!}\sum_{i=0}^{n-j} b_{i+j}c_{n-i}$$
于是可以 $O(n\log n)$ 计算出 $(x+n)^{\overline n}$，最后与 $x^{\overline n}$ 卷积即可 $O(n\log n)$ 计算出 $x^{\overline {2n}}$。
总时间复杂度 $T(n)=T(\frac n2)+O(n\log n)$，于是 $T(n)=O(n\log n)$。
