P13833 【MX-X18-T5】「FAOI-R6」纯蓝 笔记

前置知识：有上限排列计数。

• 由异或最值问题，想到 0/1 Trie。

在 0/1 Trie 上考虑能够成为答案的 $a_i,a_j$ 满足什么性质，容易发现他们的高位是相同的，因此他们在值域上必然是相邻的两个数。

这样子将限制从“任意两个异或最小值”变为“排序后相邻两数异或最小值”。由有上限排列计数（$a_i=a_j$ 即 $f(a)=0$ 无贡献），启发我们只用 DP 出一个单调递减序列的方案数。

可以发现，当枚举最小值 $k$ 时，DP $f(a)=k$ 不容易，但是 DP $f(a)>k$ 是简单的，似乎可以容斥，但是考虑到最后要求 $\sum f(a)$，本质就是求 $\sum _{k=0}^{+\mathrm{\infty }}[f(a)>k]$，因此只要 DP 出这个方案数就好了。

设 $f_{i,j}$ 表示考虑到 $a$ 前 $i$ 个大的数，第 $i$ 个是 $j$ 的方案数，则有

$$f_{i,j}=(c(j)-i+1)\sum _{x>j,x\oplus j>k}{f}_{i-1,x}$$

状态数 $O(nV)$，转移 $O(V)$，需要进行 $O(V)$ 次 DP，时间复杂度 $O(n{V}^3)$，难以接受。考虑优化。

优化状态数

感受一下 0/1 Trie 的过程，这个 $k$ 应该不会很大，因为要求两两异或都能大于 $k\ge 2^p$，即 $V÷2^p\ge n-1$，解得 $k\le 2V÷n$。

因此时间复杂度变为 $O(V^3)$。

优化转移

这个 $\sum$ 转移使用了 $O(V)$ 的时间，启示使用前缀和、FWT 等科技优化。

考虑瓶颈 $x\oplus j>k$，它必然是前面几位 $x_{[13,h)}\oplus j_{[13,h)}>k_{[13,h)}$，后面几位 $x_{[h,0]}\oplus j_{[h,0]}=k_{[h,0]}$，对两个条件的判断都没有影响，可以任取。

那么考虑枚举 $h$ 和 $j_{[13,h)}$，计算得 $x_{[13,h)}=j_{[13,h)}\oplus (k_{[13,h)}+1)$，对于这一部分相同的 $x\to j$ 一次性转移，使用差分和前缀和即可解决。

时间复杂度 $O(V^2)$。