You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

127 lines
4.2 KiB

2 years ago
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int M = 1e2 + 7;
const int P = 1e9 + 7;
int T, n, m, cas = 1;
int g[M][M];
int fac[M];
// 快速幂
int qmi(int a, int b) {
int res = 1;
a %= P;
while (b) {
if (b & 1) res = res * a % P;
b >>= 1;
a = a * a % P;
}
return res;
}
/*
Q:?
pap
a^(p-1) 1 (mod p)
Q:
p
a * a^(p2) 1 (mod p)
ap a^(p 2),a^(p-2)
Q:C(n,m)=n!/(m!*(n-m)!)
mod=1e9+7n<=50,mod
*/
int C(int n, int m) {
/*
fac[n]: n!
qmi(fac[m], P - 2) : (m!)^(p-2),m! (m!)^(p-2)
qmi(fac[n - m], P - 2) :
*/
return fac[n] * qmi(fac[m], P - 2) % P * qmi(fac[n - m], P - 2) % P;
}
int judge3(int i, int j, int k) { // 判断三点之间满不满足不稳定点集
if (g[i][j] && g[i][k] && g[j][k]) return 1; // 三点之间相连
if (!g[i][j] && !g[i][k] && !g[j][k]) return 1; // 三点之间不互连
return 0;
}
int judge4(int i, int j, int k, int l) {
if (judge3(i, j, k) || judge3(i, j, l) || judge3(j, k, l) || judge3(i, k, l)) return 1;
// 表示4个点中有三个点为不稳定点集就行,为什么呢?
// 因为时题目要求的不稳定点集为3个点。
return 0;
}
int judge5(int i, int j, int k, int l, int o) {
// 表示5个点中有4个点满足就行
if (judge4(i, j, k, l) || judge4(i, j, k, o) || judge4(i, j, l, o) || judge4(j, k, l, o)
|| judge4(i, k, l, o)) return 1;
return 0;
}
void solve() {
cin >> n >> m; // n个顶点,m条边
memset(g, 0, sizeof g); // 初始化地图
while (m--) {
int a, b;
cin >> a >> b;
g[a][b] = g[b][a] = 1; // 无向图
}
int ans = 0;
if (n >= 6) {
ans = qmi(2, n);
// ① 多项式定理C(n,0)+C(n,1)+...+C(n,n)=2^n
// ② 也可以这样来思考一个也不要要1个要2个要3个...,要n个
// C(n,k)(k>=6)表示从n个中取k个出来总存在一个不稳定点集的个数三点之间互联或三点之间不连
for (int i = 0; i < 6; i++) /// 减去前5个
ans = (ans - C(n, i) + P) % P;
}
if (n >= 3) { // 枚举任意3个
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
for (int k = j + 1; k <= n; k++)
if (judge3(i, j, k)) ans = (ans + 1) % P;
}
if (n >= 4) { // 暴力取4个
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 (judge4(i, j, k, l)) ans = (ans + 1) % P;
}
if (n >= 5) { // 暴力取5个
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++)
for (int o = l + 1; o <= n; o++)
if (judge5(i, j, k, l, o)) ans = (ans + 1) % P;
}
printf("Case #%lld: %lld\n", cas++, ans);
}
signed main() {
// 加快读入
ios::sync_with_stdio(false), cin.tie(0);
// 预处理阶乘数组(同步取模)
fac[0] = 1, fac[1] = 1;
for (int i = 2; i < M; i++) fac[i] = fac[i - 1] * i % P;
cin >> T;
while (T--) solve();
}