โปรแกรมหาค่า XOR ขององค์ประกอบเฉพาะจากลิสต์ที่สร้างขึ้นใน Python

สมมติว่ามีลิสต์ที่มีตัวเลขธรรมชาติ จากนั้นนำตัวเลขที่มีเลข 1 ติดกันสองตัวในรูปแบบไบนารีออก จะได้ลิสต์ใหม่ชื่อ Z กำหนดลิสต์ input_list ที่มีค่าจำนวนเต็ม ต้องการหาค่า XOR ขององค์ประกอบใน Z ที่มีดัชนีตรงกับค่าใน input_list

ตัวอย่าง

ถ้า input_list = [3, 4, 5] ผลลัพธ์จะเป็น 9

ที่ดัชนี 3, 4, 5 ของ Z มีค่า 4, 5, 8 ดังนั้น 4 XOR 5 XOR 8 = 9

วิธีแก้ปัญหา

1. สร้างฟังก์ชัน zeck_num() สำหรับคำนวณค่า Zeckendorf representation
2. สร้างลิสต์ฟีโบนัชชี f_list จนถึงค่าสูงสุด 10^18
3. วนลูปคำนวณ XOR ของแต่ละดัชนีใน input_list
4. คืนค่าผลลัพธ์ modulo 10^9 + 7

ตัวอย่างโค้ด

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]))

อินพุต / เอาต์พุต

Input:  [3, 4, 5]
Output: 9

หลักการ: ใช้การแทนค่า Zeckendorf (Zeckendorf representation) ซึ่งทุกจำนวนเต็มบวกสามารถแทนได้เป็นผลรวมของเลขฟีโบนัชชีที่ไม่ติดกัน แล้วแปลงเป็นรูปแบบไบนารีเพื่อคำนวณ XOR