题解：纯蓝

· · 题解

Solution

令 V=\max l_i。

Lem. 1：将 a 从小到大排序，相邻数异或值的最小值即为 f(a)。

:::info[证明] 这是经典问题。可以考虑 trie 求最小异或对的过程，或者也可以证明 a<b<c\Rightarrow\min(a\oplus b,b\oplus c)\le a\oplus c，总之易证。 :::

Lem. 2：对于长度为 n 的序列 a，f(a)\le\frac{2\max a_i}{n-1}。

:::info[证明] 考虑如果 f(a)\ge 2^k，\max a_i 至少为多少。

::: 设 $g(k)$ 为 $f(a)>k$ 的 $a$ 个数，有 $\sum_{k=0}^{\max f(a)} g(k)=\sum_a f(a)$。原因是序列 $a$ 会在 $g(0),g(1),\cdots,g(f(a)-1)$ 中计算，总共算了 $f(a)$ 次。 枚举 $k$，考虑计算 $g(k)$。设 $c_i=\sum_{j=1}^{n}[l_j\ge i]$。对于一个从大到小排序的序列 $b$，由于 $f(b)>0$，$b$ 中没有相同的数，因此根据经典的有上限排列计数，对应的 $a$ 的个数为 $\prod_{i=1}^{n}\left(c_{b_i}-i+1\right)$。 设 $f_{i,j}$ 为确定了 $b_1,b_2,\cdots,b_i$ 且 $b_i=j$ 的情况下，$\prod_{k=1}^{i}(c_{b_i}-i+1)$ 的和。转移： $$f_{i,j}=(c_j-i+1)\sum_{x=j}^{V}[j\oplus x>k]f_{i-1,x}$$ DP 的复杂度为 $\mathcal O(nV^2)$，根据 Lem. 2，枚举 $k$ 的复杂度为 $\mathcal O(\frac{V}{n})$，我们得到了一个 $\mathcal O(V^3)$ 做法。 考虑优化 DP 的转移，同时转移所有 $j$： - 枚举 $j\oplus x$ 与 $k$ 最高的不同的位 $h$，要求 $k$ 这位为 $0$，令 $k'=\lfloor\frac{k}{2^h}\rfloor$，类推 $j',x'$。 - 枚举 $j'$，得到 $x'=(k'+1)\oplus j'$。 - 可以发现 $j'\neq x'$，我们通过 $j',x'$ 就确定了 $j,x$ 的大小。跳过 $x'<j'$ 的情况 - $j,x$ 二进制下的低 $h$ 位是任意的，因此将 $f_i$ 的 $[j'2^h,(j'+1)2^h)$ 加上 $\sum_{t=x'2^h}^{(x+1)2^h-1}f_{i-1,t}$。 区间加与区间求和可以通过差分与前缀和实现，这样之后将 $f_{i,j}$ 乘上 $(c_j-i+1)$ 即可完成转移。 一次转移复杂度为 $\mathcal O(\sum_{i=0}^{\log_2V}2^i)=\mathcal O(V)$。因此总复杂度为 $\mathcal O(V^2)$，可以通过。 --- 感谢 @[irris](https://www.luogu.com.cn/user/419487) 提出了 Lem. 2，将此题从 $\mathcal O(nV^2)$ 优化到 $\mathcal O(V^2)$。 闲话：这题叫纯蓝的很大一部分原因是赛前预估这题为蓝题。