CVBB ACM Team

• 分类：

• 题意：

• 题解：

• comment：

• 分类：

• 题意：

• 题解：

• comment：

• 分类：莫比乌斯反演，虚树。

• 题意：给出一棵$n(2 \le n \le 2 \times 10^5)$个节点的树，边权为$1$。给定一个$1$到$n$的排列$a_i$，设$\operatorname{dist}(i,j)$为树上两点间距离，求$$\frac{1}{n(n-1)}\sum_{i=1}^{n}\sum_{j=1}^{n} \varphi(a_i \cdot a_j) \operatorname{dist}(i,j)\pmod{10^9+7}$$

• 题解：因为$a_i$是$1$到$n$的排列，所以我们可以设$p_{a_i}=i$。同时有以下结论$$\varphi(nm)=\frac{\varphi(n)\varphi(m)\gcd(n,m)}{\varphi(\gcd(n,m))}$$ 因此扔掉前面的分母$n(n-1)$，原式转化为$$\sum_{i=1}^{n}\sum_{j=1}^{n} \frac{\varphi(i)\varphi(j)\gcd(i,j)\operatorname{dist}(p_i, p_j)}{\varphi(\gcd(i,j))} $$ 开始反演，枚举$d=\gcd(i,j)$ $$=\sum_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{d} \right\rfloor} \varphi(id)\varphi(jd)\operatorname{dist}(p_{id}, p_{jd}) [\gcd(i,j)=1] $$ 套用$\epsilon = \mu * 1$ $$=\sum_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{d} \right\rfloor} \varphi(id)\varphi(jd)\operatorname{dist}(p_{id}, p_{jd}) \sum_{p|\gcd(i,j)}\mu(p)$$ 枚举$p$ $$=\sum_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor} \mu(p) \sum_{i=1}^{\left\lfloor \frac{n}{dp} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{dp} \right\rfloor} \varphi(idp)\varphi(jdp)\operatorname{dist}(p_{idp}, p_{jdp})$$ 枚举$T=dp$ $$=\sum_{T=1}^{n} \sum_{i=1}^{\left\lfloor \frac{n}{T} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{T} \right\rfloor} \varphi(iT)\varphi(jT)\operatorname{dist}(p_{iT}, p_{jT}) \sum_{d|T} \frac{\mu(\frac{T}{d})d}{\varphi(d)}$$ 设$$f(T)=\sum_{i=1}^{\left\lfloor \frac{n}{T} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{T} \right\rfloor} \varphi(iT)\varphi(jT)\operatorname{dist}(p_{iT}, p_{jT})$$ $$g(T)=\sum_{d|T} \frac{\mu(\frac{T}{d})d}{\varphi(d)}$$ 则原式转化为$$\sum_{T=1}^{n}f(T)g(T)$$ 其中$g(T)$可以在$O(n \log n)$的时间求出，考虑$f(T)$，本质相当于给$p_i$点一个权值$\varphi(i)$，然后把所有下标为$T$的倍数点$p_i$拿出来建虚树，dp跑一遍将每条边的长度乘以两侧节点权值和即可，总结点数是$O(n \log n)$的，因此总复杂度为$O(n \log n)$。

• comment：梦幻联动，双厨狂喜。

小学期，摸s