127 lines
4.2 KiB
C++
127 lines
4.2 KiB
C++
#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:什么是费马小定理?
|
||
答：费马小定理是一个关于模运算的定理，它陈述了如果p是一个质数，而a是任意整数且不是p的倍数，
|
||
那么a^(p-1) 与 1 (mod p) 同余。
|
||
|
||
Q:费马小定理是怎么求逆元的？
|
||
答：当p是质数时，我们分离一项出来
|
||
a * a^(p−2) ≡ 1 (mod p)
|
||
对比逆元的方程式，可以很容易得到，a关于p的逆元就是 a^(p −2),而a^(p-2)可以用快速幂求得
|
||
|
||
Q:组合数公式C(n,m)=n!/(m!*(n-m)!) ，由于需要取模，同时存在除法，所以可以考虑是否可以用费马小定理求除法逆元？
|
||
答：是可以的，原因：因为模mod=1e9+7是质数，并且，题目中的数据范围n<=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();
|
||
}
|