P5538 【XR-3】Namid[A]me

2019-10-04 15:19:32


好久没有题解了,那我就搬运一下官方题解吧

update: 文章已经按要求作者要求做过修改,谢谢xht37巨佬的修正!(若原作者大大有其他问题,请提出,谢谢)

另附上本文的markdown版本(本文latex全是我手打的……): $link$

官方题解

先介绍如何快速计算 $x^x mod P$ 。注意到模数 $P=786433$ ,且在题目中给出了模数的一个原根,因此我们可以轻松在 $O(P)$ 的时间内预处理出 $1~P-1$ 每个数的离散对数 $ind[x]$ 以及幂 $pow[k]=g^k mod P$ 。通过欧拉定理即可在 $O(1)$ 时间内计算 $x^x=pow[ind[x]x mod (P-1)]$ 。需要特判 $x\equiv 0 (mod P)$ 的情况。

接下来考虑一条链如何计算。

这样所有链都等价于一个区间,考虑枚举右端 ,那么对于 $[l,r]$ 内所有数的与设为 $x_l$ ,注意到若 $x_l\neq x_{l+1}$ ,由于 $x_l = x_{l+1} and a_l$ ,那么必然是至少在 $x_{l+1}$ 中的⼀个⼆进制位从 $1$ 变为 $0$ 。因此,从 $x_l$ 到 $x_1$ ,必然最多只有 $w+1$ 种取值。我们考虑只维护被取到的值分别取到了多少次即可。

接下来注意对于一个有 $d$ 个叶子的子树,在维护时子树内每个节点到子树的根的路径上的与和总共不超过 $d(w+1)$ 种取值,这是因为将每个叶子到根的一条链内的取值各自都不超过 $w+1$ 。我们只需在DFS 的过程中维护每个⼦树内所有能取到的值的出现次数即可。这一部分的复杂度为 $O(ndw)$ 。在处理子树的时候,我们还需计算路径两端点在不同子树的路径的答案,这一部分我们暴力枚举,注意到两个叶子只会在它们的 LCA 位置为合并的复杂度贡献 $(w+1)^2$ ,因此计算这⼀部分答案的总代价为 $O((dw)^2)$ 。但是同时又有另一个显然的上界: $O(n^2)$ ,因为只有这么多条路径,而在 $nd$ 总体有限制的这一条件下,考虑不等式 $min(a,b)\leq \sqrt{ab}$ ,可知这一部分的复杂度不超过 $O(min(n,dw)^2)\leq O(ndw)$ 。

综上所述,本算法的复杂度为 $O(ndw)$ 。