题目概述

JZ需要从 $n$ 个妹子中挑出 $3$ 个出去浪，但是三个妹子之间不能有冲突，一种方案 $(i,j,k),i<j<k$ 的贡献为：$Ai+Bj+Ck$ ，求所有合法方案的总贡献。

解题报告

很明显可以容斥：至少 $0$ 个冲突 $-$ 至少 $1$ 个冲突 $+$ 至少 $2$ 个冲突 $-$ 至少 $3$ 个冲突。

前面三个都很好算（就是比较烦QAQ），问题是怎么求 $3$ 个冲突的贡献，我们发现 $3$ 个冲突就是个三元环，所以只需要找三元环就行了，可以参考这篇Blog。

示例程序

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#define fr first
#define sc second
#define pb push_back
using namespace std;
typedef unsigned long long ULL;
const int maxn=200000,maxm=200000;

int n,m,D[maxn+5];ULL A,B,C,ans;pair<int,int> e[maxm+5];
vector<int> pre[maxn+5],suf[maxn+5];vector<ULL> sum[maxn+5];
int E,lnk[maxn+5],son[maxm+5],nxt[maxm+5],ti,vis[maxn+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
inline ULL C2(ULL n) {return n*(n-1)>>1;}
inline ULL Sum(ULL L,ULL R) {return (L+R)*(R-L+1)>>1;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);readi(m);readi(A);readi(B);readi(C);
    for (int i=1;i<=m;i++) {readi(e[i].fr);readi(e[i].sc);if (e[i].fr>e[i].sc) swap(e[i].fr,e[i].sc);}
    sort(e+1,e+1+m);m=unique(e+1,e+1+m)-e-1;
    for (int i=1;i<=m;i++) suf[e[i].fr].pb(e[i].sc);
    for (int i=1;i<=m;i++) swap(e[i].fr,e[i].sc);sort(e+1,e+1+m);
    for (int i=1;i<=m;i++) pre[e[i].fr].pb(e[i].sc);
    for (int i=1;i<=m;i++) D[e[i].fr]++,D[e[i].sc]++;
    for (int i=1;i<=m;i++) D[e[i].fr]<D[e[i].sc]?Add(e[i].fr,e[i].sc):Add(e[i].sc,e[i].fr);
    for (int i=0;i<n-2;i++) ans+=A*i*C2(n-i-1);
    for (int i=1;i<n-1;i++) ans+=B*i*i*(n-i-1);
    for (int i=2;i<n;i++) ans+=C*i*C2(i);
    for (int i=0;i<n;i++)
        for (int j=0,si=suf[i].size();j<si;j++){
            int u=suf[i][j];
            ans-=(A*i+B*u)*(n-1-u)+C*Sum(u+1,n-1);
            ans-=(A*i+C*u)*(u-i-1)+B*Sum(i+1,u-1);
            ans-=(B*i+C*u)*i+A*Sum(0,i-1);
        }
    for (int i=0;i<n;i++){
        int si=suf[i].size();sum[i].resize(si);if (si) sum[i][0]=suf[i][0];
        for (int j=1;j<si;j++) sum[i][j]=sum[i][j-1]+suf[i][j];
    }
    for (int i=0;i<n;i++)
        for (int j=0,si=suf[i].size();j<si;j++){
            int u=suf[i][j];
            ans+=(A*i+B*u)*(si-j-1)+C*(sum[i][si-1]-sum[i][j]);
            if (suf[u].size()) ans+=(A*i+B*u)*suf[u].size()+C*sum[u][suf[u].size()-1];
        }
    for (ULL i=0,sum=0;i<n;i++,sum=0)
        for (int j=0,si=pre[i].size();j<si;j++)
            {int u=pre[i][j];ans+=(B*u+C*i)*j+A*sum;sum+=pre[i][j];}
    for (int i=1;i<=m;i++){
        int x=e[i].fr,y=e[i].sc;ti++;
        for (int j=lnk[x];j;j=nxt[j]) vis[son[j]]=ti;
        for (int j=lnk[y];j;j=nxt[j])
            if (vis[son[j]]==ti){
                int a=x,b=y,c=son[j];if (a>b) swap(a,b);if (a>c) swap(a,c);if (b>c) swap(b,c);
                ans-=A*a+B*b+C*c;
            }
    }printf("%llu\n",ans);return 0;
}