自动搬运

查看原文

来自洛谷，原作者为

	Amidst 生若直木，不语斧凿。

搬运于2025-08-24 22:59:23，当前版本为作者最后更新于2025-05-16 08:26:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

调了一晚上看了半天没看出来结果今天早上发现 FWT 挂了。

思路

本题解思路基于现有题解，但会讲得详细些，也会谈到一些可能存在的坑点。

首先考虑 $n\le 10^6$ 的做法。显然我们可以直接建出这棵树，再对其求出贡献。我们发现问题变成了 UVA13277，预处理每个节点 $i$ 到 $1$ 的路径上的权值异或和 $d_i$，再开个桶，记录每个值出现的次数，将这个桶 FWT 自卷积即可，最后将答案除以 $2$，统计答案时将每一位的下标和值分别作为底数和指数进行快速幂，最后相乘。

注意到原题中的连边方式是 $x$ 向 $\lfloor \sqrt x \rfloor$ 连边，于是非叶子节点数量必然小于等于 $\sqrt n$。

考虑根号分治，即设立阈值 $B$，将小于等于 $B$ 的部分和大于 $B$ 的部分分别讨论。

对于前半部分显然可以依照 $n\le 10^6$ 的做法处理。

对于后半部分，考虑连续的 $x$ 与 $\lfloor \sqrt x\rfloor$ 的边权值变化规律，可以先按照 $\lfloor\sqrt x\rfloor$ 的值分成 $\left(\lfloor\sqrt n\rfloor - \lfloor n^{1/4}\rfloor\right)$ 段，显然每一段的每条边权都可以表示为 $d_k \oplus w$，其中 $w$ 是连续自然数。

考虑每个 $x$ 的贡献来源，有 $d_k \oplus l = x$，则 $d_k \oplus x = l$，我们只需确定 $l$ 的极值，然后就可以在 01trie 上乱搞。

不妨在走边的过程中统计答案，计算每个点的子树内的贡献，将其加到对应的桶中，与小于等于 $B$ 的部分得到的桶中的值按位相加，最后 FWT 自卷积即可。

注意阈值 $B$ 不要太小，至少要大于 $\sqrt n$，否则会造成部分非叶子节点被当成叶子节点计算。FWT 时注意异或卷积时使用除以 $2$ 而不是乘 $0.5$。同时由于是快速幂，根据费马小定理，

可以将 FWT 得到的指数模 $p-1$ 以后再快速幂，注意指数仍要像 $n\le 10^6$ 时一样除以 $2$。

时间复杂度 $O(\sqrt n \log n)$。