[2018HN省队集训D6T2] girls

题意

给定一张 \(n\) 个点 \(m\) 条边的无向图, 求选三个不同结点并使它们两两不邻接的所有方案的权值和 \(\bmod 2^{64}\) 的值. 一个方案 \((i,j,k)\) 的权值定义为 \(iA+jB+kC\), 其中 \(A,B,C\) 给定且 \(i<j<k\). 点从 \(0\) 开始标号.

\(n,m\le 2\times 10^5\).

题解

出题人: 用心造题, 用脚造数据

这题场上看出标算, 然而其中 \(2\) 条边的贡献部分算挂了没调出来. 最后交了一个和 \(O(n^3)\) 裸暴力组起来的程序居然tm拿了 \(90\) 分...好气啊...感觉最后的努力都在和空气斗智斗勇实际上确实是, 因为式子是错的233

部分分里有一个 \(m=0\) 的, 由这个部分分可以想到如何快速求出所有选三个点的方案的贡献, 显然直接枚举结点计算出它贡献分别为 \(A,B,C\) 的方案数量就好了, 复杂度 \(O(n)\).

考虑容斥的解法. 计算出所有方案减去存在一条边的三元组再加上存在两条边的三元组再减去存在三条边的三元组. 注意为了保证容斥的正确性, 每个三元组的贡献应该是该三元组中对应结构的数量.

计算存在一条边的三元组贡献直接枚举边 \((u,v)\) 且 \(u<v\) , 则第三个点 \(w\) 与 \(u,v\) 的大小关系分三种情况讨论再用等差数列求和做就可以了. 这一步是 \(O(m)\) 的.

两条边的情况注意不能直接用三元环计数的方法做. 因为这样的结构的数量是 \(O(m^2)\) 的, 各种复杂度正确的枚举方法都枚举不全. 实际上我们可以枚举拐角处的结点是哪个, 然后预处理出和这个点邻接且编号大于/小于该点的结点分别有哪些, 丢到 std::vector 里排序前缀和一下就可以 \(O(m)\) 算了.

三条边是三元环计数问题. 按度数与 \(\sqrt m\) 的关系分类, 根据Handshake Lemma所有的点的度数和为 \(2m\), 所以度数大于 \(\sqrt m\) 的点不超过 \(\sqrt m\) 个, 直接枚举所有三元组计算即可. 这部分复杂度 \(O(m^{3/2})\). 度数小于 \(\sqrt m\) 的部分可以从每个点出发枚举两个出点, 判断这两个出点是否联通. 容易发现每条边最多被枚举 \(O(\sqrt m)\) 次, 这部分复杂度也是 \(O(m^{3/2})\) 的. 总复杂度 \(O(m^{3/2})\).

然而调了很久一直TLE. 为啥呢?

std::unordered_set 害人不浅...手写了一个十几行的Hash表判断联通性就过了...实测开 O2 之后查询时间要多 \(20\) 倍.

什么 \(O(1)\) 都是骗人的QAQ!

参考代码

#include <bits/stdc++.h>

const int MOD=1e6+37;
const int MAXV=2e5+10;
const int MAXE=1e6+10;
typedef unsigned long long uintEx;

struct Edge{
    int from;
    int to;
    Edge* next;
};
Edge E[MAXE];
Edge* head[MAXV];
Edge* top=E;

struct List{
    uintEx key;
    List* next;
    List(const uintEx& k):key(k),next(NULL){}
};
List* L[MOD];

int v;
int e;
uintEx A;
uintEx B;
uintEx C;
int deg[MAXV];
std::vector<uintEx> le[MAXV];
std::vector<uintEx> gr[MAXV];

uintEx Sum(int,int);
void Insert(int,int);
bool Exist(const uintEx&);
void Insert(const uintEx&);
template<typename Int> void ReadInt(Int&);
template<typename Int,typename... Arg> void ReadInt(Int&,Arg&...);

