数论，树的直径 + 优化建图，01trie 及其特殊操作

# A. 常中 20181205T1-Simple

刚开始以为是扩展欧几里得定理然后乱搞，然后去测了一发大样例，结果挂了……

于是重新观察题目，原式： $nx + my = c$ ，假设有一条数轴。

当 $y = 0$ 时，可以覆盖 $n, 2n, 3n...$
当 $y = 1$ 时，可以覆盖 $n + m, 2n + m, 3n + m...$

不难发现，覆盖的点中一定会有重复的，那么哪些重复了呢？

当 $an = bm$ 时会重复，此时 $b = a\frac nm$ 。

由于 $b$ 为整数，且 $a$ 要尽量小，所以 $a = \frac{m}{\gcd(n, m)}$ ，暴力枚举 $a$ 即可。

$code$

	#include <bits/stdc++.h>
	#define ll long long

	using namespace std;

	namespace IO{
	inline ll read(){
	ll x = 0;
	char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x;
	}

	template <typename T> inline void write(T x){
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	int T;
	ll n, m, q;

	inline ll gcd(ll a, ll b){
	return !b ? a : gcd(b, a % b);
	}

	int main(){
	T = read();
	while(T--){
	n = read(), m = read(), q = read();
	ll d = n / gcd(n, m), ans = 0;
	for(ll i = 0; i < d && q - i * m >= 0; ++i) ans += (q - i * m) / n + 1;
	write(q - ans + 1), puts("");
	}
	return 0;
	}

# B. 常中 20181205T2-Walk

考虑枚举权值 $i$ ，计算权值为 $i$ （或 $i$ 的倍数）的路径中最长的长度是多少，计算最长长度直接跑个树的直径就完了。

但是如果每次都枚举所有边建图的话复杂度是过不去的，所以我们考虑优化建图过程。

类似于前向星的思想，我们用 $h[i]$ 记录是 $i$ 倍数的边，然后建图的时候直接跑 $h[i]$ 即可。

$code$

	#include <bits/stdc++.h>
	#define int long long

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0;
	char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x;
	}

	template <typename T> inline void write(T x){
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 1e6 + 10;
	const int M = 1e6;
	int n, m;
	struct node{
	int u, v, nxt;
	}edge[N << 1], e[N << 1];
	int head[N], tot, h[N], cnt;
	int stk[N << 1], top;

	inline void Add(int x, int y, int z){
	e[++cnt] = (node){x, y, h[z]};
	h[z] = cnt;
	}

	inline void add(int x, int y){
	edge[++tot].v = y, edge[tot].nxt = head[x];
	head[x] = tot;
	stk[++top] = x;
	}

	int maxl, tim = 1, vis[N];

	int dfs(int u) {
	int maxc = 0;
	vis[u] = tim;
	for (int v, j = head[u]; j; j = edge[j].nxt)
	if (vis[v = edge[j].v] != tim) {
	int tmpc = dfs(v);
	maxl = max(maxl, maxc + tmpc + 1);
	maxc = max(maxc, tmpc + 1);
	}
	return maxc;
	}

	int ans[N];

	inline void solve(int val){
	for(int i = 1; i <= top; ++i)
	if(vis[stk[i]] != tim) dfs(stk[i]);
	ans[maxl] = val;
	}

	inline void clear(){
	for(int j = 1; j <= top; ++j) head[stk[j]] = 0;
	tot = maxl = top = tot = 0;
	}

	signed main(){
	// freopen("B.in", "r", stdin);
	// freopen("B.out", "w", stdout);
	n = read();
	for(int i = 1; i < n; ++i){
	int u = read(), v = read(), w = read();
	Add(u, v, w), m = max(m, w);
	}
	for (int i = 1; i <= M; i++, tim++) {
	for (int j = i; j <= M; j += i)
	for (int k = h[j]; k; k = e[k].nxt)
	add(e[k].u, e[k].v), add(e[k].v, e[k].u);
	for (int j = 1; j <= top; j++)
	if (vis[stk[j]] != tim) dfs(stk[j]);
	ans[maxl] = i;
	clear();
	}
	for(int i = n - 1; i > 0; --i) ans[i] = max(ans[i], ans[i + 1]);
	for(int i = 1; i <= n; ++i) write(ans[i]), puts("");
	return 0;
	}

# C. 树

这题就比较有意思了。

看到求异或和，肯定想到要用 $01trie$ ，我们需要支持子树加 1，合并 $01trie$ ，求区间异或和。

$val$ ：表示权值。
$cnt$ ：表示从当前点到根的 1 的个数的奇偶性。

# 子树加 1

左子树会变成右子树，右子树变成左子树，所以就交换一下即可。

如果交换之后左子树还有值，相当于需要进位，继续加即可。

# 合并 01trie

类似于线段树合并（甚至更简单）。

~~直接合并即可。~~

# 区间异或和

01trie 基操，不多说了吧。

$code$

	#include <bits/stdc++.h>
	#define ls(x) t[x].ch[0]
	#define rs(x) t[x].ch[1]
	#define ll long long

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0;
	char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x;
	}

	template <typename T> inline void write(T x){
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 6e5 + 10;
	int n, cnt;
	int a[N];
	vector <int> g[N];

	struct Trie{
	int val, cnt, ch[2];
	}t[N * 27];
	int rt[N];

	void update(int x) {
	t[x].cnt = t[x].val = 0;
	if(ls(x)) t[x].cnt ^= t[ls(x)].cnt, t[x].val ^= (t[ls(x)].val << 1);
	if(rs(x)) t[x].cnt ^= t[rs(x)].cnt, t[x].val ^= (t[rs(x)].val << 1) \| t[rs(x)].cnt;
	}

	inline void insert(int &x, int val, int dep){
	if(!x) x = ++cnt;
	if(dep > 20) return t[x].cnt ^= 1, void();
	insert(t[x].ch[val & 1], val>> 1, dep + 1), update(x);
	}

	inline void add(int x){
	swap(ls(x), rs(x));
	if(ls(x)) add(ls(x));
	update(x);
	}

	inline int merge(int x, int y){
	if(!x \|\| !y) return x \| y;
	t[x].val ^= t[y].val, t[x].cnt ^= t[y].cnt;
	ls(x) = merge(ls(x), ls(y));
	rs(x) = merge(rs(x), rs(y));
	return x;
	}

	ll ans;

	inline void dfs(int x){
	for(auto y : g[x]) dfs(y), rt[x] = merge(rt[x], rt[y]);
	add(rt[x]), insert(rt[x], a[x], 0);
	ans += 1ll * t[rt[x]].val;
	}

	signed main(){
	// freopen("P6623.in","r",stdin);
	// freopen("P6623.out","w",stdout);
	n = read();
	for(int i = 1; i <= n; ++i) a[i] = read();
	for(int i = 2; i <= n; ++i) g[read()].push_back(i);
	dfs(1);
	write(ans), puts("");
	return 0;
	}

# A. 常中 20181205T1-Simple

# B. 常中 20181205T2-Walk

# C. 树

# 子树加 1

# 合并 01trie

# 区间异或和

AT2006 [AGC003F] Fraction of Fractal 题解

20220212