其实写题面的时候埋了不少彩蛋啊？大家可以试一试能找出几个？

几何冲刺

出题人 ftiasch

数据和题解 WrongAnswer

验题人 matthew99

算法一

对于每对红点 $P_i,P_j$，暴力枚举蓝点 $Q_k$ 判断其是否在三角形 $O{P}_i{P}_j$ 内。

如何判断 $Q_k$ 是否在三角形 $O{P}_i{P}_j$ 内？只需判断三角形 $O{P}_i{Q}_k$、三角形 $O{P}_j{Q}_k$、三角形 $P_i{P}_j{Q}_k$ 的面积之和是否等于三角形 $O{P}_i{P}_j$ 的面积即可。以 $(x_1,y_1),(x_2,y_2),(x_3,y_3)$ 为顶点的三角形面积为 $$\frac{1}{2}|x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)|$$ 这样就能每次 $O(1)$ 完成判断了。时间复杂度 $O(n^{2}m)$，期望得分 32 分。

算法二

考虑将问题进行转化。

注意到点 $Q_k$ 在三角形 $O{P}_i{P}_j$ 内的条件是点 $P_j,Q_k$ 在直线 $O{P}_i$ 同侧，且 $\mathrm{\angle }{Q}_{k}O{P}_i<\mathrm{\angle }{P}_{j}O{P}_i$ 且 $\mathrm{\angle }{Q}_k{P}_{i}O<\mathrm{\angle }{P}_j{P}_{i}O$。于是可以枚举 $P_i$，枚举直线 $O{P}_i$ 的一侧，然后把每个红点和蓝点 $X$ 当成一个二元组 $(a,b)$，其中 $a=\mathrm{\angle }XO{P}_i$，$b=\mathrm{\angle }X{P}_{i}O$。然后枚举点 $P_j$，就只需找出 $a,b$ 两维均比 $P_j$ 小的蓝点了。

按其中一维排序，用数据结构（如树状数组或set）维护另一维即可。具体实现方式是按其中一维从小到大顺序扫描每个点，如果是蓝点则插入数据结构，如果是红点则在数据结构中查询另一维比该点小的蓝点。时间复杂度 $O(n(n+m)\log m)$，期望得分 78 分。

算法三

算法二还可以进一步优化。

我们可以一开始以原点 $O$ 为中心，将所有点（包括红点和蓝点）进行极角排序。

之后枚举点 $P_i$ 时，每个点的 $a$ 这一维已经有序。由于对非空三角形只要找出任意一个内部的蓝点，因此在按 $a$ 从小到大枚举 $P_j$ 时不需要要数据结构维护蓝点，只需用一个变量维护扫描到的蓝点中 $b$ 最小的点即可。

这样时间复杂度为 $O(n^2+nm)$，期望得分 100 分。

去月球

出题人 WuHongxun

数据和题解 Scape

验题人 worse

算法 1

首先我们先来证明一个结论 即最终答案和消除顺序无关。

如果在某个时刻删掉了$..xx..$会使答案变差，那么说明更优解应该是其中的某个$x$和一个另外的$x$配对了，不失一般性地，我们设是左边这个$x$。

那么在删左边这个$x$之前，序列的样子应该是$..xxx..$,这时候我们注意到删左边这对$xx$和删右边这对$xx$之后结果的是一样的，所以答案并不会变大。

对于这个结论也有一个wiki

那对于每个询问，我们都拿一个栈暴力跑一遍就可以知道答案了

时间复杂度$O(nq)$,期望得分$20$分

算法 2

我们考虑Subtask 2

我们显然只要考虑出现了两次的括号

对于某个出现了两次的权值$i$,设第一次出现在$l_i$,第二次出现在$r_i$

那么对于某个询问$L,R$,这对括号被消除当且仅当$[l_i+1,r_i-1]$是可消除的并且$l_i\ge L$,$r_i\le R$

判断是否可消除可以直接建一棵树来判断。

而第二个约束是显然可以通过二维数点来实现的。于是这个Subtask就被解决了。

算法 3

Subtask 3是给离线做法的，我们先来考虑离线。

我们进行分治，对于当前分治区间$[L,R]$,我们只处理过中点的询问。

我们设中点是$mid$，那么对于$[L,mid]$的每个后缀区间和$[mid+1,R]\mathrm{的}\mathrm{每}\mathrm{个}\mathrm{前}\mathrm{缀}\mathrm{区}\mathrm{间}$，我们都用一个栈维护出他们消除后的答案。

