「洛谷P5395」第二类斯特林数·行 题解
题意
求$\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板子
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;
}
本博客采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可
本文链接:https://blog.seniorious.cc/2020/luogu-5395/