1.题目链接。题目大意：给定一个无向图，求这个图有多少个点的集合，每个集合至少包含一个关于这个图的独立集或者团。并且集合的元素个数要大于等于3.
2。其实这个题目就是拉姆齐定理的应用，根据拉姆齐定理，6个人中一定有三个人互相认识或者互相不认识。这个认识和不认识就是我们这道题目中的边，然后更具这个题目我们可以算出来大于等于六个人一定满足的，总共的选择方案是(C(n,0)+C(n,1)....C(n,n)=pow(2,n),减去0到5.然后我们知道，小于三一定是没戏的，那么只有3,4,5了。这个时候我们直接暴力验证就行了。实际上也是比较容易的一个题目，只需要记得拉姆齐定理即可。
#include<bits/stdc++.h> using namespace std; #pragma warning(disable:4996) const int N = 55; const int mod = 1e9 + 7; bool vis[N][N]; int n, m; #pragma warning(disable:4996) long long ans, c[N][N]; #define ll long long void init() { c[1][1] = c[0][1] = 1; for (int i = 2; i <= n; i++) for (int j = 0; j <= i; j++) { if (j == 0) c[j][i] = 1; else c[j][i] = (c[j][i - 1] + c[j - 1][i - 1]) % mod; } } ll qpow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = res * a%mod; a = a * a%mod; b >>= 1; } return res; } bool judge(int a, int b, int c) { if (vis[a][b] && vis[a][c] && vis[b][c]) return true; if (!vis[a][b] && !vis[a][c] && !vis[b][c]) return true; return false; } bool judge(int a, int b, int c, int d) { if (judge(a, b, c)) return true; if (judge(a, b, d)) return true; if (judge(a, c, d)) return true; if (judge(b, c, d)) return true; return false; } bool judge(int a, int b, int c, int d, int e) { if (judge(a, b, c, d)) return true; if (judge(a, b, c, e)) return true; if (judge(a, c, d, e)) return true; if (judge(b, c, d, e)) return true; if (judge(a, b, d, e)) return true; return false; } int main() { int T; scanf("%d", &T); for (int I = 1; I <= T; I++) { memset(vis, false, sizeof(vis)); scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { int ta, tb; scanf("%d%d", &ta, &tb); vis[ta][tb] = true; vis[tb][ta] = true; } ans = 0; if (n >= 6) { init(); ans += qpow(2, n); for (int i = 0; i < 6; i++) { ans -= c[i][n]; ans += mod; ans %= mod; } } for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) for (int k = j + 1; k <= n; k++) if (judge(i, j, k)) ans++; for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) for (int k = j + 1; k <= n; k++) for (int l = k + 1; l <= n; l++) if (judge(i, j, k, l)) ans++; for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) for (int k = j + 1; k <= n; k++) for (int u = k + 1; u <= n; u++) for (int v = u + 1; v <= n; v++) if (judge(i, j, k, u, v)) ans++; ans %= mod; printf("Case #%d: %lld\n", I, ans); } }
