P4443 [COCI2017-2018#3] Dojave 题解

前言：

不知道为什么都用的哈希，我的优化暴力全都均摊了，直接最优解（

简要题意：

给定 \(m\) 和 \(0\sim 2^m-1\) 的全排列 \(a_i\)，问有多少子区间满足交换两个不同位置后，整个区间异或和为 \(2^m-1\)

\(m\le 20\)。

分析：

正难则反，考虑求出不合法的区间个数。

以下记 \(n=2^m-1\)。

结论：

若区间内异或和为 \(0\)，并且可以两两配对使得两两异或和为 \(n\)，则这个区间不合法。

证明：

首先如果区间异或和已经为 \(n\)，那么只需要交换区间内或区间外的两个数即可。

否则，设区间 \(S\) 的异或和为 \(t\)。

那么就是找一对 \(i,j\) 使得 \(i\oplus j=t\oplus n(i\in S,j\notin S)\)，不难看出 \(i,j\) 一定是成对出现的，那么若想要不合法，唯一的可能是集合内两两配对的异或和为 \(t\oplus n\)。

问题转化为找到这种情况。

奇数长度的一定合法，因为一定能找到一个数，和它配对的在区间外。

对于偶数长度的情况，如果配对数量为奇数，不妨以三个为例，有：

由于 \(n\ne 0\)，显然不存在这种情况。

配对数量为偶数的，不妨以两个为例，有：

也就是说，当 \(t=0\) 时这个区间不合法，那么两两配对的异或和就是 \(n\) 了。

至此证毕，下面考虑统计。

定义 \(link_i\) 表示与 \(a_i\) 配对的数的位置，即 \(pos_{n\oplus a_i}\)。

对于区间 \([l,p]\) 和 \([p+1,r]\)，如果这两个区间都不合法，则 \([l,r]\) 也一定不合法，这点通过结论不难看出，那么我们只需要找对于每个点最近的不合法位置在哪里即可。

考虑一个最暴力的拓展方法，枚举一个左端点 \(l\)，那么右端点 \(r\) 至少应在 \(link_l\)，下面判断这个区间是否合法。

• 如果 \(\exists\,p\in[l,r],link_p<l\)，即区间内存在一个数，与其配对的数在 \(l\) 左边，那么直接跳出，因为我们钦定了 \(l\) 为左端点。
• 如果 \(\exists\,p\in[l,r],link_p>r\)，那么更新 \(r=link_p\)，再重复这个过程，直到跳出或者 \(\forall\, p\in[l,r],l\le link_p\le r\)，即区间内两两配对。

这样的暴力做法可以找到每个最短的不合法区间，利用双指针可以在 \(O(n^2)\) 的时间内求出，下面考虑优化。

注意到我们暴力跳右端点的时候，跳出或者更新答案的点都是区间 \(link\) 最小值或最大值，那么就可以在 \(O(mn)\) 的时间内预处理出 \(link\) 的 ST 表实现 \(O(1)\) 更新。

之后对于每个点暴力跳的复杂度就变成了均摊 \(O(1)\) 的，简要证明如下：

对于每一对匹配 \((i,link_i)\)，设 \(i<link_i\)，那么当左端点枚举到 \(i\) 的时候看起来会很暴力的一直跳过去，极限状态下单次 \(O(n)\)，但当左端点枚举到 \(link_i\) 的时候，右端点 \(i<link_i\) 会直接跳出，所以实际上每一对匹配只会跳一次，均摊 \(O(1)\)。

统计同理，暴力枚举左端点，暴力跳最近的不合法区间，由于我们要计算的区间长度必须为 \(4\) 的倍数，那么只需要统计一路上 \(\bmod 4\) 同余的个数即可，为了防止算重，对于每个跳到的点标记一下，如果枚举到了标记点直接跳过即可，每个点的时间复杂度同样是均摊 \(O(1)\)。

总时间复杂度为 \(O(mn+n+n)=O(mn)=O(m\times 2^m)\)