Mình xin chia sẻ lời giải bài này như sau:

Đầu tiên dựa vào tính chất của số đặc biệt. Vì \(a_i\sim 10^6\) nên có thể dễ dàng tìm được tập số đặc biệt như sau: \(S=\){\(1,11,111,....,9999999\)}. Và tập này có \(63\) số.

Tiếp theo bài toán quy về: Cho trước một số \(Q\) và một mảng \(a\) gồm \(n\) phần tử. Hỏi có bao nhiêu cặp (không lặp) thoả mãn tổng của chúng bằng \(Q\).

Đây là một bài toán quen thuộc. Đơn giản ta dùng một mảng để lưu tần số của từng phần tử trong mảng, và sử dụng kĩ thuật đếm bình thường là có thể giải quyết bài toán.

Mình xin lấy một ví dụ để các bạn hình dung rõ hơn:

Cho trước mảng \(a\) gồm \(4\) phần tử: \(1,1,2,2\) và số \(Q=3\). Hỏi có bao nhiêu cặp (không lặp) thoả mãn yêu cầu bài toán.

Bước 1: Ta tạo ra mảng f. Mảng này có chức năng lưu tần số của từng phần tử trong mảng. Ở đây ta có: f[1]=2,f[2]=2.

Bước 2: Ta sẽ duyệt từng phần tử \(a_i\) trong mảng và đếm xem có bao nhiêu phần tử \(a_j(i\ne j)\) thoả mãn \(a_i+a_j=3\). Và kết quả chính là \(f[3-a[i]]\).

Và ta chỉ việc cộng tất cả các kết quả của bước 2 lại. Sau đó chia cho \(2\). Vì mỗi lần lặp qua hết các phần tử của mảng, thì số cặp thoả mãn sẽ bị lặp 2 lần.

Như vậy ta đã giải quyết xong bài toán. Độ phức tạp là: \(O(63 * n)\)

Ps: Khi giải bài này, mình rút ra mình số kinh nghiệm sau: Việc dùng map,unordered_map để lưu tần số có vẻ tốn time hơn dùng mảng thông thường.

Các bạn có thể xem code của mình tại đây

Ps: Nếu có gì khó hiểu, các bạn cứ comment