【MX-X16-T2】「DLESS-3」XOR and Multiply 题解

记号与约定

• $x'\coloneqq x\oplus z$；
• $y'\coloneqq y\oplus z$；
• $k_i\coloneqq k$ 的第 $i$ 位（$0\le i<h$，$k$ 为本文或题目中定义的整数变量）；
• 本文中所有的「位」均指二进制位。

思路

1. $x_i=y_i$
   直接置 $x'_i=y'_i=1$，即置 $z_i=\bar{x_i}=\bar{y_i}$；
2. $x_i\not =y_i$
   比较 $x'$ 与 $y'$，将较小者的第 $i$ 位置为 $1$。
   为什么这么做

   由于我们是由高位向低位枚举，在本轮处理中较大者在最终结果中必然较大。

   根据位值原理将每一位拆开，则 $x'$ 与 $y'$ 中的任意一个数在本轮结束后的贡献都可以看作是高 $h-i$ 位的贡献加上第 $i$ 位的贡献。高 $h-i$ 位的贡献固定，考虑第 $i$ 位的贡献。

   $x'_i$ 的贡献为 $2^ix'_iy'$，$y'_i$ 的贡献为 $2^iy'_ix'$。而 $x'_i$ 与 $y'_i$ 中必有一 $1$ 一 $0$，则选择置 $1$ 后贡献更大的，即在上述表达式中最后一个因数更大的置 $1$，即将较小者的第 $i$ 位置 $1$。

代码

#include <bits/stdc++.h>
#define DN(i, l, r) for(int i = (r); i >= (l); -- i)
using namespace std;
using ll = long long;
int t, x, y, h;
ll xz, yz; // xz:=x', yz:=y'

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while(t --){
		cin >> x >> y >> h;
		xz = yz = 0;
		DN(i, 0, h - 1){
			if((x >> i & 1) == (y >> i & 1)){
				xz |= 1 << i;
				yz |= 1 << i;
			}
			else if(xz > yz) yz |= 1 << i;
			else xz |= 1 << i;
		}
		cout << xz * yz << '\n';
	}
}