题解：P9850 [ICPC2021 Nanjing R] Ancient Magic Circle in Teyvat

Arghariza · 2024-05-27 10:41:03 · 题解

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

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

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

复杂度 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;
}