LOJ502 题解

link

给定一棵有根树，每个点有颜色，每次加一个叶子，询问叶子到根的路径是不是所有颜色出现次数都是 $3$ 的倍数，不是的话再问是不是只有一个颜色不是 $3$ 的倍数，是的话输出这个颜色。

$n \le 10^6$，$m\le 2\times 10^6$。

考虑如果是 $2$ 的倍数，那么可以给每个颜色随机一个权值然后维护到根每个叶子的异或和，异或和为 $0$ 代表出现次数都是偶数，否则可以进行一个希的哈，查询是否存在这个异或值对应的颜色。

然后考虑 $3$ 的倍数，我们需要一个类似二进制异或的运算，连续三次与自己运算变为 $0$。类比异或不难想到**三进制不进位加法。**然后这题就做完了，算法的大致流程是：

• 对于每个颜色随机一个三进制值，并把这个值放入哈希表；
• 每插入一个叶子，计算出它到根的三进制不进位加法值；
• 如果为 $0$ 输出则所有颜色都是 $3$ 的倍数；
• 否则查询哈希表，寻找是否有匹配的颜色。

这题卡空间，哈希需要链表实现差评，具体实现还参考了官方题解，哪里也有随机化概率的具体计算和证明。

还有一个小 TIP：正常的 rand() 只能生成 $[0,32768]$ 的随机数，有时候需要较大的随机数非常麻烦。从 c++11 开始提供了一个叫 mt19937 的随机数，比 rand() 快更随机还大。简单的用法：

mt19937 rd(time(0)); // 定义和播种
/*
mt19937 范围是 unsigned int
mt19937_64 更大，unsigned long long
*/
int foo = rd(); // 生成随机数
/*=============================*/
uniform_int_distribution<int>dist(1, n);
int foo = dist(rd); // 生成 [1,n] 的随机数

激动人心的代码时间~

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = x * 10 + (c & 15), c = getchar();
	return f ? -x : x;
}

#define N 1000005
#define M 2000005
int n, m;
ull hs[N], val[M];
mt19937_64 rd(time(0));

struct trinum {
	int a[2188][2188];
	trinum() { memset(a, 0, sizeof a);
		for (int i = 0; i < 2187; i ++) {
			for (int j = 0; j < 2187; j ++) {
				int x = i, y = j, v = 1;
				for (int k = 0; k < 7; k ++) {
					int t = (x % 3 + y % 3) % 3;
					a[i][j] += t * v, x /= 3, y /= 3, v *= 3;
				}
			}
		}
	}
	ull ran() { return rd() % 12157665459056928801ull; }
	ull tor(ull x, ull y) const {
		ull r = 0, v = 1;
		for (int i = 0; i < 6; i ++) {
			r += a[x % 2187][y % 2187] * v;
			x /= 2187, y /= 2187, v *= 2187;
		}
		return r;
	}
} trin;

struct hash {
	int a[M], nex[M], hed[M], tot, m; ull v[M];
	hash() : m(1999993), tot(0) {
		memset(hed, 0, sizeof hed);
		memset(nex, 0, sizeof nex);
	}
	void add(ull x, int i) {
		a[++ tot] = i;
		v[tot] = x;
		nex[tot] = hed[x % m];
		hed[x % m] = tot;
	}
	int ask(ull x) {
		for (int i = hed[x % m]; i; i = nex[i]) {
			if (v[i] == x) return a[i];
		}
		return -2;
	}
} hat;

int main() {
	srand(time(NULL));
	n = read(), m = read();
	for (int i = 1; i <= n; i ++) {
		hs[i] = trin.ran();
		hat.add(hs[i], i);
		hat.add(trin.tor(hs[i], hs[i]), i);
	}
	val[0] = 0;
	for (int i = 1, la = 0; i <= m; i ++) {
		int u = read() ^ la, fa = read() ^ la;
		val[i] = trin.tor(hs[u], val[fa]);
		la = val[i] ? hat.ask(val[i]) : -1;
		printf("%d\n", la);
	}
	return 0;
}