前言:
不知道为什么都用的哈希,我的优化暴力全都均摊了,直接最优解(
简要题意:
给定 \(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\)。
问题转化为找到这种情况。
奇数长度的一定合法,因为一定能找到一个数,和它配对的在区间外。
对于偶数长度的情况,如果配对数量为奇数,不妨以三个为例,有:
\[(t\oplus n)\oplus (t\oplus n)\oplus (t\oplus n)=t\oplus n\ne t \]由于 \(n\ne 0\),显然不存在这种情况。
配对数量为偶数的,不妨以两个为例,有:
\[(t\oplus n)\oplus (t\oplus n)=0=\!\!\!\!?\ \ t \]也就是说,当 \(t=0\) 时这个区间不合法,那么两两配对的异或和就是 \(n\) 了。
至此证毕,下面考虑统计。
定义 \(link_i\) 表示与 \(a_i\) 配对的数的位置,即 \(pos_{n\oplus a_i}\)。
对于区间 \([l,p]\) 和 \([p+1,r]\),如果这两个区间都不合法,则 \([l,r]\) 也一定不合法,这点通过结论不难看出,那么我们只需要找对于每个点最近的不合法位置在哪里即可。
考虑一个最暴力的拓展方法,枚举一个左端点 \(l\),那么右端点 \(r\) 至少应在 \(link_l\),下面判断这个区间是否合法。
这样的暴力做法可以找到每个最短的不合法区间,利用双指针可以在 \(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)\)