โปรแกรมหาผลคูณสเกลาร์ของเวกเตอร์จากลำดับอนันต์ใน Python

กำหนดจำนวนเต็ม 3 ตัว c, m, n สร้างลำดับอนันต์ที่ค่าแรกคือ 0 ค่าที่สองคือ c และจากค่าที่ 3 เป็นต้นไป k_i = (k_{i-2} + k_{i-1}) mod m สร้างค่าจนถึง k_{2n+1} จากนั้นนำค่าติดกัน 2 ค่าเป็นพิกัด (x, y) ของเวกเตอร์ 2 มิติ ได้ n เวกเตอร์ เริ่มจากค่าที่ 3 ของลำดับ

หาจำนวนค่าเศษที่ต่างกันในเซต S โดยที่ S มีค่าเป็นผลคูณสเกลาร์ของเวกเตอร์ i และ j โดยที่ 1 ≤ i, j ≤ n และ i ≠ j หากค่ามากเกินไป ให้ modulo ด้วย m

ตัวอย่าง

อินพุต: 5, 6, 4 → เอาต์พุต: 3

• ลำดับที่ได้: [0, 5, 5, 4, 3, 1, 4, 5, 3, 2]
• เวกเตอร์: (5, 4), (3, 1), (4, 5), (3, 2)
• ผลคูณสเกลาร์มีแค่ 3 ค่าเศษที่ต่างกัน modulo 6
• ผลลัพธ์: 3 mod 6 = 3

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

1. ถ้า n == 1 คืนค่า 0
2. สร้างอาร์เรย์ temp_arr ขนาด 2*n+2
3. คำนวณลำดับด้วยสูตร Fibonacci modulo m
4. คำนวณผลคูณสเกลาร์ของคู่เวกเตอร์ที่ต่างกัน
5. นับค่าเศษที่ไม่ซ้ำกัน

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

def solve(c, m, n):
    if n == 1:
        return 0
    else:
        temp_arr = [0] * (2 * n + 2)
        temp_arr[0] = 0
        temp_arr[1] = c
        arr2 = []
        
        for i in range(2, 2 * n + 2):
            temp_arr[i] = (temp_arr[i - 1] + temp_arr[i - 2]) % m
        
        for i in range(2, 2 * n - 2, 2):
            temp = (temp_arr[i] * temp_arr[i + 2] + temp_arr[i + 1] * temp_arr[i + 3]) % m
            arr2.append(temp)
            temp = (temp_arr[i] * temp_arr[i + 4] + temp_arr[i + 1] * temp_arr[i + 5]) % m
            arr2.append(temp)
        
        temp = (temp_arr[2 * n - 2] * temp_arr[2 * n] + temp_arr[2 * n - 1] * temp_arr[2 * n + 1]) % m
        arr2.append(temp)
        
        arr2 = set(arr2)
        return len(arr2)

print(solve(5, 6, 4))

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

Input:  5, 6, 4
Output: 3