专栏文章

住在拔作岛上的贫测机该如何是好

冷冷却心月明かり
P10706题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miorwqau
此快照首次捕获于
2025/12/03 00:09
3 个月前
此快照最后确认于
2025/12/03 00:09
3 个月前
查看原文
联考 NOIP T4，由于莫反细节写错导致 100→0100 \to 0，赫赫，原题 600ms 神人卡常，联考时限放宽数据范围缩小放过虚树做法还是太有素质了。值得一提的是该假做法成功通过你谷非 Subtask 3 随机数据以外的所有数据，/bangbangt。
先把 LCA 限制去掉，我们考虑求出 fpf_p 表示满足条件的 u,vu,v 在 pp 子树内的 au×ava_u \times a_v 的总和，那么 bp=fp−∑q∈son(p)fqb_p=f_p-\sum_{q \in \text{son}(p)} f_q。
然后用莫反把 gcd⁡\gcd 限制去掉。要求不互质数对乘积和，转而考虑求互质数对乘积和。我们考虑一个弱化叫做给定一个序列 {an}\{a_n\} 求出其中所有互质数对乘积和。显然值域上开个桶，接着莫反直接做。具体而言，记 mm 为值域，sis_i 表示值为 ii 的数的总和，那么答案为 ∑i=1msi∑j=1msj[gcd⁡(i,j)=1]\displaystyle\sum_{i=1}^m s_i \sum_{j=1}^m s_j [\gcd(i,j)=1]。莫反后变成 ∑i=1msi∑k∣iμ(k)∑k∣jsj\displaystyle \sum_{i=1}^m s_i \sum_{k\mid i}\mu(k) \sum_{k \mid j} s_j，于是我们先求出 gk=∑k∣isig_k=\sum_{k|i} s_i，然后对每个 ii 枚举因数莫反。把上述过程放到树上就是对每颗子树做，需要支持动态加入一个数求莫反答案，和上述过程本质相同，然后用 dsu on tree 维护求出 fpf_p 做到 O(d(m)nlog⁡n)\mathcal O(d(m)n\log n)。堂堂倒闭 TLE。一个 naive 的优化是注意到如果 μ(i)=0\mu(i)=0 那么他对答案毫无贡献.所以因数只枚举 μ(i)\mu(i) 非零的部分，可以一开始用调和级数复杂度预处理因数 vector。μ(i)\mu(i) 非零的因数个数即为每个质因子只出现 0/10/1 次的因数个数，至多 2ω(m)=642^{\omega(m)}=64 次，复杂度 O(n2ω(m)log⁡n)\mathcal O(n2^{\omega(m)}\log n)，轻微卡常就可通过。
卡常小技巧：处理 μ(i)\mu(i) 非零的因数时不考虑不在原序列内出现过的数，然后轻松通过。
CPP
#include <bits/stdc++.h>
#define ull unsigned long long
#define uint unsigned int
#define LL long long
using namespace std;
const int N = 2e5 + 10;
const int M = 5e5 + 10;
const uint MOD = 998244353;
int n, m = 5e5, A[N]; vector<int> G[N];
int prime[M], ptot; uint mu[M]; bool is[M], vis[M];
vector<int> D[M]; int cnt[M];
void Sieve() {
	mu[1] = 1;
	for (int i = 2; i <= m; i ++) {
		if (!is[i]) { mu[i] = MOD - 1, prime[++ ptot] = i; }
		for (int j = 1; j <= ptot && i * prime[j] <= m; j ++) {
			is[i * prime[j]] = 1, mu[i * prime[j]] = (MOD - mu[i]) % MOD;
			if (i % prime[j] == 0) { mu[i * prime[j]] = 0; break; }
		}
	} 
	return ;
}

uint cur = 0, sum[M], Ans[N];
int sz[N], hson[N], dfn[N], R[N], dfncnt, inv[N]; uint W[N];
void DFS1(int u, int f) {
	sz[u] = 1; dfn[u] = R[u] = ++ dfncnt; inv[dfncnt] = u; W[u] = A[u];
	for (int v : G[u]) if (v != f) {
		DFS1(v, u); if (sz[v] > sz[hson[u]]) hson[u] = v;
		R[u] = R[v]; sz[u] += sz[v]; 
		Ans[u] = (Ans[u] + Ans[v] + 1ull * W[u] * W[v]) % MOD;
		W[u] = (W[u] + W[v]) % MOD;
	} return ;
}
void add(int u, uint k) {
	for (int d : D[u]) {
		cur = (cur + 1ull * mu[d] * sum[d] % MOD * k % MOD) % MOD;
		sum[d] = (sum[d] + k) % MOD; 
	} return ;
}
void del(int u, uint k) {
	for (int d : D[u]) {
		sum[d] = (sum[d] + MOD - k) % MOD; 
		cur = (cur + 1ull * mu[d] * sum[d] % MOD * (MOD - k) % MOD) % MOD;
	} return ;
}
void DFS2(int u, int f, bool kp) {
	for (int v : G[u]) if (v != f && v != hson[u]) DFS2(v, u, false);
	if (hson[u]) { DFS2(hson[u], u, true); }
	for (int v : G[u]) if (v != f && v != hson[u]) 
		for (int i = dfn[v]; i <= R[v]; i ++) add(A[inv[i]], A[inv[i]]);
	add(A[u], A[u]); Ans[u] = (Ans[u] + MOD - cur) % MOD;
	if (!kp) for (int i = dfn[u]; i <= R[u]; i ++) del(A[inv[i]], A[inv[i]]);
}


#define getchar getchar_unlocked
#define putchar putchar_unlocked
int read() {
	int x = 0; char c = getchar();
	for (; !isdigit(c); c = getchar());
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x;
}
void write(int x) {
	if (x >= 10) write(x / 10);
	putchar(x % 10 + 48);
}

int main() {
	freopen(".in", "r", stdin); freopen(".ans", "w", stdout); 
	n = read(); Sieve();
	for (int i = 1; i <= n; i ++) A[i] = read(), vis[A[i]] = 1;
	for (int i = 1, u, v; i < n; i ++) {
		u = read(), v = read(); G[u].push_back(v); G[v].push_back(u);
	}
	for (int i = 1; i <= m; i ++) if (mu[i] != 0)
		for (int j = i; j <= m; j += i) if (vis[j]) cnt[j] ++;
	for (int i = 1; i <= m; i ++) if (vis[i]) D[i].resize(cnt[i]), cnt[i] = 0;
	for (int i = 1; i <= m; i ++) if (mu[i] != 0)
		for (int j = i; j <= m; j += i) if (vis[j]) D[j][cnt[j] ++] = i;
	DFS1(1, 0); DFS2(1, 0, true);
	for (int i = 1; i <= n; i ++)
		for (int j : G[inv[i]]) if (dfn[j] > i) Ans[inv[i]] = (Ans[inv[i]] + MOD - Ans[j]) % MOD;
	for (int i = 1; i <= n; i ++) write(Ans[i]), putchar('\n');
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...