Python程序：查找生成列表中特定元素的异或值

假设我们得到一个包含自然数的列表。现在，从该列表中移除所有二进制表示中包含两个连续1的数字，并生成另一个名为Z的列表。现在，我们得到另一个包含一些整数值的列表“input_list”。我们需要找出Z中指定元素的异或值，这些元素的索引在input_list中指定。

因此，如果输入类似于input_list = [3, 4, 5]，则输出将为9。

在Z的索引3、4和5处；值分别为4、5和8。所以，4 XOR 5 XOR 8 = 9。

为了解决这个问题，我们将遵循以下步骤：

定义一个函数zeck_num()。这将获取k和f_list作为参数。
- res := 0
- 对于范围从(f_list的大小 - 1)到-1的i，递减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的最后一个元素 + f_list的倒数第二个元素插入到f_list的末尾
res := 0
对于input_list中的每个索引，执行以下操作：
- res := res XOR zeck_num(index, f_list)
返回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]

输出

Arnab Chakraborty

更新于：2021年10月20日

125 次浏览

开启您的职业生涯

通过完成课程获得认证

开始学习