有一回对我说道，“你读过书么？”我略略点一点头。他说，“读过书，……我便考你一考。组合数学里的斯特林数，怎样说的？”我想，AKIOI的人，我也配答么？便回过脸去，不再理会。田乙己等了许久，很恳切的说道，“不会罢？……我教给你，记着！这些数应该记着。将来做OIer的时候，省选要用。”我暗想我和省选的等级还很远呢，而且我们考纲里也没有斯特林数；又好笑，又不耐烦，懒懒的答他道，“谁要你教，不是将n个元素划分成m个集合或环排列的方案数嘛？”田乙己显出极高兴的样子，将两个指头的长指甲敲着鼠标，点头说，“对呀对呀！……斯特林数有四样求法，你知道么？”我愈不耐烦了，努着嘴走远。田乙己刚打开typora，想在电脑上打公式，见我毫不热心，便又叹一口气，显出极惋惜的样子。
第一类斯特林数·行
众所周知：
\[x^{\overline{n}}=\sum_{i=0}^n \begin{bmatrix}n\\ i\end{bmatrix} x^i \]求上升幂考虑倍增，\(x^{\overline{2n}}=x^{\overline{n}}\cdot (x+n)^{\overline{n}}\)
问题变为已知 \(f(x)\)，如何求 \(f(x+c)\)，考虑硬带
\[f(x+c)=\sum_{i=0}^n f_i (x+c)^i=\sum_{i=0}^n f_i \sum_{j=0}^i \binom{i}{j}x^j c^{i-j} \]\[=\sum_{j=0}^n x^j \sum_{i=j}^n f_i \binom{i}{j} c^{i-j} \]\[=\sum_{j=0}^n {x^j \over j!} \sum_{i=j}^n f_i i! \cdot {c^{i-j}\over (i-j)!} \]发现后面是减法卷积，reverse一遍做乘法再reverse回来就行，问题解决。
inline poly trans(poly a, int c) {
poly p;
for (register int i = 0; i < a.size(); ++i) {
a[i] = (1ll * a[i] * fac[i]) % mod;
p.push_back((1ll * power(c, i) * ifac[i]) % mod);
} int n = a.size(); reverse(a.begin(), a.end()); a = mul(a, p);
a.resize(n); reverse(a.begin(), a.end());
for (register int i = 0; i < a.size(); ++i)
a[i] = (1ll * a[i] * ifac[i]) % mod;
return a;
}
inline poly stir1R(int n) {
poly t, y; int k = n, tt = 1;
t.push_back(1); y.push_back(0); y.push_back(1);
int sum = 0;
while (k) {
if (k & 1) {
sum += tt;
t = mul(trans(t, tt), y);
t.resize(sum + 1);
} y = mul(trans(y, tt), y);
tt <<= 1; //y len
y.resize(tt + 1);
k >>= 1;
} return t;
}
第二类斯特林数·行
众所周知：
\[m^n = \sum_{i=0}^n \binom{m}{i}\begin{Bmatrix} n \\i \end{Bmatrix}i! \]考虑组合意义，\(n\) 个球放入 \(m\) 个盒子的方案数，相当于枚举 \(i\) 个盒子非空，将球划分到 \(i\) 个盒子中，再乘上全排列。
二项式反演：
\[\begin{Bmatrix} n \\m \end{Bmatrix}m!=\sum_{i=0}^m (-1)^{m-i} \binom{m}{i} i^n \]\[\begin{Bmatrix} n \\m \end{Bmatrix}=\sum_{i=0}^m ({(-1)^i \over i!})\cdot {(m-i)^n \over (m-i)!} \]做卷积即可。
inline poly stir2R(int n) {
poly a, b;
for (int i = 0; i <= n; ++i) {
a.push_back((1ll * power(i, n) * ifac[i]) % mod);
b.push_back(ifac[i]); if (i & 1) b[i] = -b[i] + mod;
if (b[i] >= mod) b[i] -= mod;
} return mul(a, b);
}
第一类斯特林数·列
考虑 \(k=1\) 时，就是环排列，构造生成函数:
\[S_1(x)=\sum_{i} \begin{bmatrix}n\\ 1\end{bmatrix} {x^i\over i!}=\sum_{i}{x^i\over i} \]所以：
\[k!S_k(x)=(S_1(x))^k \]快速幂即可。
inline poly stir1L(int n, int k) {
poly a; a.resize(n + 1);
for (int i = 0; i <= n; ++i)
a[i] = inver[i];
a = polypow(a, k, k);
for (int i = 0; i <= n; ++i)
a[i] = mul(fac[i], mul(a[i], ifac[k]));
return a;
}
第二类斯特林数·列
奇妙方法。
考虑将相同的集合换成不同的盒子，答案会多乘以 \(k!\)，设此时单个盒子的 EGF 为G，则：
\[G(x)=\sum_{i\ge 1} {x^i \over i!}=e^x-1 \]所以 \(k\) 个盒子的 EGF 就是 \((e^x-1)^k\)
\[\begin{bmatrix}n\\ k\end{bmatrix}= {n!\over k!}[x^n](e^x-1)^k \]inline poly stir2L(int n, int k) {
poly a; a.resize(n + 1);
for (int i = 1; i <= n; ++i) a[i] = ifac[i];
a = polypow(a, k, k);
for (int i = 0; i <= n; ++i)
a[i] = mul(fac[i], mul(ifac[k], a[i]));
return a;
}