斯特林数

第一类斯特林数：\([^n_k]\)：把 \(n\) 个数放入 \(k\) 个环中，本质不同的方案数。（要求每个环非空，环之间不区分，环可旋转）

\([^n_k]=(n-1)[^{n-1}_k] + [^{n-1}_{k-1}]\)。

\(\displaystyle\sum_{k=0}^n [^n_k]=n!\)。

第二类斯特林数：\(\{^n_k\}\)：把 \(n\) 个数放入 \(k\) 个盒中，本质不同的方案数。（非空，盒之间不区分）

\(\{^n_k\}=k\{^{n-1}_{k}\}+\{^{n-1}_{k-1}\}\)。

\(\{^n_k\}=\dfrac{1}{k!}\displaystyle\sum_{t=0}^k(-1)^t(^k_t)(k-t)^n\)

可以用斯特林数来让普通次幂和 上、下阶乘幂 转化。

※ 普通转下：\(x^n=\displaystyle\sum_{k=1}^n\{^n_k\}\,\cdot x^{\underline{k}}\)

普通转上：\(x^n=\displaystyle\sum_{k=1}^n(-1)^{n-k}\{^n_k\}\,\cdot x^{\overline{k}}\)

上转普通：\(x^{\overline{n}}=\displaystyle\sum_{k=1}^n[^n_k]x^k\)。

下转普通：\(x^{\underline{n}}=\displaystyle\sum_{k=1}^n(-1)^{n-k}[^n_k]x^k\)。

例题：CF932E

\(\displaystyle\sum(^n_i)i^k=\sum_{i=1}^n(^n_i)\sum_{j=1}^k\{^k_j\}i^{\underline{j}}=\sum_{i=1}^n(^n_i)\sum_{j=1}^{\min(k,i)}\{^k_j\}(^i_j)\cdot j!=\sum_{j=1}^{\min(k,n)}j!\cdot \{^k_j\}\sum_{i=j}^n(^n_i)(^i_j).\)

这里用一下这个：\((^n_i)(^i_j)=(^n_j)(^{n-j}_{i-j})\).

\(\displaystyle...=\sum_{j=1}^{\min(k,n)}j!(^n_j)\{^k_j\}\sum_{i=j}^n(^{n-j}_{i-j})=\sum_{j=1}^{\min(k,n)}j!(^n_j)\{^k_j\}\cdot 2^{n-j}\)

\(\min(k,n)\le 5000\)，就相当于 \(5000\) 个数求和。

\(j!,(^n_j),2^{n-j}\) 都可以预处理出来。（注意这里 \(j\) 的范围很小）

而 \(\{^k_j\}\) 第二类斯特林数我们直接用递推公式，\(O(k^2)\) 预处理。

斯特林

问：\(1\sim n\) 的置换，有偶数个环 计数。

即求 \(\displaystyle\sum_{k\equiv 0\pmod 2}[^n_k]\)。

解：\(x^{\overline{n}}=\sum_{k=1}^n[^n_k]x^k\)。

将 \(x\) 代入 \(1,-1\) 可以消掉奇数次幂项。