题意，给出n个不同的数，要求二元关系集合（满足交换律 传递律）但不能推出所有的元素都相等的个数。 首先有这样的一个性质，如果将二元关系用图来表示，那么满足自反传递和对称的元素构成的一定是一个完全子图。例如对于 {a,b} 集合满足自反传递对称，就有以下的二元关系 {a∼b,b∼a,a∼a,b∼b} 。也就是说只有满足条件的元素才在一个连通块内。 这样的话，求出所有的满足自反传递对称的关系集合，再用满足传递和对称的集合减去它就就行了。前一个集合实际上就是对n个元素进行一个划分，实际上就是bell数。而后一个集合推导有两种方法，一种是组合数选出满足自反的元素，划分成一些连通块，其他的元素不满足自反，而这实际上就是bell数的递推，即
bell(n+1)=∑k=0n(nk)bell(k) 另一个比较好理解的方法是， 相当于对n个元素的集合进行划分，然后将另一个元素丢到划分的集合之一，表示该集合内的所有元素都是不满足自反的，这样就表示了所有的满足传递和对称的集合。实际上相当于是对n+1个元素的集合进行划分，即 bell(n+1) 。 那么， ans=bell(n+1)−bell(n) #include <bits/stdc++.h> using namespace std; const int mod = 1000000007; const int MAXN = 4004; int dp[MAXN][MAXN]; int main() { int n; cin>>n; dp[0][0] = 1; for(int i = 1;i <= n+1;i++){ dp[i][0] = dp[i-1][i-1]; for(int j = 1;j <= i;j++){ dp[i][j] = (dp[i][j-1]+dp[i-1][j-1])%mod; } } printf("%d\n",(dp[n+1][0]-dp[n][0]+mod)%mod); return 0; }