2019牛客暑期多校训练营(第九场)E.All men are brothers(数学)

题目链接

大意:现在有n个人,每个回合都有一对人成为朋友,让你在首回合开始前和每回合结束后输出选4个人,每个人都不是朋友的方案。
思路:显然正着的情况我们不好讨论,我们可以计算出不合法的情况,然后用全部的减去不合法的。
全部的显然是 C ( n 4 ) C(_n^4) C(n4),
不合法的情况我们分几类出来
x表示朋友组的人数
1.从所有大于等于2的一组朋友选2个人,另外的随便选两个 x 2 C ( x 2 ) C ( n x 2 ) \sum_{x\geq2}C(_x^2)*C(_{n-x}^2) x2C(x2)C(nx2)
2.从所有大于等于3的一组朋友选3个人,另外的随便选一个 x 3 C ( x 3 ) ( n x ) \sum_{x\geq3}C(_x^3)*(n-x) x3C(x3)(nx)
3从所有大于等于4的一组朋友选4个人 x 4 C ( x 4 ) \sum_{x\geq4}C(_x^4) x4C(x4)
我们注意到2个人的情况会有多余的,我们要减去选的两个都是大于2人的朋友组中 C ( x 2 ) C ( y 2 ) , x = 2 , y = 2 \sum C(_x^2)*\sum C(_y^2),x=2,y=2 C(x2)C(y2),x=2,y=2
那么我们每次维护几个变量就行

细节见代码

#include<bits/stdc++.h>

#define LL __int128
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
int n,m,f[N];
int find(LL x){
	return f[x]==x?x:f[x]=find(f[x]);
}
LL get(LL x){
	return 1ll*x*(x-1)*(x-2)*(x-3)/24;
}
LL g2(LL x){
	return 1ll*x*(x-1)/2;
}
LL g3(LL x){
	return 1ll*(x-1)*x*(x-2)/6;
}
int siz[N];
LL T[5],S,Q,F,P;

void add(int x){
	if(siz[x]==2){
		F+=T[2]*g2(siz[x]);
		T[2]+=g2(siz[x]);
		Q+=g2(P-siz[x])*g2(siz[x]);
	}
	if(siz[x]==3){
		F+=T[2]*g2(siz[x]);
		T[2]+=g2(siz[x]);
		S-=g3(siz[x])*siz[x];
		Q+=g2(P-siz[x])*g2(siz[x]);
		T[3]+=g3(siz[x]);
	}
	if(siz[x]>=4){
		F+=T[2]*g2(siz[x]);
		T[2]+=g2(siz[x]);
		S-=g3(siz[x])*siz[x];
		Q+=g2(P-siz[x])*g2(siz[x]);
		T[3]+=g3(siz[x]);		
		T[4]+=get(siz[x]);		
	}
}
void del(int x){
	if(siz[x]==2){
		T[2]-=g2(siz[x]);
		F-=T[2]*g2(siz[x]);
		Q-=g2(P-siz[x])*g2(siz[x]);
	}
	if(siz[x]==3){
		T[2]-=g2(siz[x]);
		S+=g3(siz[x])*siz[x];
		F-=T[2]*g2(siz[x]);
		Q-=g2(P-siz[x])*g2(siz[x]);
		T[3]-=g3(siz[x]);
	}
	if(siz[x]>=4){
		T[2]-=g2(siz[x]);
		S+=g3(siz[x])*siz[x];
		F-=T[2]*g2(siz[x]);
		Q-=g2(P-siz[x])*g2(siz[x]);
		T[3]-=g3(siz[x]);		
		T[4]-=get(siz[x]);		
	}
}
void print(LL x)//输出
{
    if(x < 0)
    {
        x = -x;
        putchar('-');
    }
     if(x > 9) print(x/10);
    putchar(x%10 + '0');
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)f[i]=i,siz[i]=1;
	print(get(n));
	cout<<'\n';
	LL M=get(n);
	P=n;
	for(int i=1;i<=m;i++){
		int s,t;
		cin>>s>>t;
		int x=find(s);
		int y=find(t);
		if(x!=y){
			f[y]=x;
			n--;
			del(x);
			del(y);
			siz[x]+=siz[y];
			add(x);
		}
		if(n<4)cout<<0<<'\n';
		else{
			LL res=M;
			res-=T[3]*P+S;
			res-=T[4];
			res-=Q-F;
			print(res);
			cout<<'\n';
		}
	}	
	return 0;
}
全部评论

相关推荐

苍蓝星上艾露:这简历。。。可以试试我写的开源简历优化工具https://github.com/weicanie/prisma-ai
点赞 评论 收藏
分享
07-25 11:26
清华大学 Java
打开电脑,思绪又回到了7月份刚开始的时候,感觉这个月过的如梦如幻,发生了太多事,也算是丰富了我本就是平淡的人生吧太早独立的我习惯了一切都是自己做决定,拥有绝对的决定权,而且永远不会听取别人的建议。我就是那个恋爱四年出轨的男主啦,感觉既然在牛客开了这个头,那我就要做个有始有终的人。从我出轨到结束再到和女朋友和好如初真的太像一场梦了,短短的一个月我经历了太多,也成长了很多,放下了那些本就不属于我的,找回了那些我不该放弃的。我的人生丰富且多彩,但人不能一直顺,上天总会让你的生活中出点乱子,有好有坏,让你学会一些东西,让你有成长。我和女朋友的恋爱四年太过于平淡,日常除了会制造一些小浪漫之外,我们的生活...
段哥亡命职场:不得不说,我是理解你的,你能发出来足见你是个坦诚的人,至少敢于直面自己的内心和过往的过错。 这个世界没有想象中那样非黑即白,无论是农村还是城市,在看不见的阴影里,多的是这样的事。 更多的人选择站在制高点去谩骂,一方面是社会的道德是需要制高点的,另一方面,很多人不经他人苦,却劝他人善。 大部分的我们,连自己生命的意义尚且不能明晰,道德、法律、困境,众多因果交织,人会迷失在其中,只有真的走出来之后才能看明白,可是没走出来的时候呢?谁又能保证自己能走的好,走的对呢? 可是这种问题有些人是遇不到的,不去追寻,不去探寻,也就没了这些烦恼,我总说人生的意义在过程里,没了目标也就没了过程。 限于篇幅,没法完全言明,总之,这世界是个巨大的草台班子,没什么过不去了,勇敢面对,革故鼎新才是正确,祝你早日走出来。查看图片
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务