UOJ最强跳蚤

Ｐroblem

给一颗树，边有边权。求经过的边权积为完全平方数的路径条数。

(n<1e5,a_i<1e8)

Ｓolution

emm

可以看出要用点分治。

可是桶不好开。

所以要考虑转换。

我们可以将任意一个数X这样表示。

(X = p_1^{a_1}* p_2^{a_2} * p_3^{a_3}) ......

(p) 为质数。

然后我们给所有(p_i) 赋一个随机值(h(p_i))。

定义 (F(X)) 为所有 (a_i为奇数的h(p_i)的异或和)

所以，我们可以得到。

当且仅当 (F(x) = 0) 时，(x) 为完全平方数。

所以我们可以把 (A,B) 两数的积用 (F(A)oplus F(B)) 表示，因为我们仅需要知道一个数是否为完全平方数。

然后这题就完了。

好吧，还有一些细节。

比如 (h(p_i)) 的随机值要是 (long~long) 范围的。这样才能保证正确性。

还有，因为 (a_i<1e8) 不能用线性筛，所以我们要筛出 (1e4) 以内的质数，然后对所有数用 (frac {sqrt a_i}{ln n}) 的复杂度算出 (F(a_i)) 。

还有一点很重要，桶不能用 (map) ，只能用 (hash) 。

先上一份自己打的，但是被 (hack) 数据卡T了的代码：

#pragma GCC optimize(2)
#pragma G++ optimize(2)
#pragma GCC optimize(3)
#pragma G++ optimize(3)
#include <bits/stdc++.h>

using namespace std;

#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline T read()
{
	register T sum(0), fg(1);
	register char ch(getchar());
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) - 48 + ch;
	return sum * fg;
}

typedef long long LL;
typedef pair<int, LL> pii;
const int Maxn = 1e5 + 10, Maxv = 1e4 + 10, mod = 2333333;
vector <pii> Map[Maxn];
unordered_map <LL, LL> mp,book;
int pre[Maxn], top, Top, siz[Maxn], n;
bool vis[Maxn],bk[Maxn + 10];
long long p[Maxn] ,del[Maxn], pre_rand[Maxn + 10], stk[Maxn], ans;
LL Rand(){
	int res = rand(),res2 = rand();
	LL tmp = 1ll * res * res2;
	while(tmp <= 0) {
		if(res > res2) swap(res,res2);
		res = rand();
		tmp = 1ll * res * res2;
	}
	return tmp;
}
vector<pii> h[mod + 10];
int ask(LL number){
	int now = number % mod;
	for (int i = h[now].size() - 1;i >= 0; --i){
		if(h[now][i].snd == number)
			return h[now][i].fst;
	}
	return 0;
}
void add(LL number, int d){
	int now = number % mod;
	bool fl = 1;
	for (int i = h[now].size() - 1;i >= 0; --i){
		if(h[now][i].snd == number)
			h[now][i].fst += d,fl = 0;
	}
	if(fl)h[now].push_back((pii){d,number});
}
void init(){
	srand(19260817);
	for (int i = 2;i <= Maxv; ++i){
		if(!bk[i]){
			pre[++Top] = i;
			pre_rand[Top] = Rand();
			for (int j = i << 1; j <= Maxv; j += i) bk[j] = 1;
		}
	}
}
void div_siz(int now, int pa){
	siz[now] = 1;
	for (int i = Map[now].size() - 1; i >= 0; --i){
		int nxt = Map[now][i].fst;
		if(vis[nxt] || nxt == pa)continue;
		div_siz(nxt, now);
		siz[now] += siz[nxt];
	}
}
int div_rt(int now,int pa, int tot_siz){
	bool fg = 1;
	for (int i = Map[now].size() - 1; i >= 0; --i){
		int nxt = Map[now][i].fst;
		if(vis[nxt] || nxt == pa)continue;
		int p = div_rt(nxt,now,tot_siz);
		if(p) return p;
		if((siz[nxt] << 1) > tot_siz) fg = 0;
	}
	if((tot_siz - siz[now] << 1) > tot_siz) fg = 0;
	if(fg) return now;
	return 0;
}
LL get_p(int number){
	LL res = 0;
	for (int i = 1; i <= Top && pre[i] <= number; ++i){
		while(number % pre[i] == 0){
			res ^= pre_rand[i];
			number /= pre[i];
		}
	}
	if (number > 1){
		if (!mp[number]){ 
			mp[number] = Rand();
		}
		res ^= mp[number];
	}
	return res;
}
void get_dis(int now, int pa){
	stk[++top] = p[now];
	for (int i = Map[now].size() - 1; i >= 0; --i){
		int nxt = Map[now][i].fst;
		if(vis[nxt] || nxt == pa)continue;
		p[nxt] = p[now] ^ Map[now][i].snd;
		get_dis(nxt, now);
	}
}
void calc(int now){
	int tot = 0;
	for (int i = Map[now].size() - 1; i >= 0; --i){
		int nxt = Map[now][i].fst;
		if(vis[nxt]) continue;
		top = 0;
		p[nxt] = Map[now][i].snd;
		get_dis(nxt, now);
		for (int j = 1; j <= top; ++j){
			ans += ask(stk[j]);
		}
		for (int j = 1; j <= top; ++j)
			add(stk[j], 1), del[++tot] = stk[j];
	}
	for (int i = 1; i <= tot; ++i)
		add(del[i], -1);
}
void div_solve(int now){
	div_siz(now, 0), now = div_rt(now, 0, siz[now]), calc(now);
	vis[now] = 1;
	for (int i = Map[now].size() - 1; i >= 0; --i){
		int nxt = Map[now][i].fst;
		if(!vis[nxt]) div_solve(nxt);
	}
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
#endif
	n = read<int>();
	init();
	for (int i = 1; i < n; ++i){
		int x = read<int>(), y = read<int>(), w = read<int>();
		LL w0 = get_p(w);
		Map[x].push_back((pii){y, w0});
		Map[y].push_back((pii){x, w0});
	}
	add(0,1);
	div_solve(1);
	printf("%lld
",2ll * ans);
	return 0;
}

这份代码，卡了半年常，就是卡不过。

后来把手写哈希换成hash_table就过了。

感谢fatesky大佬的帮助！！！

#include <bits/stdc++.h>

using namespace std;

#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline T read()
{
	register T sum(0), fg(1);
	register char ch(getchar());
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) - 48 + ch;
	return sum * fg;
}

