2019省选训练12

T2 森林

题意

一棵以1为根的树，每次挂一个叶子，并且每次都有一次机会交换两棵不相交的子树（原树并不变），问每次交换后的最大直径。

题解

先不考虑链的情况。
假设在某一次询问中，我们交换(x, y)对应的子树，然后一条直径在交换后的(y, z)对应的子树里。
容易知道，原树中(x, y)的lca一定是(x, z)的lca的祖先。
而且显然x是叶子节点。否则为什么不交换(x子树中最深的点，y)呢？
而我们又可以发现，将y向上到lca(x, y)路径上的深度为dep(lca(x, y)) + 1的点与x交换显然会更优。
答案？容易发现，是y中深度最大的点到lca(x, y)的距离加上dis(lca(x, y), lca(x, z))加上dis(x, z)减1。那么我们其实完全可以把y中深度最大的点把y代替，把问题转化一下。
我们可以维护这样一个东西来简化原问题：
维护一个三元组(x, y, z)。
满足这个三元组(x，y, z)的三点距离和最大；这里的距离和代表的是聚集到一个点的最小距离和。（即虚树上的边数）
答案是三点距离和减1。
每次新加一个叶子w，那就判断一下无序三元组(x, y, z)，(x, y, w)，(x, z, w)，(y, z, w)到底哪个答案大，就更新一下。
但是(x，y，z)的虚树如果是一条链怎么办？

2019省选训练14

T1 与非

题意

动态在数组末尾加0或1，每次询问一段区间，求

$$a_l \otimes (a_l \circ \ a_{l+1}) \otimes ... \otimes (a_l \circ a_{l+1} \circ a_{l+2} \circ ... \circ a_r)$$
其中$\otimes$表示异或，$\circ$表示与非。

题解

容易把数组划分为000...,111...,000...,111...,...这样子。
注意到普遍的情况：

$$00000... \rightarrow 1 11111... \rightarrow \frac {\#1}{2}$$

T2 求和

题意

求下式模998244353的值：

$$\sum_{i = 1} ^ n \sum_{j = 1} ^ m \mu(i) \mu(j) s(ij)$$
其中$S(x)$表示的是$x$的因数和。

题解

这题可以有两种切入方法。
个人比较喜欢的是从$s$函数的角度切入。

$$\begin{aligned} & \sum_{i = 1} ^ n \sum_{j = 1} ^ m \mu(i) \mu(j) \sum_{d | ij} d \\ = & \sum_{i = 1} ^ n \sum_{j = 1} ^ m \mu(i) \mu(j) \sum_{\frac{d}{(i, d)} | j} d \\ (枚举t = (i, d))= & \sum_{i = 1} ^ n \sum_{j = 1} ^ m \mu(i) \mu(j) \sum_{t = 1} \sum_{\frac{d}{t} | j} d \cdot [(\frac{i}{t}, \frac{d}{t}) == 1] \\ = & \sum_{i = 1} ^ n \sum_{j = 1} ^ m \mu(i) \mu(j) \sum_{t = 1} \sum_{d | j} dt \sum_{k} [k | \frac{i}{t}] \cdot [k | d] \cdot \mu(k) \\ = & \sum_{i = 1} ^ n \sum_{j = 1} ^ m \mu(i) \mu(j) \sum_{k = 1} ^ {\lfloor \frac {n}{i} \rfloor} \mu(k) \sum_{t | \frac {i}{k}} \sum_{d | \frac{j}{k}} (dk)t \\ = & \sum_{i = 1} ^ n \sum_{j = 1} ^ m \mu(i) \mu(j) \sum_{k = 1} ^ {\lfloor \frac {n}{i} \rfloor} k\mu(k) \sum_{t | \frac {i}{k}}t \sum_{d | \frac{j}{k}}d \\ = & \sum_{k = 1} ^ n k\mu(k) \sum_{i = 1} ^ {\lfloor \frac {n}{k} \rfloor}\sum_{j = 1} ^ {\lfloor \frac {m}{k} \rfloor} \mu(ik) \mu(jk) \sum_{t | i}t \sum_{d | j}d \\ = & \sum_{k = 1} ^ n k\mu(k) \sum_{i = 1} ^ {\lfloor \frac {n}{k} \rfloor}\sum_{j = 1} ^ {\lfloor \frac {m}{k} \rfloor} \mu(ik) \mu(jk) s(i) s(j)\\ = & \sum_{k = 1} ^ n k\mu(k) \sum_{i = 1} ^ {\lfloor \frac {n}{k} \rfloor} \mu(ik) s(i) \sum_{j = 1} ^ {\lfloor \frac {m}{k} \rfloor} \mu(jk) s(j)\\ \end{aligned}$$
注意到最后两个和式是独立的，所以可以对于每个k分两次做（复杂度相同），然后总复杂度就是乘上一个调和级数，也就是$O(n \ln n)$。

另一种方法：
这种方法比较容易想到，直接枚举$\gcd(i, j)$，即：（忽略一些向下取整）

$$\begin{aligned} & \sum_{i = 1} ^ n \sum_{j = 1} ^ m (\sum_{d} [d | i] \cdot [d | j] \cdot \mu(d)) \mu(i) \mu(j) s(ij) \\ = & \sum_{d = 1} ^ n \mu(d) \sum_{i = 1} ^ {\frac {n}{d}} \sum_{j = 1} ^ {\frac {m}{d}} \mu(id) \mu(jd) s(ijd ^ 2) \\ = & \sum_{d = 1} ^ n \mu(d) s(d ^ 2) \sum_{i = 1} ^ {\frac {n}{d}} \sum_{j = 1} ^ {\frac {m}{d}} \mu(id) \mu(jd) s(i) s(j) [(i, j) == 1]\\ = & \sum_{d = 1} ^ n \mu(d) s(d ^ 2) \sum_{i = 1} ^ {\frac {n}{d}} \mu(id) s(i) \sum_{j = 1} ^ {\frac {m}{d}} \mu(jd) s(j) \sum_{t} [t | i][t | j]\mu(t)\\ = & \sum_{d = 1} ^ n \mu(d) s(d ^ 2) \sum_{t = 1} ^ {\frac {n}{d}} \mu(t) \sum_{i = 1} ^ {\frac {n}{dt}} \mu(idt) s(it) \sum_{j = 1} ^ {\frac {m}{dt}} \mu(jdt) s(jt) \\ \end{aligned}$$
同样的，最后两个和式也是一类的，所以只要调和级数枚举前两个和式，再用一个不满的ln，总共用$O(n \ln ^ 2 n)$的复杂度。