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

对于一个有序的 $\{ a \}$ 与 $\{ l \}$，分配的方案数为 $\prod\limits_i \max(0,\sum\limits_j [l_j \ge a_i] - (n-i))$。

由于 $\min\limits_{i<j} {a_i \oplus a_j} = \min\limits_{i<n} {a_i \oplus a_{i+1}}$，容易得到 $n V^2 \log V$ 的 dp，枚举 $f(a) >k$，方案数 $f_{i,j}$ 为放了 $i$ 个 $a$ 最大的是 $j$，转移即枚举一个 $p \oplus j > k \land p \ge j$ 的 $p$ 转移，显然只有 $\log V$ 个区间，直接差分即可。

考虑 $f(a)$ 的上界，设 $t = \lfloor \log_2 f(a) \rfloor$，则这 $n$ 个数放到 trie 树上，则 $<t$ 位的那些子树 $siz < 2$，不然取这个子树里两个更优。

那么在前 $\log V - t$ 层中，至少要有 $\dfrac{n}{2}$ 个叶子，那么 $2^{\log V - t} \ge \dfrac{n}{2}$，那么 $f(a) \le \Theta(\dfrac{V}{n})$，于是上面的做法就是 $\Theta(V^2 \log V)$ 的。

考虑继续优化，对每个 $j$ 枚举 $\log V$ 个区间也太不优了，直接枚举 $j\oplus p$ 第一个比 $k$ 大的位，再枚举 $j$ 的前面这些位置，那 $p$ 前面这些位置也是确定的，简单讨论前面这些位置的大小关系然后后面的位置都可以任意取，于是就有 $j$ 的一段区间的和转移到 $p$ 的一段区间，可以前缀和 + 差分求出。

复杂度 $\Theta(V^2)$。