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

· · 题解

前言

偶不，居然不是第一个写题解的。

分讨，容斥，三/四元环计数。

思路

直接求完全子图计数是困难的，考虑容斥。

设 f_{i} 表示图中边数为 i 的四元子图数量（点有序，不一定要取这四个点之间所有的边）。

那么蓝色四元完全子图的数量为 f_{0}-f_{1}+f_{2}-f_{3}+f_{4}-f_{5}+f_{6}，红色四元完全子图的数量为 f_{6}，作差得 ans=f_{0}-f_{1}+f_{2}-f_{3}+f_{4}-f_{5}。

可以对于不同的子图形状进行分类讨论，总共有 10 种情况，分别是各种菊花以及三\四元环计数和它们的变形。

除了情况⑥和情况⑧都是平凡的，所以不讨论。

对于情况⑥，可以视为三元环再加一条额外的出边。

对于情况⑧，可以视为两个共边的三元环。

记得求绝对值！

code

#include<bits/stdc++.h>
using namespace std;
template<typename G> inline void read(G&x) {x=0;G f=1;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();if(ch=='-') f=-1,ch=getchar();while(ch>='0'&&ch<='9') {x=x*10+(ch^48);ch=getchar();}x*=f;}
const int MAXN=2e5+5;
#define int long long
int n,m,ans,vis[MAXN],num[MAXN],tot,cnt[MAXN],deg[MAXN];
vector<pair<int,int> > G[MAXN];
vector<int> E[MAXN];
int u[MAXN],v[MAXN];
signed main() {
    read(n),read(m);
    ans=1ull*n*(n-1)*(n-2)/6*(n-3)/4;//0
    ans-=m*(n-2)*(n-3)/2;//1
    for(int i=1;i<=m;++i) {
        read(u[i]),read(v[i]);
        E[u[i]].emplace_back(v[i]);
        E[v[i]].emplace_back(u[i]);
        if(u[i]>v[i]) swap(u[i],v[i]);
        ans+=i-deg[u[i]]-deg[v[i]]-1;//2
        ans+=(deg[u[i]]+deg[v[i]])*(n-3);//3
        ans-=(deg[u[i]]*(deg[u[i]]-1)+deg[v[i]]*(deg[v[i]]-1))/2;//5
        ++deg[u[i]],++deg[v[i]];
    }
    for(int i=1;i<=m;++i) {
        ans-=(deg[u[i]]-1)*(deg[v[i]]-1);//4
        if(deg[u[i]]<deg[v[i]]) swap(u[i],v[i]);
        G[u[i]].emplace_back(make_pair(v[i],++tot)); 
    }
    for(int i=1;i<=n;++i) {
        for(auto p1:G[i]) {
            int j=p1.first;
            for(auto k:E[j]) {
                if(deg[i]<deg[k]||(deg[i]==deg[k]&&i>=k)) continue; 
                ans+=cnt[k]++;//7
            }
        }
        for(auto p1:G[i]) {
            int j=p1.first;
            for(auto k:E[j]) {
                cnt[k]=0;
            }
        }
    }
    for(int i=1;i<=n;++i) {
        for(auto pii:G[i]) vis[pii.first]=pii.second;
        for(auto p1:G[i]) {
            int j=p1.first,jj=p1.second;
            for(auto p2:G[j]) {
                int k=p2.first,kk=p2.second;
                if(vis[k]) {
                    ans-=(n-3);//9
                    ans+=3;//4
                    ans+=(deg[i]+deg[j]+deg[k]-6);//6
                    ans-=num[jj]++;//8
                    ans-=num[kk]++;//8
                    ans-=num[vis[k]]++;//8
                }
            }
        }
        for(auto pii:G[i]) vis[pii.first]=0;
    }
    printf("%lld",labs(ans));
    return 0; 
}