[组合数+bell数] codeforces 569D. Symmetric and Transitive

D. Symmetric and Transitive
题意：
一个集合 S 有 n 个元素，问它上面的二元关系的数量，要求二元关系满足对称性和传递性，不满足自反性。
题解：
学过离散应该知道，二元关系就是笛卡尔积 S×S 的子集。
开下脑洞可以想象一个 n 节点的有向完全图，并且对任意节点我们加上一个自环，任意边的组合就是一个关系，可以看出只要一个关系包含了所有自环，那么这个关系就有自反性。
再想想的话，假如 (1,2) 和 (2,1) 满足关系 P ，那么如果不满足关系 (1,1)或(2,2) 的话，那就不满足传递性了，因为根据传递性的定义， 1P2且2P1那么应该有1P1 ，所以假如我们没有包含 x 的自环，那么任意 x 的边都不应该包含。
现在问题就变成了一个 n 个节点的有向完全图（加入自环），任选 k(k>=1) 个点去掉，剩下的图中边的任意合法组合（满足自反和对称和传递，满足自反是因为已将不满足的先选出来了），回到集合的角度看，满足自反对称传递就是等价关系，也就是算出去掉 k(k>=1) 个元素后集合的等价关系的个数，这就是贝尔数了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4005;
const ll mod = 1e9+7;
ll C[N][N], bell[N][N];
void cm(ll& x){ if(x >= mod) x -= mod; }
void init(){
for(int i = 0; i < N; ++i){
        C[i][0] = 1;
for(int j = 1; j <= i; ++j){
            C[i][j] = C[i-1][j-1] + C[i-1][j];
            cm(C[i][j]);
        }
    }
    bell[1][1] = 1;
for(int i = 2; i < N; ++i){
        bell[i][1] = bell[i-1][i-1];
for(int j = 2; j <= i; ++j){
            bell[i][j] = bell[i][j-1]+bell[i-1][j-1];
            cm(bell[i][j]);
        }
    }
}
int main(){
    init();
    ll ans = 0, n;
cin >> n;
for(int i = 1; i <= n; ++i){
        ans += C[n][i]*bell[n-i][n-i]%mod;
        cm(ans);
    }
cout << ans << endl;
}