Hiểu bài toán

Bài toán yêu cầu đếm số lượng các vecto khác nhau sao cho cả hai điểm đầu và điểm cuối của vecto đều nằm trong tập hợp n điểm cho trước. Yếu tố quan trọng là 'vecto khác nhau' được xác định bởi sự khác biệt về độ dài hoặc hướng, tức là hai vecto có cùng độ dài và cùng hướng (từ điểm đầu đến điểm cuối) sẽ được coi là một. Do đó, bài toán về bản chất là đếm số cặp điểm có thứ tự (ordered pairs) khác nhau từ tập n điểm.

Các cách tiếp cận

Cách Suy luận Toán học

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    cout << n * (n - 1);
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là cách tiếp cận trực quan nhất. Với mỗi điểm trong n điểm, ta có thể chọn nó làm điểm đầu của vecto. Điểm này có n-1 lựa chọn làm điểm cuối (vì điểm đầu và điểm cuối phải khác nhau). Do đó, tổng số vecto khác nhau là n * (n - 1). Ví dụ với n=3, ta có 3 lựa chọn điểm đầu và 2 lựa chọn điểm cuối cho mỗi điểm đầu, tổng cộng 3*2=6 vecto.

Cách Thực thi Trực tiếp

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long result = n * (n - 1);
    cout << result;
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là cách viết mã của phương pháp Suy luận Toán học. Do ràng buộc n ≤ 10^6, kết quả n(n-1) có thể lên tới ~10^12, vượt quá giới hạn của kiểu int (210^9). Vì vậy, cần sử dụng kiểu dữ liệu long long (hoặc int64_t) để lưu trữ kết quả mà không bị tràn số (overflow).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán quy về việc đếm số cặp điểm có thứ tự (ordered pairs) vì mỗi cặp (điểm đầu, điểm cuối) tạo ra một vecto duy nhất.
• Với n điểm, số lượng cặp có thứ tự là n * (n - 1).

Lỗi thường gặp

• Sử dụng kiểu dữ liệu int thay vì long long dẫn đến lỗi tràn số (integer overflow) khi n đủ lớn (ví dụ n = 10^6 thì n(n-1) = 999,999,000,000 > 210^9).
• Nhầm lẫn giữa vecto và đoạn thẳng: Vecto có hướng nên (A, B) khác với (B, A), do đó phải dùng công thức n(n-1) thay vì n(n-1)/2 (dành cho đoạn thẳng không có hướng).