三元环计数学习笔记 || CF985G Team Players

三元环计数

题意

题解

• 当点的度数 $\le \sqrt m$ 时，出度也 $\le \sqrt m$。
• 当点的度数 $> \sqrt m$ 时，假设出度 $> \sqrt m$，那么就有至少 $\sqrt m$ 个点的度数 $> \sqrt m$，显然矛盾。

例题 CF985G Team Players

题意

题解

1. 边数 $\ge0$。
   • 直接暴力数三元组即可。
   • 贡献为 $\sum\limits_{i=1}^ni\times A\times \dbinom{n-i}{2}+\sum\limits_{i=1}^ni\times B\times (i-1)\times(n-i)+\sum\limits_{i=1}^ni\times C\times \dbinom{i-1}{2}$
   • 时间复杂度 $O(n)$。
2. 边数 $\ge 1$。
   • 枚举这条边 $(u,v)$，钦定 $u<v$，考虑第三个点 $w$ 的位置。
   • $w<u$ 时，贡献为 $\sum\limits_{w=1}^{u-1}w\times A+u\times B+v\times C=(u-1)\times (u\times B+v\times C)+\cfrac{u\times(u-1)}{2}\times A$
   • $u<w<v$ 时，贡献为 $\sum\limits_{w=u+1}^{v-1}u\times A+w\times B+v\times C=(u-v-1)\times (u\times A+v\times C)+\cfrac{(u+v)\times(u-v-1)}{2}\times B$
   • $v<w$ 时，贡献为 $\sum\limits_{w=v+1}^{n}u\times A+v\times B+w\times C=(n-v)\times (u\times A+v\times B)+\cfrac{(v+1+n)\times(n-v)}{2}\times C$
   • 时间复杂度 $O(m)$。
3. 边数 $\ge 2$。
   • 枚举两条边的交点 $u$，枚举 $u$ 邻域中的点 $v$，考虑第三个点 $w$ 的位置。钦定 $w<v$。
   • 设 $rk$ 为邻域中编号小于 $u$ 的点的数量，$i$ 为 $v$ 在邻域中的排名，$cntr=\sum\limits_{i\in N(u),i\le rk}i$，$cntv=\sum\limits_{i\in N(u),i<v}i$。
   • 当 $w\le v\le u$ 时，贡献为 $\sum\limits_{w\in N(u),w<v}w\times A+v\times B+u\times C=(i-1)\times(v\times B+u\times C)+cntv*A$
   • 当 $w\le u\le v$ 时，贡献为 $\sum\limits_{w\in N(u),w<u}w\times A+u\times B+v\times C=rk\times(u\times B+v\times C)+cntr*A$
   • 当 $u\le w\le v$ 时，贡献为 $\sum\limits_{w\in N(u),u<w<v}u\times A+w\times B+v\times C=(v-rk-1)\times(u\times A+v\times C)+(cntv-cntr)*B$
   • 时间复杂度 $O(m)$。
4. 边数 $\ge 3$。
   • 其实就是三元环计数。时间复杂度 $O(m\sqrt m)$。

代码

#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const int N=2e5+10;
int n,m,d[N],vis[N];
ll C0,C1,C2,C3,A,B,C;
int fst[N<<1],to[N<<1],nxt[N<<1],ecnt;
void adde(int u,int v){
	ecnt++;
	to[ecnt]=v;
	nxt[ecnt]=fst[u];
	fst[u]=ecnt;
}
struct edge{int u,v;}E[N];
vector<int>e[N];
int main(){
	cin>>n>>m>>A>>B>>C;
	for(int i=1;i<=n;i++){//0
		C0+=(ll)(n-i)*(n-i-1)/2*A*(i-1);
		C0+=(ll)(i-1)*(n-i)*B*(i-1);
		C0+=(ll)(i-1)*(i-2)/2*C*(i-1);
	}
	for(int i=1;i<=n;i++)e[i].push_back(0);
	for(int i=1,u,v;i<=m;i++){//1
		cin>>u>>v;u++,v++;
		d[u]++,d[v]++;
		E[i]=(edge){u,v};
		e[u].push_back(v);
		e[v].push_back(u);
		if(u>v)swap(u,v);
		C1+=(u-1)*((u-1)*B+(v-1)*C)+(ll)(u-2)*(u-1)/2*A;
		C1+=(v-u-1)*((u-1)*A+(v-1)*C)+(ll)(v+u-2)*(v-u-1)/2*B;
		C1+=(n-v)*((u-1)*A+(v-1)*B)+(ll)(v+n-1)*(n-v)/2*C;
	}
	for(int i=1;i<=n;i++)sort(e[i].begin(),e[i].end());
	for(int u=1;u<=n;u++){//2
		ll rk=0,cntr=0,cnt=0;
		for(int i=1;i<=d[u];i++){
			if(e[u][i]<u)rk=i,cntr+=e[u][i]-1;
			else break;
		}
		for(int i=1;i<=d[u];i++){
			int v=e[u][i];
			if(v<u)C2+=(i-1)*((u-1)*C+(v-1)*B)+cnt*A;
			else{
				C2+=(i-rk-1)*((u-1)*A+(v-1)*C)+(cnt-cntr)*B;
				C2+=rk*((u-1)*B+(v-1)*C)+cntr*A;
			}
			cnt+=v-1;
		}
	}
	for(int i=1;i<=m;i++){
		if(d[E[i].u]<d[E[i].v]||(d[E[i].u]==d[E[i].v]&&E[i].u<E[i].v))adde(E[i].u,E[i].v);//注意这一行 
		else adde(E[i].v,E[i].u);
	}
	for(int u=1;u<=n;u++){//3
		for(int i=fst[u];i;i=nxt[i])vis[to[i]]=1;
		for(int i=fst[u];i;i=nxt[i]){
			int v=to[i];
			for(int j=fst[v];j;j=nxt[j]){
				int w=to[j];
				if(vis[w])C3+=(min({u,v,w})-1)*A+(u+v+w-min({u,v,w})-max({u,v,w})-1)*B+(max({u,v,w})-1)*C;
			}
		}
		for(int i=fst[u];i;i=nxt[i])vis[to[i]]=0;
	}
	cout<<C0-C1+C2-C3;
}