「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;
}

本博客采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可
本文链接:https://blog.seniorious.cc/2020/CF-568B/