题解：CF985G Team Players

HPXXZYY · 2025-04-13 21:39:16 · 题解

我敢赌，就算你知道怎么做，也必然得调试半天才能 AC。

\color{blue}{\texttt{[Analysis]}}

显然不可能正面计算。所以被迫正难则反。

把所有三元组分成四类：不考虑有没有边相连；有且只有一条边连接；有且只有两条边连接；三个点形成三元环。

每种情况分别考虑。

不考虑有没有边相连。

等价于对所有 (i,j,k) \quad \text{s.t.} \quad 0 \leq i <j<k<n 求出 \sum\limits_{\text{legal (i,j,k)}} Ai+Bj+Ck。

枚举 k，则 (i,j) 只能在 [0,k-1] 中取值，共 \dfrac{k(k-1)}{2} 种情况。

对于固定的 k，\sum\limits_{0 \leq i < j <k}Ai+Bj=\sum\limits_{0 \leq i < k-1}\left ( \sum\limits_{i<j<k}Ai+Bj \right )=\sum\limits_{0\leq i <k-1} \left ( Ai(k-i-1)+\sum\limits_{i<j<k}Bj\right )

然后把括号内的项展开，可以得到关于 \sum i^2，\sum i 的式子，这些式子都是有公式可以 O(1) 计算的。
有且只有一条边连接的三元组。

枚举每条边 (u,v) \quad \text{s.t.} \quad u<v，则第三个点 w 只有三种情况：w<u<v，u<w<v，u<v<w。每种情况下 u,v 的贡献都是确定的，而 w 的和是连续正整数的和，可以用公式求出。

注意： 用这种方法求出的三元组包含了第三步和第四步的情况。因此，准确地说，第二种情况是有边相连的三元组。
有且只有两条边连接的三元组。

这是最不好想的一种情况。不仅容易漏掉，也不好想解决方法。

正解还是很惊艳的。三个点有且只有两条边连接，必然两条边有一个公共点。枚举这个公共点 u，那么 v,w 就只能在和 u 有边相连的点集中取值。

问题是，这个点集可能很大，怎么办？

那我们就不要同时考虑 v,w，仅考虑单个点对答案的贡献。

如果 v<u，那么 v 前面的系数可能是 A 或者 B（绝对不会是 C）。如果系数是 A，那么 w 比 v 大。在一个有限的点集中，我们很容易知道这样的 w 有多少个，因此 Av 的系数我们就可以求出来（请注意，我们只算 v 的贡献，至于 w 的和我们先不考虑）。其它情况同理。

枚举点集里的所有点，即可求出第三种情况的贡献。

注意： 第三步里也重复计算了第四步的情况。
有三条边连接的三元组。

这部分最简单了。直接用三元组计数的模板即可。

（当然，不会这个模板就是送命。）

现在来考虑容斥系数。分别记四个步骤算出来的结果为 S_1,S_2,S_3,S_4。

所有的三元组都会在第一步中计算且仅计算一次。
第二步中，有且仅有一条边连接的三元组仅计算了一次，两条边相连的三元组计算了两次，三条边相连的三元组计算了三次。
第三步中，有两条边相连的二元组计算了一次；三条边相连的三元组计算了三次。
第四步中，三条边连接的三元组都仅计算了一次。

因此，通过你聪明的大脑，你一定可以发现，答案就是 S_1-S_2+S_3-S_4。

就这么开心的写代码吧。小心细节不要 WA 哦。

\color{blue}{\text{Code}}

typedef unsigned long long ll; 

const int N=2e5+100; 

int n,m,A,B,C,u[N],v[N];
ll ans;
vector<int> edge[N],e[N];

ll pre_sqr(int n){
    return 1ull*n*(n+1)/2*(2*n+1)/3;
}
ll pre_sum(int n){
    return 1ull*n*(n+1)/2;
}
ll get_sum(int a,int b){
    int t=(b-a+1);
    return 1ull*(a+b)*t/2;
}

ll get_all(){
    ll cnt,tmp1,tmp2,res=0;

    for(int j=2;j<n;j++){
//      从 0 到 j-1 中选出两个数
        int i=j-1;//写着简单 

        cnt=pre_sum(i);
        tmp1=1ull*i*pre_sum(i-1)-pre_sqr(i-1);
        tmp2=pre_sqr(i);

        res+=1ull*tmp1*A;
        res+=1ull*tmp2*B;
        res+=1ull*cnt*C*j;
    }

    return res;
}//第一步

ll get_minus(){
    ll res=0;

    for(int i=1;i<=m;i++){
        if (u[i]>v[i]) swap(u[i],v[i]);

        //(x, u[i], v[i])
        if (u[i]>0)
            res+=1ull*A*pre_sum(u[i]-1)+1ull*u[i]*(1ull*B*u[i]+1ull*C*v[i]);

        //(u[i], x, v[i])
        if (v[i]-u[i]>1)
            res+=1ull*B*get_sum(u[i]+1,v[i]-1)+(1ull*A*u[i]+1ull*C*v[i])*(v[i]-u[i]-1);
        //(u[i], v[i], x)
        if (v[i]<n-1)
            res+=1ull*C*get_sum(v[i]+1,n-1)+(1ull*A*u[i]+1ull*B*v[i])*(n-1-v[i]);
    } 

    return res;
}//第三步

int ind[N],vistime[N];

ll get_triple(){
    ll res=0;

    for(int i=1;i<=m;i++){
        ++ind[u[i]];
        ++ind[v[i]];
    }

    for(int i=1;i<=m;i++){
        if (ind[u[i]]>ind[v[i]]) swap(u[i],v[i]);
        else if ((ind[u[i]]==ind[v[i]])&&(u[i]>v[i])) swap(u[i],v[i]);

        edge[u[i]].push_back(v[i]);
    }

    memset(vistime,-1,sizeof(vistime));//注意这里，不然可能会多算出一些三元组
    for(int i=0;i<n;i++){
        for(int j:edge[i]) vistime[j]=i;

        for(int j:edge[i])
            for(int k:edge[j])
                if (vistime[k]==i){//因为这里
                    int t[]={i,j,k};
                    sort(t,t+3);

                    res+=1ull*A*t[0]+1ull*B*t[1]+1ull*C*t[2];
                }
    }

    return res;
}//第四步，三元环计数的板子

ll get_add(){
    for(int i=1;i<=m;i++){
        e[u[i]].push_back(v[i]);
        e[v[i]].push_back(u[i]);
    }

    ll res=0;

    for(int u=0;u<n;u++){
        e[u].push_back(u);
        sort(e[u].begin(),e[u].end());

        int x=e[u].size()-1;
        if (x==0) continue;

        for(int i=0;i<=x;i++){
            int v=e[u][i];

            if (v<u)
                res+=1ull*A*v*(x-i-1)+1ull*B*v*i;
            else if (v>u)
                res+=1ull*B*v*(x-i)+1ull*C*v*(i-1);
            else
                res+=1ull*v*(1ull*(x-i)*(x-i-1)/2*A+1ull*B*(x-i)*i+1ull*i*(i-1)/2*C); 
        }
    }//第二步

    return res;
}

int main(){
    n=read();m=read();
    A=read();B=read();C=read();
    for(int i=1;i<=m;i++){
        u[i]=read();
        v[i]=read();
    }

    ans=get_all()-get_minus()+get_add()-get_triple();

    cout<<ans<<endl;

    return 0;
}

最后，Good luck to you。