首先作为管理员主要苦力向大家谢罪。这场比赛由于准备比较匆忙，以及管理员们的经验不足，导致部分分的分值和范围设置上有诸多不合理之处，样例与数据的强度也有较大差距，在此为造成大家不便表示歉意。

月球列车

idea from he_____he,mayaohua, solution from he_____he, data from hehezhou.

算法1

直接暴力模拟！时间复杂度 $O(nm)$ ，可以通过子任务 1，期望得分 $30$ 分。

算法2

考虑对于一次查询 $x$ ，依次决定每一个二进制位是 $0$ 还是 $1$ 。设 $a'_{j,i}=a_i \& (2^{j+1}-1)$ ，其中 $\&$ 表示二进制与。对于每个 $i$ ， $a_i+x$ 的 $2^j$ 位是 $a_i\oplus x$ 的 $2^j$ 位再异或上 $a_i+x$ 的第 $j-1$ 位是否进位。前者容易处理，后者等价于 $a'_{j-1,i}+(x\& (2^j-1))\geq 2^j$ 。所以求 $\bigoplus\limits_{i=1}^n (a_i+x)$ 的 $2^j$ 位时只需求出有多少个 $a'_{j-1,i}\geq 2^j- (x\& (2^j-1))$ 。可以排序预处理然后每次查询对每一位二分。

时间复杂度 $O((n+m)\log n\log a_i)$ ，可以通过前两个子任务，期望得分 $60$ 分。

算法3

注意到排序预处理的部分可以利用上一次排序的结果，将新的一位为 $0$ 的部分和为 $1$ 的部分归并排序，使预处理复杂度降至 $O(n\log a_i)$ 。

将查询离线之后，同样可以按上述方法将 $x$ 的前 $j-1$ 位的顺序用 $O(m\log a_i)$ 的复杂度求出。然后对于每一位，线性 two pointers 求出每个查询在这一位上的答案。

时间复杂度 $O((n+m)\log a_i)$ ，可以通过子任务 3，与算法 2 结合可以通过前三个子任务，期望得分 $90$ 分。

算法4

由于强制在线，我们不能预处理出所有查询的信息，但我们可以预处理出所有 $a_i$ 的信息。设对于 $j$ 预处理出的 $a'_{j,i}$ 的顺序为 $b_{j,1}\leq b_{j,2}\leq \cdots \leq b_{j,n}$ 。默认 $b_{j,0}=-\infty,b_{j,n+1}=\infty$ 。我们原先做的事就是将其中的一些 $+2^j$ 再和剩下的归并得到 $b_{j+1,1}\leq b_{j+1,2}\leq \cdots \leq b_{j+1,n}$ ，然后对于每个查询找到 $2^{j+1}-(x\& (2^{j+1}-1))$ 大于多少个 $b_{j,i}$ 。

此时多预处理出两个数组 $c_{j,i,0}=\max\{x|b_{j+1,x}\leq b_{j,i}\}$ 和 $c_{j,i,1}=\max\{x|b_{j+1,x}\leq b_{j,i}+2^j\}$ 。这个容易归并在 $O(n\log a_i)$ 内做到。

对于 $x$ 查询的时候如果求出 $2^{j+1}-(x\& (2^{j+1}-1))$ 在 $[b_{j,k},b_{j,k+1})$ 之间，那么直接用 $c_{j,k,0/1}$ 就可以得到 $j+1$ 的答案。这是因为 $\{b_{j+1}\}$ 中不存在 $(b_{j,k},b_{j,k+1})$ 中的数和 $(b_{j,k}+2^j,b_{j,k+1}+2^j)$ 中的数，$c_{j,k,0/1}$ 得到的解和 $2^{j+2}-x\& (2^{j+2}-1)$ 得到的解一定相同。

每次查询复杂度 $O(\log a_i)$ ，总复杂度 $O((n+m)\log a_i)$ ，可以通过所有子任务，期望得分 $100$ 分。

月球铁轨

idea from wangziji,he_____he, data,solution from hehezhou.

算法一

我会暴力！枚举每个区间再枚举每个位置的选择，然后排序求出第 $k$ 小。

复杂度 $O(2^nn^2)$，期望得分 $0$ 分。

算法二

定义 $f(x,T)=\max_{y\in T}(x\oplus y),g(x,T)=\min_{y\in T}(x\oplus y)$，其中 $x$ 是一个数，$T$ 是一个 $\mathbb{F}_2$ 上的线性空间。

考虑如何计算一个区间的最优稳定度。令 $c_i=a_i\oplus b_i(1\leq i\leq n)$。对于区间 $[l,r]$，求出 $x_{l,r}=\oplus_{i=l}^{r} a_i$，再对 $c_l\cdots c_r$ 求出张出的线性空间 $T_{l,r}$，则答案为 $f(x_{l,r},T_{l,r})$。

维护线性空间（可以维护一组基）以及求出 $f(x_{l,r},T_{l,r})$ 的复杂度均为 $O(m)$。

时间复杂度 $O(n^2m)$，可以通过子任务一，期望得分 $10$ 分。

算法三

