已完成嘟嘟嘟大学习

斯特林数计算
门
总之我们可以理解斯特林数为

n

人分

k

组的方案。
考虑容斥，我们钦定至少有

m

个组为

1

，有：

ans=\sum_{m=0}^n (-1)^m \binom{n}{m} \sum_{k \ge 0}S_{n-m,k}\\ = \sum_{m=0}^n (-1)^{n-m} \binom{n}{m} \sum_{k \ge 0}S_{m,k}

后面的sum等于其他任选的方案。
同时，上下两个式子显然是对称的。

根据oi wiki,我们可以知道其有通项公式

S_{n,m}=\sum_{i=0}^m \frac{(-1)^{m-i}i^n}{i!(m-i)!}

，那么整个式子变为了：

\sum_{m=0}^n (-1)^{n-m} \binom{n}{m} \sum_{k \ge 0}\sum_{i=0}^k \frac{(-1)^{k-i}i^m}{i!(k-i!)}\\ =\sum_{m=0}^n (-1)^{n-m} \binom{n}{m} \sum_{k \ge 0}\frac{1}{k}\sum_{i=0}^k \frac{k!(-1)^{k-i}i^m}{i!(k-i)!}\\ =\sum_{m=0}^n (-1)^{n-m} \binom{n}{m} \sum_{k \ge 0}\frac{1}{k}\sum_{i=0}^k \frac{k!(-1)^{k-i}i^m}{i!(k-i)!}\\ =\sum_{m=0}^n (-1)^{n-m} \binom{n}{m} \sum_{k \ge 0}\frac{1}{k}\sum_{i=0}^k \binom{k}{i}(-1)^{k-i}i^m\\ \text{交换求和顺序}\\ = \sum_{k \ge 0}\frac{1}{k}\sum_{i=0}^k \binom{k}{i}(-1)^{k-i}\sum_{m=0}^n (-1)^{n-m} \binom{n}{m} i^m

此时，最后那一坨看起来很容斥原理，思考其组合意义，可以发现其相当于钦定i个为1，其他在

1-j

选的方案，可以转为

(i-1)^n

：

\sum_{k \ge 0}\frac{1}{k}\sum_{i=0}^k \binom{k}{i}(-1)^{k-i}(i-1)^n

这个式子与

i

与

k-i

有关，分别设为

x,y

那么有：

\sum_{x\ge 0}\frac{1}{(x+y)!}\sum_{y\ge 0}^{x+y}\binom{x+y}{x}(-1)^y(x-1)^n\\ = \sum_{x\ge 0}\sum_{y\ge 0}^{x+y}\frac{(-1)^y(x-1)^n}{x!y!}\\ =\sum_{x+y\le n}\frac{(-1)^y(x-1)^n}{x!y!}

其余几项好解决，我们如何线性预处理

x^n

呢？
实际上很简单，我们用欧拉筛维护就行了，很容易O(n)。

文章操作