• 在以下复杂度计算中， 表示 值域大小。

Subtask 1

枚举异或哪个数 ，暴力计算 Highbit。复杂度 。

Subtask 2

我们发现这个 一定是 的一段二进制前缀。证明是容易的，感性理解一下，因为如果不是的话，那么这个 的无法再匹配上任何一个 的一段末位不会再减小答案，只会可能增大答案。

于是做到 。

Subtask 3

送分。

Subtask 4,5

考虑 01trie 上 dp。我们令 表示当前前 位已经选定，在 trie 上这段前缀的编号是 ，然后选择后面这段二进制位造成的最小贡献。

在转移中，如果你当前的前缀后面那一位选 ，那么所有前缀是“当前这个前缀后面一位接上 ” 的数异或以后的 Highbit 都确定在这个第 位了，令这个前缀的数的数量是 ，那么造成 的贡献。显然这个 就是 trie 中插入时统计的每个结点的访问次数 就行了。

选择后面一位接 的处理方法也一样。

这是转移代码：

int dp(int x,int w)
{
    if(w<0) return 0;
    if(!x) return 0;
    int u=dp(trie[x][0],w-1)+cnt[trie[x][1]]*(w+1);
    int v=dp(trie[x][1],w-1)+cnt[trie[x][0]]*(w+1);
    return min(u,v);
}

显然如果你转到一个前缀没有对应的数了，那么后面也没有递归下去的必要了，显然这时候这个贡献是 。这里也同样证明了前面选择一个前缀的结论是对的。

显然这时候，复杂度做到了 ，可以通过。

如果不用 trie 实现用一些其他的较劣的实现（就不讲了），复杂度是 ，只能通过 Subtask 4。