题解：P10583 [蓝桥杯 2024 国 A] 异或路径

· · 题解

调了一晚上看了半天没看出来结果今天早上发现 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。同时由于是快速幂，根据费马小定理，

a^{p-1}\equiv 1 \pmod p

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

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