让我感觉有点意思的总想写一个题解。

问题简述

        给定一个序列，请将其重新排列，使得前缀按位或得到的序列字典序最大，其中。

        题目链接：https://codeforces.com/contest/1742/problem/G

思路

        由于最后得到的序列长度恒定为，因此字典序最小只需令靠前的项尽可能大，换言之，可以直接构造解：

        （注：因为任意解均可，当有多个结果相同时，取最小下标。）我们可以直接如此构造，得到一个复杂度为的算法。但实际上没有必要：一个int型（哪怕不带符号）数至多32位，因此一种朴素的感觉是，序列会很快（项之内）变成常列，于是此后的排序将不再影响的字典序大小。这一朴素的感觉很容易得到证明。

        假设对某一个，有，这意味着对任意，有：

        如果我们将整数看作集合，上式意味着对任意，有。而注意到的通项按集合为，因此有：

        根据上式不难发现，序列将变为常列，即。而如果，则至少集合中多出个元素，而全集仅包含个元素，因此实际上只需要计算的前项即可，时间复杂度为。

后记

        本场的实况录制地址：https://www.bilibili.com/video/BV1f84y1B7td

        当然，我也不知道为什么我临场写了个那么复杂的玩意儿……看来还需要继续努力。