好吧我觉得是脑子,别人觉得是套路$qwq$


这道题相当于是求除了$u,v$两点互相连接,所连的点相同的点对$(u,v)$

我们首先每个点一个随机权值,对于$u$点记为$w[u]$,然后记与$u$点相连的点的异或和为$hsh[u]$

分类:

  1. 若$u,v$相连,则$u,v$是朋友满足$(hsh[u]^w[v])==(hsh[v]^w[u])$;
  2. 若$u,v$不相连,则$u,v$是朋友满足$hsh[u]==hsh[v]$;

对于第一种情况,直接枚举每条边上的两点就行了;对于第二种情况,先把$hsh$数组$sort$一遍,然后对于$hsh$相同的点来说,设共有$cnt$个点的$hsh[u]==c$,$c$是某定值,则答案个数是$C_{cnt}^2$。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define fr first
#define sc second
#define ull unsigned long long
#define ll long long
#define R register int
using namespace std;
namespace Fread {
static char B[<<],*S=B,*D=B;
#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
}
}using Fread::g;
const int N=;
pair<int,int> e[N];
int n,m; ll ans;
ull vl[N],hsh[N];
signed main() {
#ifdef JACK
freopen("NOIPAK++.in","r",stdin);
#endif
n=g(),m=g(); srand();
for(R i=;i<=n;++i) vl[i]=(ull)rand()*rand()*rand()*rand();
for(R i=,u,v;i<=m;++i) u=e[i].fr=g(),v=e[i].sc=g(),hsh[u]^=vl[v],hsh[v]^=vl[u];
for(R i=;i<=m;++i) ans+=(int)((hsh[e[i].fr]^vl[e[i].sc])==(hsh[e[i].sc]^vl[e[i].fr]));
sort(hsh+,hsh+n+); R cnt=; for(R i=;i<=n;++i) {
++cnt; if(i==n||hsh[i]!=hsh[i+]) ans+=(ll)cnt*(cnt-)/,cnt=;
} printf("%lld",ans);
}

2019.06.10

最新文章

  1. Get sdcard directory by adb
  2. 团队开发——冲刺1.b
  3. SVM之SMO最小序列
  4. Flex 选项卡加载方式简介
  5. URAL1017. Staircases
  6. Hacking Secret Ciphers with Python翻译序言
  7. linq to sql 博客集锦
  8. bootstrap 响应式导航条模板(含下拉菜单,弹出框)
  9. android 面试之listview
  10. centos 7 Chrony 集群同步时间
  11. Javascript高级编程学习笔记(16)—— 引用类型(5) Function类型
  12. Promise.all和Promise.race区别,和使用场景
  13. 【VMware vSphere】详解VDP安装步骤
  14. The Little Prince-12/10
  15. Linux用户创建/磁盘挂载相关命令
  16. [CC-XXOR]Chef and Easy Problem
  17. go语言之进阶篇字符串操作常用函数介绍
  18. C# 历史曲线控件 基于时间的曲线控件 可交互的高级曲线控件 HslControls曲线控件使用教程
  19. 学习GIT 版本控制的好去处 另GDB资料
  20. KBEngine 服务器端-loginapp-协议构建、解析执行详细介绍

热门文章

  1. bzoj1000~1025
  2. mysql调优参考笔记
  3. 【LeetCode】060. Permutation Sequence
  4. Springboot监控之一:SpringBoot四大神器之Actuator之2--spring boot健康检查对Redis的连接检查的调整
  5. JSP介绍(4)--- JSP 过滤器
  6. docker Get started part 4: Accessing your cluster cannot curl
  7. python 基础 操作文件和目录
  8. Ok6410裸机驱动学习(一)开发工具
  9. 27.【转载】挖洞技巧:如何绕过URL限制
  10. javascript 数组中出现的次数最多的元素