Nemlit 的博客

Nemlit 的博客

By a konjac

题解 CF809E 【Surprise me!】

posted on 2019-09-30 23:46:38 | under 题解 |

我们要求的柿子是张这样子的:

$$\frac{1}{n * (n - 1)} * \sum_{i = 1}^n\sum_{j = 1}^{n}\phi(a_i*a_j)*dis(i, j)$$

其中 $a_i$ 为一个排列, $dis(i, j)$ 表示在树上的距离

这种题的套路一般是先拆柿子,但是这道题的式子……

我们要从一个性质下手: $$\phi(a * b) = \frac{\phi(a) * \phi(b) * gcd(a, b)}{\phi(gcd(a, b))}$$

代入原式得:

$$\frac{1}{n * (n - 1)} * \sum_{i = 1}^n\sum_{j = 1}^{n}\frac{\phi(a_i) * \phi(a_j) * gcd(a_i, a_j)}{\phi(gcd(a_i, a_j))}*dis(i, j)$$

先忽略前面的数,只看后面的 $\sum$ ,枚举 $gcd(a_i, a_j)$ ,得到

$$\sum_{k = 1}^n\frac{k}{\phi(k)}\sum_{i = 1}^n\sum_{j = 1}^{n}\phi(a_i) * \phi(a_j)*dis(i, j)*[gcd(a_i, a_j) == k]$$

然后反演一波,得到:

$$\sum_{k = 1}^n\frac{k}{\phi(k)}\sum_{i = 1}^n\sum_{j = 1}^{n}\phi(a_i) * \phi(a_j)*dis(i, j)*\sum_{(x * k|a[i]) \& (x * k | a[j])}\mu(x)$$

枚举 $k * x$

$$\sum_{T = 1}^n\sum_{k|T}\frac{k}{\phi(k)}\sum_{i = 1}^n\sum_{j = 1}^{n}\phi(a_i) * \phi(a_j)*dis(i, j)*\sum_{(T|a[i]) \& (T | a[j])}\mu(\frac{T}{k})$$

交换顺序得: $$\sum_{T = 1}^n\sum_{k|T}\frac{k}{\phi(k)} * \mu(\frac{T}{k})\sum_{a[i]\ |\ T}\sum_{a[j]\ |\ T}\phi(a_i) * \phi(a_j)*dis(i, j)$$

我们考虑枚举T,对于后面的柿子,我们可以单独拎出来,对所有 $a[i] | T$ 用树形DP求出后面柿子的答案,前面的柿子可以提前与处理出来

由于虚树的总点数是 $(nlogn)$ 个(并不会证明),所以复杂度正确,但由于虚树上的DP和普通DP有一定差异,所以我们还需要对后面的柿子继续化简

$$\sum_{a[i]\ |\ T}\sum_{a[j]\ |\ T}\phi(a_i) * \phi(a_j)*dis(i, j)$$

拆开 $dis(i, j)$ 得:

$$\sum_{a[i]\ |\ T}\sum_{a[j]\ |\ T}\phi(a_i) * \phi(a_j)*(dep[i] + dep[j] - 2 * dep[lca(i, j)])$$

令 $val[i] = \phi(a_i)$ ,把所有 $a[i] | T$ 拎出来,假设有x个

$$\sum_{i= 1}^{x}\sum_{j = 1}^xval[i] * val[j]*(dep[i] + dep[j] - 2 * dep[lca(i, j)])$$

$$\sum_{i= 1}^{x}\sum_{j = 1}^xval[i] * val[j]*dep[i] + \sum_{i= 1}^{x}\sum_{j = 1}^xval[i] * val[j] * dep[j] -2 * \sum_{i= 1}^{x}\sum_{j = 1}^xval[i] * val[j] * dep[lca(i, j)])$$ $$2 * \sum_{i= 1}^{x}val[i] *dep[i] \sum_{j = 1}^xval[j] -2 * \sum_{i= 1}^{x}\sum_{j = 1}^xval[i] * val[j] * dep[lca(i, j)])$$

前面的柿子可以与处理出来,后面的柿子只需要我们在虚树上枚举lca,求出 $\sum_{i= 1}^{x}\sum_{j = 1}^xval[i] * val[j]*[lca(i, j) == lca]$

这个值其实不难求,记录 $f(x)= \sum_{i = 1}^xval[i]$ 即可