LC 2939. 最大异或乘积

https://leetcode.cn/problems/maximum-xor-product/description/

我感觉这题目有个关键点，就是其实我们可以考虑每个bit的影响，不需要过多考虑上下文。

如果是a, b在某一个bit上相同，那么非常好解决。问题在于不同的地方，比如Ai=0, Bi=1这样的情况

如果我们将Ai=1, Bi=0的话，那么其实相当于选择的是 `B(n..i+1) 0 B(i-1..0) x (1 << i)`
如果我们将Ai=0, Bi=1的话，那么其实相当于选择的是 `A(n..i+1) 0 A(i-1..0) x (1 << i)`

对于 `B(i-1..0)` 以及 `A(i-1..0)` 这些都是将来要选择的元素，可以独立进行选择。

但是 `B(n..i+1)` 以及 `A(n..i+1)` 已经是之前进行选择的，

如果其中一个更大的的话，那么我们就应该选择。
如果两者相同的话，那么我们就可以任意选择一个。注意这里选择了任意一个之后，A, B前缀就开始出现了差异。

我的解释稍微有点按照直觉表达，形式证明上有点不太行。

class Solution:
    def maximumXorProduct(self, a: int, b: int, n: int) -> int:
        MOD = 10 ** 9 + 7

        pa = a >> n
        pb = b >> n
        ans = 0
        for i in reversed(range(n)):
            ca = (a >> i) & 0x1
            cb = (b >> i) & 0x1
            bit = 0
            if ca == cb == 0:
                bit = 1
            elif ca == cb == 1:
                pass
            else:
                if pa >= pb:
                    # preserve pa
                    bit = (1 - cb)
                else:
                    bit = (1 - ca)
            # print((pa, pb), ca, cb, bit)
            ans = (bit << i) | ans
            pa = (pa << 1) | (ca ^ bit)
            pb = (pb << 1) | (cb ^ bit)

        return ((ans ^ a) * (ans ^ b)) % MOD