一道离散数学知识点的题
题目：http://codeforces.com/problemset/problem/569/D
题目大意： 要求找出n个元素组成集合A，所满足的反自反，对称，可传递的所有情况种数。
题解： 由于不难发现，所满足的情况为，A集合中随意挑k个元素，这些元素所自由组合后所形成的集合的种数。 因为只要满足一个子集是A的真子集，那么，这个集合与自己笛卡尔乘积后所构成的集合，一定满足反自反，对称，可传递。 所以我们每次只需要选择k个元素，再让这k个元素自由划分即可。 就是用到组合数和bell数 顺便扒到了个bell数的板子
附上AC代码
/* @resource: codeforces 569d @date: 2017-4-13 @author: QuanQqqqq @algorithm: bell数 + 组合数学 */ #include <bits/stdc++.h> #define ll long long #define MAXN 4007 using namespace std; ll bell[MAXN][MAXN]; ll c[MAXN][MAXN]; const ll mod = 1e9 + 7; void init(){ c[0][0] = c[1][0] = c[1][1] = 1; for(int i = 2;i < MAXN;i++){ for(int j = 0;j <= i;j++){ if(j == 0 || j == i){ c[i][j] = 1; } else { c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod; } } } bell[0][0] = bell[1][1] = 1; for(int i = 2;i < MAXN;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]) % mod; } } } int main(){ init(); int n; ll ans = 0; scanf("%d",&n); for(int i = 0;i < n;i++){ ans += c[n][i] * bell[i][i] % mod; ans %= mod; } printf("%lld\n",ans); }