题目
题意
求\(\left\{\begin{matrix}n\\i\end{matrix}\right\},i=0,1,\dots,n\)
其中\(\left\{\begin{matrix}n\\i\end{matrix}\right\}\)为第二类斯特林数，组合意义为将\(n\)个不同元素划入\(i\)个相同集合（所有集合非空）的方案数，有递推式\(\left\{\begin{matrix}n\\m\end{matrix}\right\}=\left\{\begin{matrix}n-1\\m-1\end{matrix}\right\}+\left\{\begin{matrix}n-1\\m\end{matrix}\right\}\times m\)
推导
先说结论：
\[\boxed{\left\{\begin{matrix}n\\m\end{matrix}\right\}=\sum\limits^n_{i=0}\frac{(-1)^i}{i!}\times\frac{(m-i)^n}{(m-i)!}}\]
证明如下：
先将\(m\)个集合标号，钦定其中\(i\)个集合为空，\(n\)个元素任意安排到剩余的\(m-i\)个集合（可以为空）的方案数为\(\binom{m}{i}\times(m-i)^n\)，由于原先的集合是无标号的，所以还要除以\(m!\)
于是就有：\(m\)个集合中至少有\(i\)个为空的方案数为\(\frac{1}{m!}\times\binom{m}{i}\times(m-i)^n\)
考虑对其进行容斥，即可得所有集合非空的方案数：
\[\begin{aligned}\left\{\begin{matrix}n\\m\end{matrix}\right\}&=\sum\limits^m_{i=0}(-1)^i\times\frac{1}{m!}\times\binom{m}{i}\times(m-i)^n\\&=\sum\limits^m_{i=0}(-1)^i\times\frac{1}{m!}\times\frac{m!}{i!\times(m-i)!}\times(m-i)^n\\&=\sum\limits^m_{i=0}\frac{(-1)^i}{i!}\times\frac{(m-i)^n}{(m-i)!}\end{aligned}\]
发现是一个卷积的形式，将\(\sum\limits^n_{i=0}\frac{(-1)^i}{i!}x^i\)和\(\sum\limits^n_{i=0}\frac{i^n}{i!}x^i\)做卷积，\(i\)次项的系数即为\(\left\{\begin{matrix}n\\i\end{matrix}\right\}\)
时间复杂度\(O(n\log_2n)\)
代码
大约就是一个NTT板子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| class Polynomial {
public:
int *a;
Polynomial() {
a = new int[N];
memset(a, 0, sizeof(int) * N);
}
void NTT(int, bool);
};
int pow(int a, int b, int m) {
int ans = 1, now = a;
while (b) {
if (b & 1) {
ans = ans * 1ll * now % m;
}
now = now * 1ll * now % m;
b >>= 1;
}
return ans;
}
void Polynomial::NTT(int lim, bool opt) {
if (opt) {
std::reverse(a + 1, a + lim);
}
for (int i = 0; i < lim; ++i) {
if (i < r[i]) {
std::swap(a[i], a[r[i]]);
}
}
for (int l = 1; l < lim; l <<= 1) {
int gw = pow(g, (Mod - 1) / (l << 1), Mod);
for (int i = 0; i < lim; i += (l << 1)) {
for (int j = 0, gn = 1; j < l; ++j, gn = gn * 1ll * gw % Mod) {
int x = a[i | j], y = a[i | j | l] * 1ll * gn % Mod;
a[i | j] = (x + y) % Mod;
a[i | j | l] = (x - y + Mod) % Mod;
}
}
}
if (opt) {
int iv = pow(lim, Mod - 2, Mod);
for (int i = 0; i < lim; ++i) {
a[i] = a[i] * 1ll * iv % Mod;
}
}
}
void solve(int n) {
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * 1ll * i % Mod;
}
ifac[n] = pow(fac[n], Mod - 2, Mod);
for (int i = n - 1; i >= 0; --i) {
ifac[i] = ifac[i + 1] * 1ll * (i + 1) % Mod;
}
Polynomial f, g;
f.a[0] = 1, g.a[0] = 0;
for (int i = 1; i <= n; ++i) {
f.a[i] = (i & 1) ? (Mod - ifac[i]) : ifac[i];
g.a[i] = pow(i, n, Mod) * 1ll * ifac[i] % Mod;
}
int lim = 1;
while (lim <= (n << 1)) {
lim <<= 1;
}
for (int i = 0; i < lim; ++i) {
r[i] = (r[i >> 1] >> 1) | ((i & 1) * (lim >> 1));
}
f.NTT(lim, false), g.NTT(lim, false);
for (int i = 0; i < lim; ++i) {
f.a[i] = f.a[i] * 1ll * g.a[i] % Mod;
}
f.NTT(lim, true);
for (int i = 0; i <= n; ++i) {
write(f.a[i]), SP;
}
EL;
}
|