1 参考自：http://blog.csdn.net/Miracle_ma/article/details/52737597?locationNum=1 2 给你n个点，m条边，然后告诉你选择一个点集S 3 如果里面有一个子集A，A里面的点都不相连，或者都相连，则这个点集不稳定 4 求不稳定的个数 5 子集A的大小是大于等于3，所以考虑到6个点的图，里面肯定有3个点，互相有边，或者互相没边 6 所以用ramsey定理优化，6以上都可以直接求 7 剩下3，4，5的情况，搜索或者循环 8 #include <iostream> 9 #include <algorithm>10 #include <cstdio>11 #include <cmath>12 #include <memory.h>13 #include <queue>14 #include <map>15 #include <set>16 using namespace std;17 typedef long long ll;18 const int maxn = 1e5 + 10;19 const int mod = 1e9 + 7;20 int n,m,mp[60][60];21 ll fact[60];22 int ok3(int a,int b,int c){23     if(mp[a][b] == 0&&mp[a][c] == 0&&mp[b][c] == 0) return 1;24     if(mp[a][b] == 1&&mp[a][c] == 1&&mp[b][c] == 1) return 1;25     return 0;26 }27 int ok4(int a,int b,int c,int d){28     if(ok3(a,b,c)||ok3(a,b,d)||ok3(a,c,d)||ok3(b,c,d)) return 1;29     else return 0;30 }31 int ok5(int a,int b,int c,int d,int e){32     if(ok4(a,b,c,d)||ok4(a,b,c,e)||ok4(a,b,d,e)||ok4(a,c,d,e)||ok4(b,c,d,e)) return 1;33     else return 0;34 }35 void init(){36     fact[0]=1;37     for(int i=1;i<=50;i++) fact[i]=fact[i-1]*i%mod;38 }39 ll qpow(ll a,ll n){40     ll ans=1;41     while(n){42         if(n&1) ans=ans*a%mod;43         a=a*a%mod;44         n>>=1;45     }46     return ans;47 }48 49 ll C(int n,int m){50     return fact[n]*qpow(fact[m],mod-2)%mod*qpow(fact[n-m],mod-2)%mod;51 }52 53 int main() {54    // freopen("in.txt","r",stdin);55     //freopen("out.txt","w",stdout);56     int T;57     init();58     int cas = 0;59     cin>>T;60     while(T--){61         scanf("%d%d",&n,&m);62         memset(mp,0,sizeof(mp));63         int x,y;64         for(int i = 1;i <= m;i++){65             scanf("%d%d",&x,&y);66             mp[x][y] = 1;67             mp[y][x] = 1;68         }69         ll ans = 0;70         for(int i = 1;i <= n;i++)71             for(int j = i + 1;j <= n;j++)72                 for(int k = j + 1;k <= n;k++)73                     if(ok3(i,j,k)) ans++;74         for(int i = 1;i <= n;i++)75             for(int j = i + 1;j <= n;j++)76                 for(int k = j + 1;k <= n;k++)77                     for(int l = k + 1;l <= n;l++)78                         if(ok4(i,j,k,l)) ans++;79         for(int i = 1;i <= n;i++)80             for(int j = i + 1;j <= n;j++)81                 for(int k = j + 1;k <= n;k++)82                     for(int l = k + 1;l <= n;l++)83                         for(int m = l + 1;m <= n;m++)84                             if(ok5(i,j,k,l,m)) ans++;85         ans %= mod;86          if(n>=6){87             for(int i=6;i<=n;i++){88                 ans+=C(n,i);89                 if(ans>=mod) ans-=mod;90             }91         }92         printf("Case #%d: %lld\n",++cas,ans);93     }94 95     return 0;96 }