第一类斯特林数
含义
\(S(i,j)\) 表示 \(i\) 个不同元素，分成 \(j\) 个圆，排列的方案数
那么 \(S(0,0)=1,S(i,0)=1\) 显然有\[S(i,j)=S(i-1,j-1)+(i-1)S(i-1,j)\]结论
\[\sum_{k=0}^{n}S(n,k)=n!\]
证明
一个排列对应一个置换
把这个置换中的上下对应位置连边，可以得到许多的环 由于排列和置换是一一对应的，所以我们要求排列的个数，就是求用n个元素组成环的方案数，所以我们枚举环的个数它的生成函数
\[x^{\overline{n}}=x(x+1)(x+2)...(x+n-1)=\sum_{k=0}^{n}S(n,k)x^k\]
\[x^{\underline{n}}=x(x-1)(x-2)...(x-n+1)=\sum_{k=0}^{n}(-1)^{n-k}S(n,k)x^k\]求法
可以直接 \(nlog^2n\) 分治 \(FFT\)
或者还有一个 \(nlogn\) 倍增的求法 设 \(F_n(x)=\prod_{i=0}^{n-1}(x+i)\) 那么 \(F_{2n}(x)=F_n(x)F_n(x+n)\) 考虑利用 \(F_n(x)\) 推出 \(F_n(x+n)\) 设 \(F_n(x)=\sum_{i=0}^{n}a_ix^i\) 那么\[F_n(x+n)=\sum_{i=0}^{n}a_i\sum_{j=0}^{i}\binom{i}{j}x^jn^{i-j}=\sum_{i=0}^{n-1}x^i\sum_{j=i}^{n-1}\binom{j}{i}n^{j-i}a_j\] 而\[\sum_{j=i}^{n-1}\binom{j}{i}n^{j-i}a_j=\frac{1}{i!}\sum_{j=i}^{n-1}j!a_j\frac{n^{j-i}}{(j-i)!}\] 所以可以反转之后 \(FFT\)# includeusing namespace std;typedef long long ll;const int maxn(1 << 18);const int mod(998244353);inline void Inc(int &x, int y) { x = x + y >= mod ? x + y - mod : x + y;}inline int Pow(ll x, int y) { register ll ret = 1; for (; y; y >>= 1, x = x * x % mod) if (y & 1) ret = ret * x % mod; return ret;}int f[maxn], w[2][maxn], a[maxn], b[maxn], c[maxn], l, r[maxn], len;inline void Init(int n) { register int i, x, y; for (l = 0, len = 1; len < n; len <<= 1) ++l; for (i = 0; i < len; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1)); x = Pow(3, (mod - 1) / len), y = Pow(x, mod - 2), w[0][0] = w[1][0] = 1; for (i = 1; i < len; ++i) w[0][i] = (ll)w[0][i - 1] * x % mod, w[1][i] = (ll)w[1][i - 1] * y % mod; for (i = 0; i < len; ++i) c[i] = a[i] = b[i] = 0;}inline void DFT(int *p, int opt) { register int i, j, t, k, x, y, wn; for (i = 0; i < len; ++i) if (r[i] < i) swap(p[i], p[r[i]]); for (i = 1; i < len; i <<= 1) for (t = i << 1, j = 0; j < len; j += t) for (k = 0; k < i; ++k) { wn = w[opt == -1][len / t * k]; x = p[k + j], y = (ll)wn * p[i + j + k] % mod; p[k + j] = x + y >= mod ? x + y - mod : x + y; p[i + j + k] = x - y < 0 ? x - y + mod : x - y; } if (opt == -1) for (wn = Pow(len, mod - 2), i = 0; i < len; ++i) p[i] = (ll)p[i] * wn % mod;}int n, inv[maxn], fac[maxn], pw[maxn];void Solve(int x) { if (x == 1) return f[1] = 1, void(); register int i, cnt; if (x & 1) for (Solve(x - 1), i = x; i; --i) f[i] = ((ll)(x - 1) * f[i] + f[i - 1]) % mod; else { Solve(x >> 1), cnt = x >> 1, Init(x + 1); for (i = pw[0] = 1; i <= cnt; ++i) pw[i] = (ll)pw[i - 1] * cnt % mod; for (i = 0; i <= cnt; ++i) a[i] = (ll)fac[i] * f[i] % mod; for (i = 0; i <= cnt; ++i) b[i] = (ll)pw[i] * inv[i] % mod; reverse(b, b + cnt + 1), DFT(a, 1), DFT(b, 1); for (i = 0; i < len; ++i) a[i] = (ll)a[i] * b[i] % mod; for (DFT(a, -1), i = 0; i <= cnt; ++i) c[i] = (ll)a[cnt + i] * inv[i] % mod; for (DFT(f, 1), DFT(c, 1), i = 0; i < len; ++i) f[i] = (ll)f[i] * c[i] % mod; for (DFT(f, -1), i = x + 1; i < len; ++i) f[i] = 0; }}int main() { register int i, c = 1, a, b, m; scanf("%d%d%d", &n, &a, &b); if (a + b - 2 > n - 1 || !a || !b) return puts("0"), 0; if (n == 1) return puts(a == b && a == 1 ? "1" : "0"); fac[0] = fac[1] = inv[0] = inv[1] = 1, m = a + b - 2; for (i = 2; i <= n; ++i) inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod; for (i = 1; i < a; ++i) c = (ll)c * (m - i + 1) % mod * inv[i] % mod; for (i = 2; i <= n; ++i) inv[i] = (ll)inv[i] * inv[i - 1] % mod, fac[i] = (ll)fac[i - 1] * i % mod; Solve(n - 1), c = (ll)c * f[a + b - 2] % mod, printf("%d\n", c); return 0;}
第二类斯特林数
含义
\(n\)个有区别的球放在\(m\)个相同的盒子内，要求盒子不为空的方案数
实际上也就是把数\(n\)拆成\(m\)个正整数和的方案数 记作\(S(n, m)\)性质
- \(S(n, 0)=S(0, n)=0\)，其中\(n \in N\)
- \(S(n, k)=0\)，其中\(k>n>=1\)
- \(S(n, n)=S(n, 1)=1\)，其中\(n>=1\)
等等......
求法
递推
\[S(n, m) = S(n - 1, m - 1) + S(n - 1, m) * m\]，其中\(n>1，m>=1\)
解释：新开一盒子或者在原有盒子中选一个公式
\[S(n, m)=\frac{1}{m!}\sum_{k=0}^{m}(-1)^kC(m, k)(m-k)^n\]
证明
先考虑\(n\)个不同的球放在\(m\)个不同的盒子内没有无空盒限制的方案数
那么显然就是\(m^n\) 考虑容斥原理 总的 \(-\) 有大于等于一个空盒的方案 \(+\) 有大于等于两个个空盒的方案 \(-\)有大于等于三个空盒的方案...... 写出来就是\[S(n, m)=\sum_{k=0}^{m}(-1)^kC(m, k)(m-k)^n\] 因为我们认为盒子有区别\(C(m, k)\)就是把那\(k\)个空盒子选出来 其他的随便放现在求出了\(n\)个不同的球放在\(m\)个不同的盒子内有无空盒限制的方案数
然而要求的是盒子无区别的 还要除以一个\(\frac{1}{m!}\) 就得到了那个公式其他的一些东西
\[S(n, m)=\frac{1}{m!}\sum_{k=0}^{m}(-1)^kC(m, k)(m-k)^n\]
假设\(n\)固定，那么预处理出\(C(m, k)\)就可以直接多项式卷积求出来所有的\(S(n,m)\)考虑换一种形式
\[S(n, m)=\frac{1}{m!}\sum_{k=0}^{m}(-1)^kC(m, k)(m-k)^n\]\[=\frac{1}{m!}\sum_{k=0}^{m}(-1)^k\frac{m!}{k!(m-k)!}(m-k)^n\]\[=\sum_{k=0}^{m}\frac{(-1)^k}{k!}\frac{(m-k)^n}{(m-k)!}\]这样就可以不用预处理组合数直接\(FFT\)求了
推论
- 因为\(S(m, m)=1\)，所以\[m!=\sum_{k=0}^{m}(-1)^kC(m, k)(m-k)^m\]
- \(m^n\)类似表示，即用第二类斯特林数表示\(n\)个不同的球放在\(m\)个不同的盒子内没有无空盒限制的方案数 这次枚举不是空的的盒子\[m^n=\sum_{k=0}^{m}S(n, k)k!C(m, k)\]
两个之间的关系
反转公式
\[\begin{cases}\sum_{k=m}^n(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}\begin{Bmatrix}k\\m\end{Bmatrix}=[n=m]\\\sum_{k=m}^n(-1)^{n-k}\begin{bmatrix}k\\m\end{bmatrix}\begin{Bmatrix}n\\k\end{Bmatrix}=[n=m]\end{cases}\]第一类Stirling数幂与下降幂的关系
\[x^{\underline k}=\sum_{i=0}^k(-1)^{k-i}\begin{bmatrix} k\\i \end{bmatrix}x^i\]第二类Stirling数幂与下降幂的关系
\[x^{k}=\sum_{i=0}^k\begin{Bmatrix} k\\i \end{Bmatrix}x^{\underline i}\]