P10118 『STA - R4』And

P10118 『STA - R4』And

题意：给定 A，B，求 \(\sum y - x\)，其中 x，y 满足：

• x < y
• x + y = A
• x & y = B

对于加运算和与运算，有 x + y = 2(x & y) + (x ^ y)。
那么令 C = x ^ y = A - 2B。
这里判断下无解情况，

• C < 0， 显然无解。
• C ^ B != 0，与位运算性质矛盾，无解。

当然如果 C < 0，那么 C ^ B 也不等于 0，所以只需判第二个条件即可。

因为 x & y = B，所以 B 为 1 的位置 x，y 也为 1。
现在只需讨论 C 中的 1 如何分配。
最高位的 1 一定给 y。
对于非最高位，一种方案取反后仍是合法的。
如
x = 0 _ 1 _ 0 _ _，y = 1 _ 0 _ 1 _ _
x'= 0 _ 0 _ 1 _ _，y'= 1 _ 1 _ 0 _ _
那么这互相匹配的方案对答案的贡献只有 C 最高位的 1
设最高位在第 i 位，
则 \(ans = 2 ^ {popcount(C) - 1} \cdot 2 ^ i\)

void solve() {
	ll A, B; cin >> A >> B;
	ll C = A - 2 * B;
	if(!C || (B & C)) cout << "0\n"; 
	else cout << ((1ll << __builtin_popcountll(C) - 1) % P) * ((1ll << 63 - __builtin_clzll(C)) % P) % P << '\n';
}