20220502 - 模拟赛 | Final Fantasy = xixike = 人间忽晚，山河已秋

数论，树状数组 + 按右端点排序再扫一遍，树上背包

# A. gcd

考过原题。

一个非常显然的结论（假设 $a > b$ ）：

$\gcd(a, b) <= a - b\\ a \oplus b >= a - b$

那么我们先枚举一个数 $i$ 作为 $\gcd$ ，然后枚举它的倍数 $j\ (2 \times i \leq j \leq n)$ ，判断 $j \oplus (j - i)$ 是否等于 $i$ ，是的话就让答案加 1。

同样有原题（就是多了个多测）。

类似于【HH 的项链】这道题。

考场上的暴力：把每个数的因数全都预处理出来，然后每次查询 $l \sim r$ 时，把 $l \sim r$ 中所有数的因数全都放到桶里，答案就是最大的出现至少两次的数，再整个莫队优化一下。

复杂度我也不知道是多少，反正是过不了 QwQ

现在来说正解：

首先还是要把每个数的因数全都预处理出来，然后把询问按照右端点排序。

从左到右依次枚举每一个数 $a_i$ ，然后枚举 $a_i$ 的所有因数，判断这个因数之前是否出现过（出现过两次及以上就可以当作 $\gcd$ ），如果出现过就把这个因数插到树状数组第 $lastpos$ 位上，维护一个前缀最大值。

注意时刻更新 $lastpos$ 。

查询的时候枚举以当前点 $i$ 为右端点的询问，在树状数组上查询 $q[i].l$ 为左端点的后缀最大值，就是答案了。

	#include <bits/stdc++.h>
	#define pb push_back
	#define fi first
	#define se second

	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 = 1e5 + 10;
	typedef pair<int, int> P;
	int n, m, T;
	int a[N];
	vector <int> num[N];
	vector <P> q[N];

	namespace BIT{
	int c[N];

	inline void add(int x, int y){
	for(; x > 0; x -= x & (-x)) c[x] = max(c[x], y);
	}

	inline int qry(int x){
	int res = 0;
	for(; x <= n; x += x & (-x)) res = max(res, c[x]);
	return res;
	}
	}
	using namespace BIT;

	int lst[N], ans[N];

	inline void solve(){
	for(int i = 1; i <= n; ++i){
	for(auto x : num[a[i]]) add(lst[x], ~lst[x] ? x : 0), lst[x] = i;
	for(auto x : q[i]) ans[x.se] = qry(x.fi);
	}
	}

	inline void Clear(){
	for(int i = 1; i <= n; ++i) q[i].clear();
	memset(ans, 0, sizeof(ans));
	memset(lst, -1, sizeof(lst));
	memset(c, 0, sizeof(c));
	}

	signed main(){
	// freopen("max.in", "r", stdin);
	// freopen("max.out", "w", stdout);
	for(int i = 1; i < N; ++i)
	for(int j = i; j < N; j += i) num[j].pb(i);
	T = read();
	while(T--){
	n = read(), Clear();
	for(int i = 1; i <= n; ++i) a[i] = read();
	m = read();
	for(int i = 1, l, r; i <= m; ++i)
	l = read(), r = read(), q[r].pb(P(l, i));
	solve();
	for(int i = 1; i <= m; ++i) write(ans[i]), puts("");
	}
	return 0;
	}

（ ${\text{\color{black}l\color{Red}{ndjy}}}$ 在 Luogu 上放了道私题，就不放链接了）

非常妙的树形背包。

设 $f_{x, i}$ 表示以 $x$ 为根的子树内与 $x$ 颜色相同的联通块大小为 $i$ 时合法的方案树，不考虑颜色。

设 $sum_x$ 表示以 $x$ 为根的子树内， $col_x \neq col_{fa[x]}$ 且其他所有条件都符合的方案数，即：

$sum_x = \sum_{i = 1}^{\min(l, siz[x])} f_{x, i} \times (k - 1)$

乘 $(k - 1)$ 是因为不能和父亲的颜色相同。

然后再来看 $f_{x, i}$ 如何转移。

分两种情况讨论：

$x$ 的儿子 $y$ 和 $x$ 颜色相同，那么就是树上背包板题了，先枚举与 $x$ 颜色相同的联通块大小，然后枚举 $y$ 子树内与 $y$ 颜色相同的联通块大小（此时 $col_x = col_y$ ），那么有：
$f_{x, i} = \sum_{j}f_{x, j} \times f_{y, i - j}$
儿子 $y$ 的颜色与 $x$ 不相同，那就很简单了，直接令 $f_{x, i}$ 乘上 $sum_y$ 再加上刚才背包计算出来的结果就行。
（至于为什么能直接乘 $sum_y$ ，我只能说 $sum_y$ 的定义实在是巧妙）

注意最后的答案是 $\sum\limits_{i = 1}^l (f_{1, i} \times k)$ 。

	#include <bits/stdc++.h>
	#define pb push_back
	#define get_B(x) x / B

	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 = 2e5 + 10;
	const int mod = 998244353;
	int n, k, l, ans;
	vector <int> g[N];
	int f[N][210], siz[N], sum[N];

	inline int add(int x) {return x >= mod ? x - mod : x;}
	inline int mul(int a, int b) {return 1ll * a * b % mod;}

	inline void dfs(int x, int fa){
	f[x][1] = siz[x] = 1;
	for(auto y : g[x]){
	if(y == fa) continue;
	dfs(y, x);
	int sizu = siz[x]; siz[x] += siz[y];
	for(int i = min(l, siz[x]); i >= 1; --i){
	int res = 0;
	for(int j = min(i - 1, siz[y]); j >= max(1, i - sizu); --j)
	res = add(res + mul(f[x][i - j], f[y][j]));//x 与 y 颜色相同
	f[x][i] = add(res + mul(f[x][i], sum[y]));//x 与 y 颜色不同
	}
	}
	if(siz[x] == 1) sum[x] = k - 1;
	else for(int i = min(l, siz[x]); i >= 1; --i) sum[x] = add(sum[x] + mul(f[x][i], k - 1));
	}

	signed main(){
	n = read(), k = read(), l = read();
	for(int i = 1; i < n; ++i){
	int u = read(), v = read();
	g[u].pb(v), g[v]. pb(u);
	}
	dfs(1, 0);
	for(int i = 1; i <= l; ++i) ans = add(ans + f[1][i]);
	write(mul(ans, k)), puts("");
	return 0;
	}

还不会，咕咕咕。