「Codeforces 568B」Symmetric and Transitive 题解

题目

题意

计数\(n\)个元素的满足对称性、传递性，但不满足自反性的二元关系种数，\(n\le4000\)

思路

发现若\(a\sim b\)则有\(b\sim a,a\sim a,b\sim b\)，所以一定存在不和其他所有元素相连的，不妨设有\(n-k\)个单独点，剩下的\(k\)个点可以分为几个集合（注意大小为\(1\)的集合不等于单独点，大小为\(1\)的集合有自身连自身），此时对答案的贡献为\(\binom{n}{k}B_{k}\)（\(n\)个里选\(k\)个分成若干集合，其他都是单独的），其中\(B_i\)为第\(i\)个贝尔数，等于\(\sum_{j=1}^i\left\{\begin{matrix}i\\j\end{matrix}\right\}\)，于是答案就为\(\sum_{k=0}^{n-1}\binom{n}{k}B_k\)

由于\(n\)很小，\(\operatorname{O}(n^2)\)搞出第二类 Stirling 数即可

代码

int fac[N], ifac[N];
int S[N][N];
int Bell[N];
int n;

int main () {
  read(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;
  }
  S[0][0] = 1;
  Bell[0] = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
      S[i][j] = (S[i - 1][j - 1] + S[i - 1][j] * 1ll * j % Mod) % Mod;
      Bell[i] = (Bell[i] + S[i][j]) % Mod;
    }
  }
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    ans = (ans + C(n, i) * 1ll * Bell[i] % Mod) % Mod;
  }
  write(ans), EL;
  return 0;
}