Python에서 생성된 목록에서 특정 요소의 XOR 값을 찾는 프로그램

<시간/>

자연수를 포함하는 목록이 있다고 가정합니다. 이제 그 목록에서 이진 표현에서 두 개의 연속적인 1을 포함하는 모든 숫자를 제거하고 Z라는 또 다른 목록을 생성합니다. 이제 일부 정수 값을 포함하는 또 다른 목록 'input_list'가 제공됩니다. input_list에 인덱스가 지정된 Z에서 지정된 요소의 XOR 값을 찾아야 합니다.

따라서 입력이 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
- i 범위(f_list -1의 크기)에서 -1까지, 1만큼 감소, do
  - k>=f_list[i]이면
    - res :=res + 2^i
    - k :=k - f_list[i]
- 반환 결과
MOD :=10^9 + 7
최대값:=10^18
f_list :=값 1과 2를 포함하는 새 목록
f_list <=max_val의 마지막 요소인 동안 do
- f_list의 마지막 요소 삽입 + f_list의 끝에 f_list의 두 번째 마지막 요소 삽입
res :=0
input_list의 각 인덱스에 대해 다음을 수행합니다.
- res :=res XOR zeck_num(index, f_list)
Return 모드 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]