int main(){
    ReadInt(v,e);
    ReadInt(A,B,C);
    for(int i=0;i<e;i++){
        int a,b;
        ReadInt(a,b);
        ++a,++b;
        Insert(a,b);
        Insert(b,a);
        ++deg[a],++deg[b];
    }
    uintEx ans=0;
    std::vector<int> large,small;
    int sqre=sqrt(e);
    for(int i=1;i<=v;i++){
        ans+=(uintEx(i-1)*uintEx(i-2)/2)*C*uintEx(i-1);
        ans+=uintEx(i-1)*uintEx(v-i)*B*uintEx(i-1);
        ans+=(uintEx(v-i)*uintEx(v-i-1)/2)*A*uintEx(i-1);
        std::sort(le[i].begin(),le[i].end());
        std::sort(gr[i].begin(),gr[i].end());
        for(size_t k=1;k<le[i].size();k++)
            le[i][k]+=le[i][k-1];
        for(size_t k=1;k<gr[i].size();k++)
            gr[i][k]+=gr[i][k-1];
        if(deg[i]>sqre)
            large.push_back(i);
        else
            small.push_back(i);
    }
    for(Edge* i=E;i!=top;i++){
        if(i->from<i->to){
            ans-=Sum(0,i->from-2)*A+uintEx(i->from-1)*(B*(i->from-1)+C*(i->to-1));
            ans-=Sum(i->from,i->to-2)*B+uintEx(i->to-i->from-1)*(A*(i->from-1)+C*(i->to-1));
            ans-=Sum(i->to,v-1)*C+uintEx(v-i->to)*(A*(i->from-1)+B*(i->to-1));
        }
    }
    for(int i=1;i<=v;i++){
        if(!le[i].empty()&&!gr[i].empty())
            ans+=(*le[i].rbegin())*uintEx(gr[i].size())*A
                +uintEx(le[i].size())*uintEx(gr[i].size())*B*(i-1)
                +(*gr[i].rbegin())*uintEx(le[i].size())*C;
        for(size_t k=1;k<le[i].size();k++)
            ans+=le[i][k-1]*A+((le[i][k]-le[i][k-1])*B+(i-1)*C)*k;
        for(size_t k=1;k<gr[i].size();k++)
            ans+=gr[i][k-1]*B+((gr[i][k]-gr[i][k-1])*C+(i-1)*A)*k;
    }
    uintEx triple=0;
    std::sort(large.begin(),large.end());
    for(size_t ii=0;ii<large.size();ii++){
        int i=large[ii];
        for(size_t jj=ii+1;jj<large.size();jj++){
            int j=large[jj];
            if(!Exist((uintEx(i)<<32)|j))
                continue;
            for(size_t kk=jj+1;kk<large.size();kk++){
                int k=large[kk];
                if(Exist((uintEx(i)<<32)|k)&&Exist((uintEx(j)<<32)|k))
                    triple+=(i-1)*A+(j-1)*B+(k-1)*C;
            }
        }
    }
    int cnt=0;
    for(auto s:small){
        for(Edge* i=head[s];i!=NULL;i=i->next){
            if(deg[i->to]<=sqre&&i->to<=s)
                continue;
            for(Edge* j=i->next;j!=NULL;j=j->next){
                if(deg[j->to]<=sqre&&j->to<=s)
                    continue;
                assert(++cnt<=2e7);
                if(Exist((uintEx(i->to)<<32)|j->to)){
                    uintEx q[3]={s-1,i->to-1,j->to-1};
                    std::sort(q,q+3);
                    triple+=q[0]*A+q[1]*B+q[2]*C;
                }
            }
        }
    }
    ans-=triple;
    printf("%llu\n",ans);
    return 0;
}

inline uintEx Sum(int l,int r){
    return l<=r?uintEx(l+r)*uintEx(r-l+1)/2:0;
}

inline void Insert(int from,int to){
    Insert((uintEx(from)<<32)|to);
    if(to>from)
        gr[from].push_back(to-1);
    else
        le[from].push_back(to-1);
    top->from=from;
    top->to=to;
    top->next=head[from];
    head[from]=top++;
}

template<typename Int> void ReadInt(Int& target){
    target=0;
    register char ch=getchar();
    while(!isdigit(ch))
        ch=getchar();
    while(isdigit(ch)){
        target=target*10+ch-'0';
        ch=getchar();
    }
}

template<typename Int,typename... Arg> void ReadInt(Int& target,Arg&... args){
    ReadInt(target);
    ReadInt(args...);
}

inline void Insert(const uintEx& k){
    int pos=k%MOD;
    if(!L[pos])
        L[pos]=new List(k);
    else{
        List* cur=L[pos];
        while(cur->next&&cur->key!=k)
            cur=cur->next;
        if(cur->key!=k)
            cur->next=new List(k);
    }
}

inline bool Exist(const uintEx& k){
    for(List* cur=L[k%MOD];cur!=NULL;cur=cur->next){
        if(cur->key==k)
            return true;
    }
    return false;
}