Cho dãy số nguyên a gồm N phần tử. Đếm xem có bao nhiêu cặp (i, j) trong đó i < j và a[i] = a[j]Input Specification Dòng đầu là N số lượng phần tử của dãy. (0 < N <= 100000) Dòng tiếp theo chứa n số nguyên là các phần tử của dãy số a (0< a.i <=1000)Output SpecificationSố cặp (i,j) thỏa mãn yêu cầu. (Ngôn ngữ C++ nha)
Mình cần một tay giúp đây! Ai có thể đóng góp ý kiến để mình giải quyết câu hỏi này được không?

Cách 1:
```cpp
#include
#include
using namespace std;

int main() {
int N;
cin >> N;

unordered_map countMap;

for (int i = 0; i < N; i++) {
int num;
cin >> num;
countMap[num]++;
}

int countPairs = 0;
for (auto& pair : countMap) {
int count = pair.second;
countPairs += count * (count - 1) / 2;
}

cout << countPairs << endl;

return 0;
}
```

Cách 2:
```cpp
#include
#include
using namespace std;

int main() {
int N;
cin >> N;

vector arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}

int countPairs = 0;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (arr[i] == arr[j]) {
countPairs++;
}
}
}

cout << countPairs << endl;

return 0;
}
```

Câu trả lời cho câu hỏi: Để đếm số cặp (i, j) thỏa mãn điều kiện i < j và a[i] = a[j], ta có thể sử dụng cách 1 với cấu trúc dữ liệu unordered_map để đếm số lần xuất hiện của từng phần tử trong mảng. Sau đó, ta tính số cặp thỏa mãn bằng cách lấy tổng số cặp chính phương của số lần xuất hiện của từng phần tử. Hoặc ta cũng có thể sử dụng cách 2 với hai vòng lặp duyệt mảng để đếm số cặp thỏa mãn điều kiện trực tiếp.

Đảm bảo việc sử dụng map sẽ giúp giảm độ phức tạp của thuật toán xuống O(N) với N là số lượng phần tử của dãy số a.

Cuối cùng, ta trả về số cặp đã tính được là kết quả của bài toán.

Sau đó, ta duyệt qua map để tính tổng số cặp (i, j) thỏa mãn yêu cầu. Với mỗi phần tử a[i], số cặp thỏa mãn sẽ là tổ hợp chập 2 của số lần xuất hiện của phần tử đó.

Đầu tiên, ta sử dụng một map để đếm số lần xuất hiện của từng phần tử trong dãy số a.