題干：

Long long ago, there was a prosperous kingdom which consisted of n cities and every two cites were connected by an undirected road.

However, one day a big monster attacked the kingdom and some roads were destroyed. In order to evaluate the influence brought by the catastrophe, the king wanted to know the instability of his kingdom. Instability is defined as the number of the unstable subset of {1, 2,??,n}.

A set S is unstable if and only if there exists a set A such that?A?S(|A|≥3A?S(|A|≥3) and A is a?clique?or an?independent set, namely that cites in A are pairwise connected?directly?or they are pairwise disconnected.

Archaeologist has already restored themroads that were not destroyed by the monster. And they want you to figure out the instability.

Since the answer may be tremendously huge, you are only required to write a program that prints the answer modulo 1000000007.

Input

The first line contains only one integer T, which indicates the number of test cases.

For each test case, the first line contains two integers n (3≤n≤503≤n≤50) and m (1≤m≤n(n?1)/21≤m≤n(n?1)/2), indicating the number of cities and the number of roads.

Then the following are m lines, each of which contains two integers x and y, indicating there is a road between the city x and the city y.

It is guarenteed that there does not exist a road connecting the same city and there does not exist two same roads.

Output

For each test case, print a line “Case #x: y”, where x is the case number (starting from 1) and y is an integer indicating the instability modulo 1000000007.

Sample Input

2 4 3 1 2 2 3 1 3 3 0

Sample Output

Case #1: 2 Case #2: 1

Hint

? In the first example, {1,2,3} and {1,2,3,4} , containing the subset {1,2,3} which is connected directly, are considered unstable. ? In the second example, {1,2,3} is considered unstable because they are not pairwise connected directly.

題目大意：

給你一個n個點m條邊的無向圖，問圖中有多少個“unstable ”的集合？定義“unstable”的集合為這個集合里面存在一個子集(大小>=3)為團或者是獨立集。(n<=50)

解題報告：

首先觀察數據范圍，，感覺點數比較多的集合肯定都是“unstable”的，然后湊一下發現點數為6的時候就肯定是“unstable”的了，所以點數大于6的肯定也都是，所以可以直接組合數算出來，然后小范圍的情況直接暴力dfs。比賽的時候組合數竟然寫掛了，我以為C(n,m)中n只有50，m只有5，所以可以直接(n!)/((m!)*(n-m)!)，，但是忘記了你算n!的時候會炸。真的是醉了。

賽后看題解發現有個定理：

Ramsey定理：?世界上任意6個人中，總有3個人相互認識，或互相皆不認識。

證明如下：首先，把這6個人設為A、B、C、D、E、F六個點。由A點可以引出AB、AC、AD、AE、AF五條線段。設：如果兩個人認識，則設這兩個人組成的線段為紅色；如果兩個人不認識，則設這兩個人組成的線段為藍色。

由抽屜原理可知：這五條線段中至少有三條是同色的。不妨設AB、AC、AD為紅色。若BC,CD,BD至少存在一條為紅色，則至少存在三人相互認識，結論成立。若BC,CD,BD均為藍色，則B,C,D相互不認識，結論成立。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 50 + 5; const ll mod = 1e9 + 7; int n,m; int ok[MAX][MAX]; vector<int> vv; ll ans,tmp; int j3() {int up = vv.size(); for(int i = 0; i<up; i++) {for(int j = i+1; j<up; j++) {for(int k = j+1; k<up; k++) {int x = vv[i],y = vv[j],z = vv[k];if(ok[x][y]+ok[x][z]+ok[y][z] == 3 || ok[x][y]+ok[x][z]+ok[y][z] == 0) return 1;}}}return 0; } int j4() {int up = vv.size();for(int i = 0; i<up; i++) {for(int j = i+1; j<up; j++) {for(int k = j+1; k<up; k++) {for(int l = k+1; l<up; l++) {int x = vv[i],y = vv[j],z = vv[k],q = vv[l];if(ok[x][y]+ok[x][z]+ok[x][q]+ok[y][z]+ok[y][q]+ok[z][q] == 6 || ok[x][y]+ok[x][z]+ok[x][q]+ok[y][z]+ok[y][q]+ok[z][q] == 0) return 1;}}}}return 0; } int j5() {int up = vv.size();for(int i = 0; i<up; i++) {for(int j = i+1; j<up; j++) {for(int k = j+1; k<up; k++) {for(int l = k+1; l<up; l++) {for(int p = l+1; p<up; p++) {int x = vv[i],y = vv[j],z = vv[k],q = vv[l],w = vv[p];if(ok[w][x]+ok[w][y]+ok[w][z]+ok[w][q]+ok[x][y]+ok[x][z]+ok[x][q]+ok[y][z]+ok[y][q]+ok[z][q] == 10 || ok[w][x]+ok[w][y]+ok[w][z]+ok[w][q]+ok[x][y]+ok[x][z]+ok[x][q]+ok[y][z]+ok[y][q]+ok[z][q] == 0) return 1;}}}}}return 0; } void dfs(int cur,int stp,int all) { if(stp == all) {if(all == 3) tmp += j3();if(all == 4) tmp += j3()||j4();if(all == 5) tmp += j3()||j4()||j5();return;}for(int i = cur; i<=n; i++) {vv.pb(i);dfs(i+1,stp+1,all);vv.pop_back();} } ll C(int n,int m) {ll tmp1 = 1,tmp2=1,tmp3=1;for(int i = n; i>=n-m+1; i--) tmp1 *= i;for(int i = 1; i<=m; i++) tmp2 *= i;return tmp1/tmp2; } int main() {int T,iCase=0;cin>>T;while(T--) {scanf("%d%d",&n,&m);ans=1;memset(ok,0,sizeof ok);for(int u,v,i = 1; i<=m; i++) scanf("%d%d",&u,&v),ok[u][v]=ok[v][u]=1;for(int i = 1; i<=n; i++) ans = ans*2%mod;ans = (ans+2*mod-1-n-n*(n-1)/2)%mod;for(int i = 3; i<=min(n,5); i++) {tmp=0;//每次都清零vv.clear();dfs(1,0,i);ans = (ans+10*mod+tmp - C(n,i))%mod;}printf("Case #%d: %lld\n",++iCase,ans%mod);}return 0 ; }

總結：其實dfs的時候每次判斷如果不符合的情況就ans--就不會出現組合數爆longlong這種情況了（雖然主要還是代碼寫掛了）。上面代碼中的寫法是先用一個tmp變量記錄符合的情況，然后再先減去組合數的情況（先認為都不合法），再加上合法情況。

總結

以上是生活随笔為你收集整理的【HDU - 5917】Instability（规律，结论，Ramsey定理，知识点，tricks）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。