我们发现如果一个区间的线性空间维数达到 $m$，则这个区间的答案就是 $2^m-1$。

随机数据下，维数小于 $m$ 的区间只有 $O(nm)$ 个，求出这些区间的答案后，使用经典算法求出第 $k$ 小即可。

时间复杂度 $O(nm^2)$，可以通过子任务三。

算法四

定义 $S_n=\oplus_{i=1}^n a_i$，则 $x_{l,r}=S_r\oplus S_{l-1}$。

对于性质 B，我们发现一个区间的答案就是 $S_r\oplus S_{l-1}$，于是我们把所有前缀异或和插入一颗 trie，然后 trie 上二分即可求出第 $k$ 小的答案。

时间复杂度 $O(nm)$，可以通过子任务四。

算法五

对于性质 C，此时区间 $[l,r]$ 答案就是 $f(0,T_{l,r})$。注意到一个性质，对于某个固定的 $l$，$T_{l,r}$ 最多只有 $m+1$ 种，维数分别为 $0\cdots m$，并且如果区间 $A$ 包含区间 $B$，$T_A$ 包含 $T_B$。

使用扫描线算法，每次在序列末尾加入一个数 $S_r$，并且维护出每个左端点当前对应的线性空间。加入一个数会使当前一个后缀的线性空间维数变大 $1$。维数变大总次数是 $O(nm)$ 的，于是暴力维护即可。

加粗部分更详细解释是，考虑使用 $S_{1}\cdots S_{r-1}$ 异或出 $S_r$，并且最小下标尽可能大，设这个最小下标是 $p$（如果不存在则为 $0$）。则 $p+1\cdots r$ 对应的 $T_{i,r}$ 维数均加一， $1\cdots p$ 对应的维数均不加一。

时间复杂度 $O(nm^2)$，可以通过子任务五。

算法六

我们发现一个性质，$f(x\oplus y, T)=f(x,T)\oplus g(y,T)$。于是区间 $[l,r]$ 的答案也是 $f(S_{l-1},T_{l,r})\oplus g(S_r,T_{l,r})$。

使用算法五维护出所有 $T_{i,r}$ 以及 $f(S_{i-1},T_{i,r})$。并且维护 $m+1$ 棵 trie，第 $t$ 棵 trie 包含 $f(S_{i-1},T_{i,r})(\texttt{dim}(T_{i,r})=t)$，其中 $\texttt{dim}$ 表示维数。

对于某个 $r$，$T_{i,r},g(S_r,T_{i,r})$ 同样最多 $m+1$ 种，且每一种对应一个维数。

于是计算出这几个值，并在对应 trie 上查询，但是这里有两个方向，一种是二分答案（逐位确定），每次跑一遍上述过程，时空复杂度分别为 $O(nm^3),O(nm)$，另一种是使用可持久化 trie 并多树二分，时空复杂度均为 $O(nm^2)$。

均可以通过子任务二，期望得分 $25\sim 70$ 分。

算法七

对于算法六的逐位确定方向，但是确定每一位的时候，通过 trie 的上一层，只维护出 trie 对应的一层。

时间复杂度 $O(nm^2)$，空间复杂度 $O(nm)$，可以通过本题，期望得分 $100$ 分。

月球车站

idea,solution from jiqimao, data from hehezhou.

以下把硬币的正反面属性称为颜色，0 表示背面，1 表示正面。

算法一

对于 $p=0$ 的情况，伏特永远不会翻转，因此当且仅当初始硬币全为正面，答案为 0，否则 skip 蚤也选择不操作答案为 -1。

可以通过子任务一，期望得分 $5$ 分。

算法二

对于 $p=1$ 的情况，伏特每次遇到背面的硬币都会将它翻转。

我们把同色的连续一些硬币称为一段。对于段数大于 $2$ 的局面，skip 蚤也只需要每次遇到正面的硬币都将它反转即可。容易发现这样即可让游戏无法结束。

当局面为全 0 或全 1，伏特显然获胜。

当局面为 00...011...1 时，显然伏特会获胜。

当局面为 11...100...0 时，伏特能否获胜与 1 的个数有关。当仅有一个 1 时，不管 skip 蚤如何操作，都会变为上述伏特必胜局面。否则，skip 蚤不翻转第一个 1 ，即可使段数大于 2 ，于是游戏无法结束。

判断一下即可，可以通过子任务二，期望得分 $10$ 分，结合算法一期望得分 $15$ 分。

算法三

规定一些记号：$c_x$ 表示局面 $x$ 的第一个硬币的颜色。$trans_{x,c}$ 表示局面 $x$ 去掉第一个硬币后接一个颜色为 $c$ 的硬币，即 $trans_{abcd,e}=bcde$。$f_x$ 表示局面 $x$ 的答案。

我们可以暴力地列一个 dp 出来。

若 $c_x=1$ ，$f_x=\max(f_{trans_{x,0}},f_{trans_{x,1}})+1$，

若 $c_x=0$，$f_x=pf_{trans_{x,1}}+(1-p)f_{trans_{x,0}}+1$。

这是个带环还带 $\max$ 的 dp，我们枚举 $\max$ 取值来源，每次用高斯消元求解。