考虑把两个区间合并，新发生的消除显然只会是前面区间的某个后缀和后面区间的某个长度相同的前缀翻转过来完全相同。我们接下来就是要求一个lcp。

考虑怎么求lcp，$[mid+1,R]$的长度为$i+1$的前缀消除后的结果要么是长度为$i$的前缀删掉最后一个字符或者是在最后面加上一个新的字符。那么我们用trie来保存这个结果。求lcp就是求两个对应节点的LCA。

而在线就显然只需要把每个区间的trie和结果都存下来，对于每个询问都去对应的分治区间查询。

那么我们如果用倍增/树剖去求LCA，我们可以做到$O(n{\log }^{2}n+q\log n)$，基本上可以得到$100$分。

如果我们用RMQ去求LCA，我们可以做到$O(n{\log }^{2}n+q)$

如果更丧病一点用$O(n)-O(1)$LCA，我们可以做到$O(n\log n+q)$

标算用的是RMQ求LCA。

但是还有一个小细节是如果我们想要做到每个询问回答是$O(1)$,我们还要做到快速定位到询问区间

我们有两个做法，第一个做法是分治实际上就是一棵线段树，那么某个询问对应的分治区间实际上就是他们的$LCA$,我们用$O(1)$回答的LCA就可以做到。

或者我们也可以用一个更简单的方法，我们把分治这棵线段树开到$2^{17}-1$,这样对于询问$L,R$，他们会在$LxorR$的highbit上分开。

这题$80$分的Subtask大概是给一些分块做法和询问需要$lo{g}^2$的做法的（比如二分hash）。

算法4

from matthew99

考虑我们像算法二那样建一棵操作树，保证对于这棵树的每个子树都是可以完美消除的。

我们直接类似算法三分治后建trie的做法，我们从左往右扫，如果当前字符和栈顶匹配就回到父亲，不然就把当前字符压到栈内并且走到对应的儿子。

对于这棵树，我们从任意一个节点出发，经历一个可完美消除的序列后，它都一定会回到这个节点本身。

所以对于某个询问$[L,R]$，答案就是$R-L+1$再减去他们在这棵树上的距离。

正常的写法是$O((n+q)\log n)$

如果用hash_map和$O(n)-O(1)$LCA的话，可以做到$O(n+q)$

具体实现细节可以参考这个submission

量子破碎

出题人 WuHongxun

数据和题解 WuHongxun

验题人 fateice

算法0

我们用操作4，暴力$O(2^n)$的问出来每个$a[i]$就好啦。

算法1

我们考虑怎么优化这个暴力。

我们可以注意到我们大部分的时间都在查空的$a[i]$，如果我们只关注一位，不妨把别的位都变成0，然后查一查这一位上xor是0还是1。

注意$A{A}^t=I$意味着，$A^t=A^{-1}$，从而$A$一定是可逆的。

而把所有别的位都改成0不是一个可逆的操作，所以肯定是无法用2实现的。

我们只好用操作3来做到把除了第$i$位之外每一位强制为0，作用上矩阵$\left(\begin{array}{cc}1& 0\\ 1& 0\end{array}\right)$

然后用操作4查一下$a[0]$和$a[2^i]$即可。

因为要对每个$i$做一次，复杂度$O(n^2)$。

算法2

我们考虑如何丢掉算法1里的最后一步用操作4查$a[0]$和$a[2^i]$？

如果直接随机，那么无论xor是0还是1，都会随机返回0或1（每次x会重新随机）。

为了区分出来我们做变换$a[0]:=a[0]+a[2^i]$，$a[2^i]:=a[0]-a[2^i]$, 也就是应用矩阵$\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$

这样如果xor是0，那么一定会返回0，否则会随机返回0或1。

随机多次判断即可，复杂度$O(n^2)$有较大的常数。

算法3

fateice 在验题时提出一个hack。注意题面里有提到交互库的实现，会在概率平方和为0的时候返回0。

如果平方和不为0，返回0的概率很小。

那么只要每次把一位做变换$a[0]:=a[0],a[1]:=a[0]$，如果返回了0，那么说明xor为0，否则说明xor为1。

$\left(\begin{array}{cc}1& 0\\ 1& 0\end{array}\right)$

复杂度$O(n)$但同样是概率算法。

算法4

