「AT1727」「CODE FESTIVAL 2015 OKINAWA OPEN」Enormous XOR Rectangle

\(H\times W\) 的矩阵，第 \(i(0\le i< H)\) 行第 \(j(0\le j< W)\) 列的数为 \(iW+j\)。

选一个子矩阵，使得该子矩阵中所有元素 xor 的值最大。输出这个值。

\(H,W\le 10^9\)

记 \(n\) 为满足 \(2^{n-1} \le H\times W-1 < 2^n\) 的值。所以答案一定 \(< 2^n\)。

当 \(2^{n-1}-1\) 与 \(2^{n-1}\) 左右相邻时，由于 \((2^{n-1}-1)\text{ xor }(2^{n-1})=2^n-1\)，所以答案显然为 \(2^n-1\)。

否则，此时的情况一定是 \(2^{n-1}-1\) 在某行的最后一列，\(2^{n-1}\) 在这一行下面一行的第一列，所以 \(W\) 此时一定能表示为 \(2^m(0\le m\le n-1)\)。例如：

1
2
3
4
5
6
7
8

 0  1  2  3
 4  5  6  7
 8  9 10 11
12 13 14 15
-----------
16 17 18 19
20 21 22 23
24 25 26 27

图中 \(n=5,2^{n-1}-1=15,2^{n-1}=16\)。

这种情况下，下界显然是 \(2^n-2^m=2^n-W\)，即 \((2^{n-1}-1)\text{ xor }(2^{n-1}-1+2^m)\)。记这个下界为 \(d\)，考虑是否有答案超过 \(d\) 的情况。

通过观察可以发现：

1. 一行中所有数的最高 \(n-m\) 位都相同。
2. 一列中所有数的最后 \(m\) 位都相同。

继续分析可以得到：

1. 若选偶数行，xor 值的最后 \(m\) 位都是 \(0\)，答案 \(\le d\)。
2. 若选偶数列，xor 值的最高 \(n-m\) 位都是 \(0\)，答案 \(\le d\)。
3. 若选奇数列，考虑每一行，一定在该行中存在一个数与该行的 xor 值相等，且每一行的这个数一定在同一列，所以选奇数列的所有情况相当于选 \(1\) 列的所有情况。那么，为了得到最优的答案，一定选择最后一列。

综上，我们选择的范围变成了最后一列，选奇数行。并且，若存在这样的答案，答案最后的 \(m\) 位一定都为 \(1\)。那么超过 \(d\) 的答案只可能是 \(2^n-1\)。

所以，问题变成了以一个序列上的问题：

\(H\) 个数，第 \(i(0\le i< H)\) 个数为 \(i\)，问是否存在一个区间，使得这个区间的 xor 值为 \(2^{n-m}-1\)。

例如：

1

0 1 2 3 | 4 5 6

分界线左边最高位为 \(0\)，右边最高位为 \(1\)。由于要达到 \(2^{n-m}-1\)，分界线右边必须选奇数个，才能保证最高位为 \(1\)。

根据 \((2n)\text{ xor }(2n+1)=1\ (n\ge 0)\)，可以证明分界线左边的数不需要选择。

根据 \(0\text{ xor }1\text{ xor }2\text{ xor }\cdots\text{ xor }(2^n-1)=0 \ (n\ge 2)\)，可以证明右边若要选出 \(2^{n-m}-1\)，必须选择 \(2^{n-m-1}\sim 2^{n-m}-2\) 的所有数。

注意上述结论是一般情况，\(n-m\) 特别小时可以特殊处理，不过仍然可以证明下面总结中的结论是正确的。

根据上面的分析、推导和转化，可以得到如下结论：

若 \(W\) 不是 \(2\) 的幂次，或者 \(H\) 是 \(2\) 的幂次，或者 \(H+1\) 是 \(2\) 的幂次，则答案为 \(2^n-W\)，否则答案为 \(2^n-1\)。

技巧

判断一个数是否是 \(2\) 的幂次，可以根据 \(lowbit\) 与该数本身是否相等来判断。