python/TangDou/Topic/HDU5917.cpp

#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();
}