Chương trình tìm giá trị XOR của các phần tử cụ thể từ danh sách sinh ra trong Python

Cho một danh sách chứa các số tự nhiên. Loại bỏ tất cả các số có hai bit 1 liên tiếp trong biểu diễn nhị phân, tạo danh sách mới Z. Cho danh sách input_list chứa các chỉ số. Tìm giá trị XOR của các phần tử trong Z tại các chỉ số đó.

Ví dụ

Input: input_list = [3, 4, 5] → Output: 9

Giải thích: Z[3]=4, Z[4]=5, Z[5]=8. XOR: 4 ⊕ 5 ⊕ 8 = 9.

Thuật toán

Sử dụng dãy Fibonacci và biểu diễn Zeckendorf để sinh danh sách Z hiệu quả.

1. Xây dựng danh sách Fibonacci f_list đến giá trị lớn nhất (10^18)
2. Hàm zeck_num(k, f_list) chuyển chỉ số k thành giá trị trong Z bằng cách dùng biểu diễn Zeckendorf (mỗi số tự nhiên là tổng các số Fibonacci không liên tiếp)
3. Tính XOR lũy tiến của các giá trị tại các chỉ số trong input_list
4. Trả về kết quả modulo 10^9+7

Mã nguồn

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]))  # Output: 9

Giải thích chi tiết

Dãy Z là các số không có hai bit 1 liên tiếp trong nhị phân (còn gọi là số Fibbinary). Các số đầu tiên: 0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 16, 17...

Hàm zeck_num sử dụng tính chất: số Fibbinary thứ k tương ứng với biểu diễn nhị phân của k được "chèn" vào các vị trí Fibonacci. Cụ thể, nếu k = Σ F_i (biểu diễn Zeckendorf), thì Z[k] = Σ 2^i.

Ví dụ: k=3 = F_2 (2) + F_1 (1) → Z[3] = 2^2 + 2^1 = 4+2=6? Wait, kiểm tra lại: Z[3]=4 trong ví dụ. Thực tế thuật toán dùng f_list=[1,2,3,5,8...] (bỏ F_1=1). Cần xem kỹ: f_list[0]=1, f_list[1]=2, f_list[2]=3... Với k=3: i=2 (f=3) → res+=4, k=0. Kết quả 4. Đúng.