自动搬运

查看原文

来自洛谷，原作者为

	Arghariza Delightful.

搬运于2025-08-24 22:52:24，当前版本为作者最后更新于2024-05-27 10:41:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

考虑容斥掉蓝色完全子图。令 $f_i(0\le i\le 6)$ 为硬点有 $i$ 条红边的方案数（即有 $j$ 条红边的子图贡献为 $\dbinom{j}{i}$），$g_i$ 为恰有 $i$ 条红边的方案数。

$$f_i=\sum\limits_{j=i}\dbinom{j}{i}g_j\iff g_i=\sum\limits_{j=i}\dbinom{j}{i}(-1)^{j-i}f_j $$

考虑我们要求 $|g_0-g_6|=|f_0-f_1+f_2-f_3+f_4-f_5|$。

然后画图发现每种情况都是可以算的，分类讨论即可：

• $f_0$：即 $\dbinom{n}{4}$。
• $f_1$：$m\dbinom{n-2}{2}$。
• $f_2$：$(n-3)\sum\limits_{i}\dbinom{d_i}{2}+\dbinom{m}{2}-\sum\limits_{i}\dbinom{d_i}{2}$，$d_i$ 为 $i$ 的度数。
• $f_3$：$(n-3)c_3+\sum\limits_{i}\dbinom{d_i}{3}+\sum\limits_{(u,v)\in E}(d_u-1)(d_v-1)-3c_3$，$c_3$ 为三元环个数。
• $f_4$：$\sum\limits_{i}ct_i(d_i-2)+c_4$，$ct_i$ 为以 $i$ 为顶点的三元环数，$c_4$ 为四元环数。
• $f_5$：$\sum\limits_{(u,v)\in E}\dbinom{cnt_{u,v}}{2}$，$cnt_{u,v}$ 为包含 $(u,v)$ 边的三元环数。

复杂度 $O(m\sqrt m)$，瓶颈在三元环/四元环计数。

#include <bits/stdc++.h>
#define eb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define int long long

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tu;
bool Mbe;

const int N = 1e5 + 100;
const int M = 2e5 + 200;

int n, m, l3, c3, c4;
int op[10], d[N], ct[N], cte[M], vs[N];
vector<pi> g[N], h[N];

void solve() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) 
        cin >> u >> v, g[u].eb(v, i), g[v].eb(u, i), d[u]++, d[v]++;
    for (int u = 1; u <= n; u++) {
        for (pi p : g[u]) {
            int v = p.fi, w = p.se;
            if (d[u] > d[v] || (d[u] == d[v] && u > v)) h[u].eb(v, w);
        }
    }
    for (int u = 1; u <= n; u++) {
        for (pi p : h[u]) {
            int v = p.fi;
            for (pi q : g[v]) {
                int w = q.fi;
                if (d[u] < d[w] || (d[u] == d[w] && u <= w)) continue;
                c4 += (ct[w]++);
            }
        }
        for (pi p : h[u]) 
            for (pi q : g[p.fi]) ct[q.fi] = 0;
    }
    for (int u = 1; u <= n; u++) {
        for (pi p : h[u]) vs[p.fi] = p.se;
        for (pi p : h[u]) {
            int v = p.fi, i = p.se;
            for (pi q : h[v]) {
                int w = q.fi, j = q.se;
                if (!vs[w]) continue;
                c3++, ct[u]++, ct[v]++, ct[w]++;
                cte[i]++, cte[j]++, cte[vs[w]]++;
            }
        }
        for (pi p : h[u]) vs[p.fi] = 0;
    }
    for (int i = 1; i <= n; i++)
        l3 += d[i] * (d[i] - 1) / 2;
    op[0] = (__int128)n * (n - 1) / 2 * (n - 2) / 3 * (n - 3) / 4;
    op[1] = m * (n - 2) * (n - 3) / 2;
    op[2] = (n - 3) * l3 + m * (m - 1) / 2 - l3;
    op[3] = (n - 3) * c3;
    for (int i = 1; i <= n; i++) op[3] += d[i] * (d[i] - 1) * (d[i] - 2) / 6;
    for (int i = 1; i <= n; i++) {
        for (pi p : g[i]) {
            int j = p.fi;
            if (i < j) op[3] += (d[i] - 1) * (d[j] - 1);
        }
    }
    op[3] -= 3 * c3;
    op[4] = c4;
    for (int i = 1; i <= n; i++) op[4] += ct[i] * (d[i] - 2);
    for (int i = 1; i <= n; i++) {
        for (pi p : g[i]) {
            int j = p.fi;
            if (i < j) op[5] += cte[p.se] * (cte[p.se] - 1) / 2;
        }
    }
    cout << abs(op[0] - op[1] + op[2] - op[3] + op[4] - op[5]) << '\n';
}

bool Med;
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
	#ifdef FILE
		freopen(".in", "r", stdin);
		freopen(".out", "w", stdout);
	#endif
	int T = 1;
	// cin >> T;
	while (T--) solve();
	cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
	return 0;
}