已完成嘟嘟嘟大学习
TLE_AK
·
·
算法·理论
斯特林数计算
门
总之我们可以理解斯特林数为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)。