Pythonで生成されたリストから特定の要素のXOR値を見つけるプログラム

自然数を含むリストが与えられたとしましょう。ここで、そのリストから、バイナリ表現に2つの連続する1を含むすべての数値を削除し、Zという別のリストを生成します。これで、整数値を含む別のリスト'input_list'が与えられます。 input_listでインデックスが指定されているZから、指定された要素のXOR値を見つける必要があります。

したがって、入力がinput_list =[3、4、5]のようである場合、出力は9になります。

Zのインデックス3、4、および5。値は4、5、および8です。したがって、4 XOR 5 XOR8=9です。

これを解決するには、次の手順に従います-

• 関数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]
  • return res
• MOD：=10 ^ 9 + 7
• max_val：=10 ^ 18
• f_list：=値1と2を含む新しいリスト
• f_listの最後の要素<=max_val、do
  • f_listの最後の要素+f_listの最後から2番目の要素をf_listの最後に挿入します
• res：=0
• input_listのインデックスごとに、
  を実行します。
  • res：=res XOR zeck_num（index、f_list）
• return res mod MOD

例

理解を深めるために、次の実装を見てみましょう-

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