第一次给HNOI出题（其实也是第一次给NOI赛事出题）。

题目链接

稍微了解一点MIT的人（比如知道Infinite Corridor不是真的无限长)可能看完题就知道出题人是谁了（然而好像因为奇怪的原因不能把学校名写在题目里，不过大家看到“某大学”，而不是“T大”或者“P大”可能也知道是怎么回事了？）。

简易题解：

如果第i个数之前的运算符是and，则这一位设为1，否则为0，得到的二进制数记为$x$。

对每一位分别考虑，对于第i位，如果第j个数是1，那么这一位设为1，否则为0，得到的二进制数记为$b_i$。

以左边为最低位，按前缀归纳容易证明，第i位的结果为1，当且仅当$x < b_i$。

我们将b从大到小排序，结果设为c，那么答案不为零仅当在c的顺序下，r中没有任何0在1的前面。找到r中第一个0的位置，假设是k，那么解x要满足$c_k \le x < c_{k – 1}$，于是答案是$c_{k – 1} – c_k$。

题外话：

当时出题的时候很紧张，是真的紧张，因为觉得实在是太水了。我当时的70分做法是猜结论，大概就是猜到有用的DP状态有$O(nm)$个再bitset。然后觉得这实在太好猜了，其实根本不用猜，只要你注意到DP状态可能不满这个事实，然后直接记录有用状态就行了。

我当时很怕结果出来十几个AC，全场70。然后就再也没人找我出题了。

当时就不停的想HNOI有什么水题，是不是比我这个更水来安慰自己。

后面想想给大家送送分也好，至少这个题不是原题或者错题，能让自己成为大众喜闻乐见的出题人也不错。

结果分数分布大家都懂的。我至今不知道拿50分的是怎么回事（$n$只开了$500$？拿50分的人能不能在下面评论区说一下怎么拿的）。于是我的顾虑成了多余的。

不过这也不错，一来我的题终于不是HNOI最水的题了，二来我的题很可能送人进队（比如你A了或者高分暴力），不太可能送人退役（最多就是你30分暴力分挂成10分或者0分）。Still，如果有人因为我的题暴力写错退役我只能抱歉了，对不起我给了30分暴力分。

至于重测，那是因为我在Windows下造的数据，然后由于跨操作系统，换行符出了点问题-.-

考场上被各种倒推做法虐了。

其实倒推本质就是动态维护字典序。我很高兴大家因为我的题发明了一种新的排序算法。我可以把这个题改成每次模一个不同的数，然而似乎还是有基于倒推的奇技淫巧可以做。我也可以出成二进制高精度什么的，但是感觉它们还是可以过，也就是说在不懂正解只会倒推的（也就是大多数）人眼里，我把这个题目弄得更毒瘤而不是更神了。

说起来$O(\frac{nmq}{w})$可能是能过的（UOJ上能过TAT），解决方法大概是把$q$弄大，比如$10,000$。但是读入就很tricky了，可以压字符读入但是这样也很毒瘤。

所以大概这个题也只能放了吧，虽然不得不说我不是很喜欢这种倒推的做法，太直接了，个人感觉和标算没法比。但是也没办法，就像一个优美的题，结论就是输出a+b，也会有不明真相的群众写出一种和按位模拟加法等价的做法，你还没什么办法卡。