特判掉 $p=1$ 或 $p=0$ 的情况之后若出现矩阵不满秩的情况则一定不合法。另外若求出的dp值不满足上述约束则也不合法。可以证明最多只有一种情况合法（因为最优策略唯一）。若没有合法情况输出 -1 ，否则输出唯一合法的解即可。

注意求解需先用 double 算出最优策略再算出取模后的答案。

复杂度为 $O(2^{2^{n-1}}\cdot2^{3n})$，可通过子任务三，期望得分 $10$ 分，结合算法一、二期望得分 $25$ 分。

算法四

为了进一步挖掘性质优化算法，先来研究一下两人都绝顶聪明时的这个博弈问题（伏特希望最小化步数，skip 蚤希望最大化步数）。

首先有一个很自然的问题：为什么 skip 蚤不是能翻就翻呢？其实是因为当 skip 蚤翻掉一个硬币时，他也就丧失了接下来对这个硬币的操作权。对于一个正面硬币，主动权掌握在 skip 蚤手中，而对于背面硬币，skip 蚤就陷入被动。

考虑到全正的局面是已知的最终局面，我们从这个局面开始推出其他局面的最优步数。

具体地，类似最短路的过程，我们维护一个队列，其中存储一些局面，它们已知最优步数且等待扩展其他局面。这些局面要按照最优步数从小到大排列。

从队头取出一个已经确定最优步数的局面 $z$ ，考察有哪些局面能一步转移到它，设为 $x,y$，其中 $c_x=0,c_y=1$。则如果 $x$ 是第一次被访问到，则 $x$ 的最优决策即可转移到 $z$。（伏特希望最小化步数）。类似的，如果 $y$ 是第二次被访问到，则 $y$ 的最优决策转移到 $z$。（skip 蚤希望最大化步数）

被扩展到的新局面存到队尾即可。

注意这里的 $x$ 和 $y$ 只有第一个硬币不同。则可以发现 $x$ 和 $y$ 总是同时被访问到，它们要第一次都是第一次，要第二次都是第二次。这样我们发现，每次都有且仅有一个局面可以扩展。

那么在一种理想的情况下，局面之间的转移关系就构成了一条链，所有局面的最优步数恰好取遍了 $0$ 到 $2^n-1$ 。

但是还有一个例外：当全正局面作为第二次访问到的 $y$ 出现时，它已经无法再被扩展了。此时还没有被扩展到的局面就是无解局面：以它们为初始局面的游戏无法结束。

选手们当然可以验证出在给定的数据范围内不存在这种例外情况。就算没有得到这个结论，也可以在代码中特判。当存在无解局面时，不管初始局面是否无解直接输出 -1 即可，这是因为在伏特随机的游走的时候，总会有可能走到无解局面。

下面还是证明一下在 $n$ 取任何值时都不会存在上述例外发生。即对于任何初始局面，伏特有必胜策略。

证明：我们把初始局面的硬币按 $1$ 到 $n$ 标号。从硬币按 $1$ 到 $n$ 排列到下一次硬币按 $1$ 到 $n$ 排列的一次过程称为一回合。对于每一回合，起初伏特看到背面的硬币就翻面，直到 skip 蚤第一次操作，伏特在这一回合之后就都不操作。

这样会发现每一轮过后局面表示的二进制数都会变小。总会变成全 0，此时伏特一路翻过去就获胜了。

证毕。

注意，上面的这个策略只是保证获胜的策略，并不是步数最少的策略。

于是，得到了这样的结论：局面之间的转移关系构成了一条链，所有局面的最优步数恰好取遍了 $0$ 到 $2^n-1$ 。我们可以按局面在这条链上的位置来给局面编号，局面 $i$ 的最优步数为 $i$，以下均使用这个标号描述局面。

回到最初的问题。当伏特操作与否随机时，利用这个结论来优化一下算法。

对于 skip 蚤，他从 $i$ 要么到 $i-1$，要么到某个 $x(x < i-1)$。对于伏特，他从 $i$ 要么到 $i-1$，要么到某个 $y(y > i-1)$。下面证明 skip 蚤每次都从 $i$ 到 $i-1$，即期望 $f_i$ 单调递增。

反证，若 $x < y,f_x > f_y$，则从 $y$ 到第一次到达 $x$ 的这些回合里，skip 蚤都从 $i$ 走到 $i-1$，那么必定经过 $x$。第一次到达 $x$ 之后按之前的最优策略走。则 $f'_y > f_x > f_y$，与最优性矛盾。则 $f_i$ 单调得证。

于是我们去掉了转移方程中的 $\max$，可以高斯消元解决，而观察方程组形态可以优化到 $O(2^{2n})$。

可以通过子任务三、四，期望得分 $40$ 分，结合算法一、二期望得分 $55$ 分。

算法五

观察到从局面 $i$ 一定会经过局面 $i-1$。我们改变状态定义：从 $i$ 到 $i-1$ 的期望步数。写出方程发现可以按链的顺序递推，优化为 $O(2^n)$。

期望得分 $100$ 分。

bonus: 是否可以在多项式复杂度内解决本题或得到局面序列的某一项。