与えられた和を得るためにシーケンス要素を使ってxorに番号を見つける

Question

私は最近、次の問題を抱えています：x_i (x_i < 2^60)はn (n < 10^5)の整数と整数S (S < 2^60)は次のようになります。

。例えば

：aため

x = [1, 2, 5, 10, 50, 100] 
S = 242 

可能な解決策は、21、23、37、39、であるが、最小の一つから少しずつ結果を構築することができる21

(1^21) + (2^21) + (5^21) + (10^21) + (50^21) + (100^21) 
= 20 + 23 + 16 + 31 + 39 + 113 
= 242 

Answer 1

ありますボトム。最下位ビットから始めて、aの最下位ビットとして0と1を試して、sum-xorの最下位ビットがSの対応ビットと一致するかどうかを確認してから、次の最下位ビットを試して前のステップからのキャリーを伝播してください。

aのビットごとに0,1または2の選択肢がある可能性があります。最悪の場合、異なる分岐を探索し、最小の結果を与えるものを選択する必要があります。指数関数的な振る舞いを避けるために、私たちは以前に見られたキャリーの結果を特定のビットでキャッシュします。これは、入力リストの長さがnである場合、kが結果の最大ビット数であり、nがキャリーの最大値であるO（kn）の最悪の場合の複雑さをもたらす。

ここでこれを実現するいくつかのPythonコードです：解はありません場合

max_shift = 80 

def xor_sum0(xs, S, shift, carry, cache, sums): 
    if shift >= max_shift: 
     return 1e100 if carry else 0 
    key = shift, carry 
    if key in cache: 
     return cache[key] 
    best = 1e100 
    for i in xrange(2): 
     ss = sums[i][shift] + carry 
     if ss & 1 == (S >> shift) & 1: 
      best = min(best, i + 2 * xor_sum0(xs, S, shift + 1, ss >> 1, cache, sums)) 
    cache[key] = best 
    return cache[key] 

def xor_sum(xs, S): 
    sums = [ 
     [sum(((x >> sh)^i) & 1 for x in xs) for sh in xrange(max_shift)] 
     for i in xrange(2)] 
    return xor_sum0(xs, S, 0, 0, dict(), sums) 

、コードが大（> = 1e100）浮動小数点数を返します。

ここでは、指定した範囲内のランダムな値を選択し、ランダムaを選択してSを計算して解決するテストを行います。 aの値は必ずしも一意ではないため、コードはSを計算するために使用されたものより小さいaを見つけることがあります。

import random 
xs = [random.randrange(0, 1 << 61) for _ in xrange(random.randrange(10 ** 5))] 
a_original = random.randrange(1 << 61) 
S = sum(x^a_original for x in xs) 
print S 
print xs 

a = xor_sum(xs, S) 
assert a < 1e100 
print 'a:', a 
print 'original a:', a_original 

assert a <= a_original 

print 'S', S 
print 'SUM', sum(x^a for x in xs) 

assert sum(x^a for x in xs) == S