cf568 B. Symmetric and Transitive（贝尔数）

题意：

求大小为 n 的集合中满足对称性和传递性，但不满足自反性的所有二元关系种数。要取模。

一种关系定义为一个pair的集合 \(\rho\)，\(x\sim y \iff (x,y)\in \rho\)

\(1\le n \le 4000\)

思路：

其实由 \((x,y)\in \rho, (y,x)\in \rho\) 和传递性是可以推出 \((x,x)\in \rho\) 和 \((y,y)\in \rho\) 的。也就是说一个元素一旦在 \(\rho\) （的某一个pair）中出现，这个元素就满足自反性。问题在于自反性要求对每一个元素 \(x\) 都有 \(x \sim x\)。

在原集 \(S\) 中选一个真子集 \(E\)，用 \(E\) 中的元素来构造 \(\rho\)，即 \(E\) 中的每个元素都在 \(\rho\) 中出现。那么 \(E\) 中的每个元素都有自反性，但 \(E\) 外的每个元素都无自反性，因此 \(\rho\) 不是等价关系。

\(E\) 的选法显然有 \(C_n^i\) 种，其中 \(n,i\) 分别为 \(S,E\) 的元素个数，\(0\le i < n\) 。怎么用 \(E\) 来构造 \(\rho\) 呢？

可以把 \(\rho\) 视为一个图，图中每个点都有自环。这个图由若干连通分量组成。那么每种 \(\rho\) 的构造就对应 \(E\) 的一种划分，集合的不同的划分数就是贝尔数 \(B_i\)

答案是 \(\sum \limits _{i=0}^{n-1} C_n^iB_i\) ，也可以用 \(B_{n+1}=\sum \limits _{k=0}^n C_n^k B_k\) 化简为 \(B_{n+1}-B_n\)

\(O(n^2)\)

const int N = 4010, MOD = 1e9 + 7;

int B[N][N];
void init(int n) //每行首项是贝尔数
{
    B[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        B[i][0] = B[i-1][i-1];
        for(int j = 1; j <= i; j++)
            B[i][j] = (B[i-1][j-1] + B[i][j-1]) % MOD;
    }
}

signed main()
{
    int n; cin >> n;
    init(n + 1);
    cout << (B[n+1][0] - B[n][0] + MOD) % MOD;
}