typedef long long LL;
typedef pair<int, LL> pii;
const int Maxn = 1e5 + 10, Maxv = 1e4 + 10, mod = 2333333;
vector <pii> Map[Maxn];
map <LL, LL> mp,book;
int pre[Maxn], top, Top, siz[Maxn], n;
bool vis[Maxn],bk[Maxn + 10];
long long p[Maxn],del[Maxn], pre_rand[Maxn + 10], stk[Maxn], ans;
LL Rand(){
	int res = rand(),res2 = rand();
	LL tmp = 1ll * res * res2;
	while(tmp <= 0) {
		if(res > res2) swap(res,res2);
		res = rand();
		tmp = 1ll * res * res2;
	}
	return tmp;
}

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

namespace DIV
{
	cc_hash_table<LL, int> H;

	void init(){
		srand(19260817);
		for (int i = 2;i <= Maxv; ++i){
			if(!bk[i]){
				pre[++Top] = i;
				pre_rand[Top] = Rand();
				for (int j = i << 1; j <= Maxv; j += i) bk[j] = 1;
			}
		}
	}
	void div_siz(int now, int pa){
		siz[now] = 1;
		for (int i = Map[now].size() - 1; i >= 0; --i){
			int nxt = Map[now][i].fst;
			if(vis[nxt] || nxt == pa)continue;
			div_siz(nxt, now);
			siz[now] += siz[nxt];
		}
	}
	int div_rt(int now,int pa, int tot_siz){
#define p zjmsb
		bool fg = 1;
		for (int i = Map[now].size() - 1; i >= 0; --i){
			int nxt = Map[now][i].fst;
			if(vis[nxt] || nxt == pa)continue;
			int p = div_rt(nxt,now,tot_siz);
			if(p) return p;
			if((siz[nxt] << 1) > tot_siz) fg = 0;
		}
		if((tot_siz - siz[now]) * 2 > tot_siz) fg = 0;
		if(fg) return now;
		return 0;
#undef p
	}
	LL get_p(int number){
		LL res = 0;
		for (int i = 1; i <= Top && pre[i] <= number; ++i){
			while(number % pre[i] == 0){
				res ^= pre_rand[i];
				number /= pre[i];
			}
		}
		if (number > 1){
			if (!mp[number]) mp[number] = Rand();
			res ^= mp[number];
		}
		return res;
	}
	void get_dis(int now, int pa){
		stk[++top] = p[now];
		for (int i = Map[now].size() - 1; i >= 0; --i){
			int nxt = Map[now][i].fst;
			if(vis[nxt] || nxt == pa)continue;
			p[nxt] = p[now] ^ Map[now][i].snd;
			get_dis(nxt, now);
		}
	}
	void calc(int now){
		H.clear();
		++H[0];
		int tot = 0;
		for (int i = Map[now].size() - 1; i >= 0; --i){
			int nxt = Map[now][i].fst;
			if(vis[nxt]) continue;
			top = 0;
			p[nxt] = Map[now][i].snd;
			get_dis(nxt, now);
			for (int j = 1; j <= top; ++j) if(H.find(stk[j]) != H.end()) ans += H[stk[j]];
			for (int j = 1; j <= top; ++j) ++H[stk[j]];
		}
	}
	void div_solve(int now){
		div_siz(now, 0), now = div_rt(now, 0, siz[now]), calc(now);
		vis[now] = 1;
		for (int i = Map[now].size() - 1; i >= 0; --i){
			int nxt = Map[now][i].fst;
			if(!vis[nxt]) div_solve(nxt);
		}
	}
}
using namespace DIV;

int main()
{
#ifndef ONLINE_JUDGE
	freopen("zjm.in", "r", stdin);
	freopen("zjm.out", "w", stdout);
#endif
	n = read<int>();
	init();
	for (int i = 1; i < n; ++i){
		int x = read<int>(), y = read<int>(), w = read<int>();
		LL w0 = get_p(w);
		Map[x].emplace_back(y, w0);
		Map[y].emplace_back(x, w0);
	}
	div_solve(1);
	printf("%lld
",2ll * ans);
	return 0;
}