Pythonで生成したリストから特定の要素のXOR値を求めるプログラム

自然数を含むリストが与えられたとします。まず、このリストから2進表現において「1」が連続して現れる数をすべて取り除き、残った数だけで新しいリストZを作成します。次に、いくつかの整数値を含む別のリストinput_listが与えられるので、Zのうちinput_listで指定されたインデックス位置にある要素のXOR値を求めます。

たとえば、input_list = [3, 4, 5] が入力された場合、出力は 9 になります。

Zのインデックス3、4、5に対応する値はそれぞれ 4、5、8 です。したがって、4 XOR 5 XOR 8 = 9 となります。

解法のアプローチ

この問題を効率的に解く鍵となるのはフィボナッチ数列です。「2進表現に連続する1を含まない数」と「互いに隣接しないフィボナッチ数の和(ゼッケンドルフ表現)」との間には一対一の対応関係があります。この性質を利用すると、リストZを実際に構築しなくても、インデックスkに対応するZの要素を直接計算できます。

具体的には、以下の手順で解きます。

• 関数 zeck_num() を定義する(引数は k と f_list)
  • res := 0
  • i を f_list のサイズ − 1 から −1 まで、1ずつ減らしながら繰り返す
    • k >= f_list[i] ならば
      • res := res + 2^i
      • k := k − f_list[i]
  • res を返す
• MOD := 10^9 + 7
• max_val := 10^18
• f_list := 値 1 と 2 を含む新しいリストを作成
• f_list の最後の要素が max_val 以下である間、次を繰り返す
  • f_list の末尾に「最後の要素 + 後ろから2番目の要素」を追加
• res := 0
• input_list の各 index について
  • res := res XOR zeck_num(index, f_list)
• res mod MOD を返す

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def zeck_num(k, f_list):
    res = 0
    for i in range(len(f_list)-1, -1, -1):
        if k >= f_list[i]:
            res += 2**i
            k -= f_list[i]
    return res

def solve(input_list):
    MOD = 10**9+7
    max_val = 10**18
    f_list = [1, 2]
    while f_list[-1] <= max_val:
        f_list.append(f_list[-1] + f_list[-2])
    res = 0
    for index in input_list:
        res ^= zeck_num(index, f_list)
    return res % MOD

print(solve([3, 4, 5]))

入力

[3, 4, 5]

出力

9

この実装では、あらかじめ10^18までのフィボナッチ数をリスト化しておくことで、任意の大きさのインデックスに対しても高速に対応する値を求められます。各クエリの計算量はフィボナッチ数列の長さに比例する程度であり、非常に効率的です。