Chương trình tìm số dư khác nhau của tích vô hướng các vector từ dãy vô hạn trong Python

Cho ba số nguyên c, m, n. Sinh dãy vô hạn: k₀=0, k₁=c, kᵢ=(kᵢ₋₂ + kᵢ₋₁) mod m. Sinh đến k_{2n+1}. Từ phần tử thứ 3, lấy cặp liên tiếp làm vector 2D: (k₂,k₃), (k₄,k₅), ..., tạo n vector. Tính tích vô hướng của mọi cặp vector (i,j) với i≠j, lấy modulo m. Đếm số giá trị dư khác nhau.

Ví dụ

Input: c=5, m=6, n=4 → Output: 3

Dãy: [0, 5, 5, 4, 3, 1, 4, 5, 3, 2]

Vector: (5,4), (3,1), (4,5), (3,2)

Tích vô hướng mod 6 cho 3 giá trị dư khác nhau.

Thuật toán

1. Nếu n=1, trả về 0 (không có cặp)
2. Sinh mảng temp_arr độ dài 2n+2 chứa dãy k
3. Tính tích vô hướng của các cặp vector theo quy luật đặc biệt:
   • Vector i với i+1: temp_arr[2i]×temp_arr[2i+2] + temp_arr[2i+1]×temp_arr[2i+3]
   • Vector i với i+2: temp_arr[2i]×temp_arr[2i+4] + temp_arr[2i+1]×temp_arr[2i+5]
   • Cặp cuối: vector n-1 với n
4. Loại trùng lặp, đếm số phần tử duy nhất

Mã nguồn

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

Giải thích logic vector

Với n=4, có 4 vector: v₁=(k₂,k₃), v₂=(k₄,k₅), v₃=(k₆,k₇), v₄=(k₈,k₉).

Cặp cần tính: (v₁,v₂), (v₁,v₃), (v₂,v₃), (v₂,v₄), (v₃,v₄). Code tính theo pattern tối ưu thay vì brute-force O(n²).