8VC Venture Cup 2016 - Final Round (Div. 1 Edition) B. XOR Equation
B. XOR Equation
$n$の$i$ bit目を$x_i$と書くとして、
- $x_i = 1$なら
- $a_i = 1 \land b_i = 0$あるいは
- $a_i = 0 \land b_i = 1$。
- $x_i = 0$なら
- $a_i = 1 = b_i = 1$あるいは
- $a_i = b_i = 0$。
したがって、
- $x_i = 1$なら
- いずれにせよ$a_i + b_i = 1$。
- $x_i = 0$なら
- $a_i + b_i = 2$あるいは
- $a_i + b_i = 0$。
なので$s - x$と$x$を比較すれば$a,b$の存在が判定できる。 存在するなら、$a,b$を正でなく非負の範囲に拡張すれば、$2^{ {\rm popcount}(x)}$個存在する。
#!/usr/bin/env python3
s, x = map(int,input().split())
mod = (1<<40) - 1
assert s < mod and x < mod
y = (s - x + mod) % mod
if y & (x << 1 | 1):
ans = 0
else:
ans = 2 ** bin(x).count('1')
if y == 0:
ans -= 2
print(ans)