我们考虑对每一位$i$都做算法2中的变换$a[0]:=a[0]+a[2^i]$，$a[1]:=a[1]-a[2^i]$，这样$a[0]$就会变成所有$a$的和。

如果我们在变换前枚举第$i$位，把它的$a[0]:=a[0],a[1]:=-a[1]$，也就是作用矩阵$\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right)$。

那么变换后如果这位xor为0，那么$a[0]$会变为$0$，否则一定不是$0$。

最后一步用操作4查一下$a[0]$就好啦。

询问复杂度$O(n^2)$

算法5

@fateice 在算法1上稍微修改一下，丢掉操作3的玄学做法。

我们可以对旋转矩阵，$\left(\begin{array}{cc}cos(x)& sin(x)\\ -sin(x)& cos(x)\end{array}\right)$随机取几个$x$。

然后对除了第$i$位之外的每一位做这个变换，然后随意找一个位置$x$用操作4查出$a[x],a[x^{(}1<<i)]$。如果同时有值就说明了xor为1。

算法6

我们思考一下算法4，不难发现这其实是一个fwt！算法2中我们用它得到了一些non-trivial的信息，算法4中我们用$a[0]$的信息得到了一个部分分做法，$a[t]$的信息丢掉非常可惜，我们不妨思考一下它能告诉我们什么？

考虑fwt中$x$对$y$的贡献，显然绝对值肯定是$1$，由于fwt的矩阵只有 $A[1][1]=-1$。所以贡献的权值等于 $(-1{)}^{x\mathrm{\&}y}$。

fwt之后位置$t$的值等于 $(-1{)}^{x\mathrm{\&}t}+(-1{)}^{y\mathrm{\&}t}$。

为 $0$ 当且仅当 $x\mathrm{\&}t=y\mathrm{\&}t$，根据$F_2$下的乘法分配律也就是 $(x\oplus y)\mathrm{\&}t=0$。

所以我们 $a[t]\ne 0$ 当且仅当$t$和答案的and有偶数个1！

我们是不是随机线性无关的 $n$ 个 $t$ 就可以解出答案了呢？

很可惜，这些$t$并不是满秩的！比如说当答案是二进制$11$的时候，$t$只能是$00$和$11$，$00$没有用，也就是说最大秩为$n-1$。

因为每一维选不选定为$c_i$的话，我们其实有一个限制若干个$c_i$（ans为1的那些$c_i$）异或起来为0，所以秩只有$n-1$。

不过这只是偶数的情况，如果我们把它变成and有奇数个1，那么我们可以用$10$和$01$构成一组满的基！

考虑怎么变成奇数个1，只要在一个xor为1的位，应用算法4中的变换 $\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$ 即可。

我们每次枚举一位，然后应用变换 $\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$ 之后，用fwt随机$O(n)$个t，然后高斯消元判断一下秩是$n$还是$n-1$即可知道这一维是不是1。（考虑答案中只有一位是1的情况，就算在满秩情况接出了所有位，最差情况总是要枚举每一位）

询问复杂度$O(n^3)$。

算法7

我们用另外一个方向理解一下为什么秩只能有$n-1$，因为所有$x\oplus y=0$始终都会是xor方程的解。

xor方程组始终都有两个解$x\oplus y$和$0$，所以秩为$n-1$。

但是我们知道答案不可能是$0$，所以把它丢掉取$x\oplus y$输出即可。

期望要随机$O(n)$个随机向量会满秩，实际上更接近$n+1$。

询问复杂度$O(n^2)$，期望得分100分。

算法8

matthew99在验题的时候，猜想是fwt，于是，fwt之后暴力枚举$2^n$直到方程只有一个解。

询问复杂度$O(n^2)$，算法复杂度$O(n{2}^n)$。期望得分100分。

由于交互库很慢，所以只能让这种做法通过了。不过思考到fwt，可以说已经解决了这道题的一半了。

题目背景

其实这道题目相当于给出$n$个纠缠的量子比特，你每次可以旋转翻转（正交变换）其中一个量子或者是做一次观测（然后会坍缩到一个态）。

如果把题目中$2\times 2$的矩阵换成一个$2^3\times 2^3$的矩阵作用在三位上，并且允许振幅是复数，就是量子计算的理论模型了。

这个算法其实正是量子计算机上寻找循环节的Simon算法，正是这个算法启发了著名的Shor算法。

FWT和高斯消元从入门到精通