2021ZROI省选十连测Day5T2

· · 个人记录

首先，任意在空间中随机四个点，他们共面的概率为0。你就想三个点确定一个平面，再随一个点落在上面，额概率就是0。

然后这个题打暴力的前提就是把第一个样例手玩出来——四个点，正好形成一个三棱锥。

我当时讨论了好久诶，，不断计漏计重。

还有一些其他讨论方法不过没必要写了吧。

三/四元环计数：这篇博客不错。

大概是你三元环计数打标记时是只搜一层嘛，这是O(n+m)的，就很亏。

打标记也搜两层，就是四元环了嘛，复杂度还不变。

注意四元环读书最大的那个点一定连出两个外向边。但不一定另外三个点的度数相对大小如何。所以只需要保证打标记的那个点（即博客中的w）的度数小于开始搜的点即可，因而第二层需要在原图上（而不是有向图上）走。（即博客中的w和u）这样每个环只会在度数最大的地点被找到一遍。

大概是每走到一次w就把它之前被打上的标记数加上，再把标记数++。

细节见代码。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using std::vector;
//using std::cout;
//using std::endl;

const int p=998244353;
const int inv2=(p+1)/2;
int add(int x,int y){return x+y>=p?x+y-p:x+y;}
long long C(long long x){return x>1?x*(x-1)/2%p:0;}
int T;
int n,m;
const int MAXN=200200;
int read(){//int，不能读负数，longlong 
    int h=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')h=(h<<1)+(h<<3)+c-'0',c=getchar();
    return h; 
}

namespace solve1{
    vector<int>eg[MAXN];//原图 
    vector<int>g[MAXN];//有向图 
    int ans;
    int du[MAXN];

    int tag[MAXN];//其实是vis数组。是那种避免每次清空的经典小trick。 
    int get_3(){//三元环 
        long long anss=0;
        for(int u=1;u<=n;u++){
            for(int i=0;i<g[u].size();i++){
                tag[g[u][i]]=u;
            }
            for(int i=0;i<g[u].size();i++){
                int v=g[u][i];
                for(int j=0;j<g[v].size();j++){
                    if(tag[g[v][j]]==u)anss++;//如果g[v][j]被打上了标记 
                }
            }
        } 
        for(int i=1;i<=n;i++)tag[i]=0;
        return anss%p;//不超过msqrtm个/se 
    }

    int qwq[MAXN];//w当前被经过次数 
    int get_4(){
        long long anss=0;
        for(int u=1;u<=n;u++){
            for(int i=0;i<g[u].size();i++){//第一层按有向图走 
                int v=g[u][i];
                for(int j=0;j<eg[v].size();j++){//第二层按原图走 
                    int w=eg[v][j];
                    if(du[u]>du[w]||(du[u]==du[w]&&u>w)){//要求du[u]>du[w]（u是四元环中度数最大的那个。顺便把w,u相同也判了
//                      cout<<u<<" "<<v<<" "<<w<<endl; 
                        if(tag[w]!=u)tag[w]=u,qwq[w]=0;//第一次走到w，要清空之前的次数
                        anss=add(anss,qwq[w]);//已经经过了qwq[w]次 
                        qwq[w]++;//又经过了一次 
                    }
                }
            }
        }
        return anss; 
    }

    void clr_(){
        for(int i=1;i<=n;i++)eg[i].clear(),g[i].clear();
        for(int i=1;i<=n;i++)du[i]=tag[i]=qwq[i]=0;
        ans=0;
    }

    int work1(){
        scanf("%d",&T);
        while(T--){
            scanf("%d%d",&n,&m);
            for(int i=1;i<=m;i++){
                int u=read(),v=read();
                du[u]++,du[v]++;
                eg[u].push_back(v),eg[v].push_back(u);
            }
            for(int u=1;u<=n;u++){
                for(int j=0;j<eg[u].size();j++){
                    int v=eg[u][j];
                    if(u<v){
                        if(du[u]>du[v]||(du[u]==du[v]&&u>v))g[u].push_back(v); 
                        else g[v].push_back(u);
                    }
                }
            }
            ans=1ll*m*(n+m-3)%p; 
            for(int i=1;i<=n;i++){
                ans=add(ans,1ll*du[i]*(du[i]-1)/2%p);//写成了du[i-1]???hhh我是five 
            }
//          cout<<get_3()<<" "<<get_4()<<endl; 
            ans=add(ans,get_3()*3%p);
            ans=add(ans,get_4());
            printf("%d\n",ans);
            clr_();
        }
        return 0;
    }
}

int main(){
    return solve1::work1();
}