「洛谷P5395」第二类斯特林数·行 题解 | Seniorious' blog

题目

题意

求$\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/