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)