PerfectPan
;

UOJ 192 最强跳蚤

July 31, 2018

题目链接http://uoj.ac/contest/28/problem/192

题意:略。

思路:完全平方数意味着这个数里面质因子出现次数均为偶数,由又异或具有差分的特性,所以我们可以对每个点分解质因数,求出这个点到根每个质因子数的前缀异或和,然后只要两个点每个质因子数前缀异或和相异或后为 00 就说明这个质因子数在这个路径的异或和的权值上出现了偶数次,只要每个质因子都如此即可保证这条路径权值异或和是完全平方数。但这样直接暴力维护肯定不行,因为权值太大了,质因子数很多很多,所以我们考虑对一个质因子数随机一个 [0,264)[0,2^{64}) 里的权值,然后这个条边权就相当于分解质因子后权值的异或和,我们再求前缀异或和,只要两个点异或和相等那么两个点的简单路径权值一定是完全平方数,排个序扫一下就可以了。随机的正确性就在于冲突性很小,可以忽略不计。

#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
typedef unsigned long long ull;
const int N=1e4+10;
int n,i,j,p,u,v,w,primes[N];
ull val[N],sum[N*10]; 
map<int,ull>mp;
vector<pair<int,int> >G[N*10];
ull get(){return (ull)rand()*rand();}
ull getSingleHash(int x){
	if (mp.find(x)!=mp.end()) return mp[x];
	return mp[x]=get();
}
ull getHash(int x){
	ull ret=0;
	for (int i=1;i<=primes[0];i++){
		if (x<primes[i]) break;
		if (x%primes[i]==0){
			while (x%primes[i]==0){
				x/=primes[i];
				ret^=val[i];
			}
		}
	}
	if (x>1) ret^=getSingleHash(x);
	return ret;
}
void init(){
	srand((unsigned long long)new char);
	for (int i=2;i<=10000;i++){
		if (!primes[i]) primes[++primes[0]]=i;
		for (int j=1;j<=primes[j]&&i*primes[j]<=10000;j++){
			primes[i*primes[j]]=1;
			if (i%primes[j]==0) break;
		}
	}
	for (int i=1;i<=primes[0];i++) val[i]=get();
}
void dfs(int u,int f){
	for (int i=0;i<(int)G[u].size();i++){
		int v=G[u][i].first;
		if (v==f) continue;
		sum[v]=sum[u]^getHash(G[u][i].second);
		dfs(v,u);
	}
}
int main(){
	init();
	scanf("%d",&n);
	for (i=1;i<n;i++){
		scanf("%d%d%d",&u,&v,&w);
		G[u].PB(MP(v,w));
		G[v].PB(MP(u,w));
	}
	dfs(1,0);
	sort(sum+1,sum+1+n);
	long long ans=0;
	for (i=1,p;i<=n;i=p){
		p=n+1;
		for (j=i+1;j<=n;j++){
			if (sum[j]!=sum[i]){
				p=j;
				break;
			}
		}
		ans+=1LL*(p-i)*(p-i-1);
	}
	printf("%lld\n",ans);
	return 0;
}

Yiming Pan

Written by Yiming Pan who lives and works in Hangzhou China. Welcome follow me on Github

Cannot load comments. Please check you network.