Đếm cặp
Đề bài
Đếm cặp
Hôm nay Tèo được học về luỹ thừa của $2$. Qua bài học, Tèo được biết rất nhiều ứng dụng của luỹ thừa của $2$ như số cách chọn một tập con của tập hợp, biểu diễn số nguyên dưới dạng nhị phân, ... Tuy đã hết chương trình nhưng vẫn còn chút thời gian, cô giáo quyết định ra một bài tập cho lớp làm. Cô viết lên bảng một vài số nguyên và yêu cầu lớp đếm số cách nhóm hai số khác nhau sao cho tổng của chúng là một luỹ thừa của $2$. Tèo nhanh chóng nhìn vào bảng và viết ra kết quả đến mức cô giáo phải ngạc nhiên. Bạn hãy giúp cô kiểm tra xem kết quả của Tèo có đúng không nhé.
Input:
- Dòng đầu tiên chứa số nguyên $n$ $(1 \le n \le 10^5)$ là số lượng số mà cô giáo viết lên bảng.
- Dòng tiếp theo chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 10^9)$ là các số mà cô viết.
Output: Một số nguyên duy nhất là số lượng cặp có tổng là một luỹ thừa của $2$.
Scoring:
- Subtask 1 (30% số điểm): $n \le 10^3$.
- Subtask 2 (30% số điểm): $a_i \le 10^3$.
- Subtask 3 (40% số điểm): Không có ràng buộc gì thêm.
Giải thích ví dụ: Có 3 cặp thoả mãn là $(a_1, a_5)$, $(a_2, a_3)$ và $(a_2, a_6)$.
6
4 7 1 5 4 93Lời mở đầu
Chú ý chữ "hai số khác nhau" trong đề nghĩa là hai vị trí khác nhau, còn giá trị thì có thể bằng nhau: trong ví dụ, cặp $(a_1, a_5) = (4, 4)$ có tổng $8 = 2^3$ vẫn được tính. Bài này cùng "họ" với bài đếm cặp có tổng bằng $s$, chỉ khác là bây giờ tổng có thể là bất kỳ lũy thừa nào của 2. Mẹo then chốt: tổng hai số không quá $2 \cdot 10^9$ nên chỉ có 31 lũy thừa của 2 cần thử, ta "đếm cặp có tổng bằng $s$" cho từng $s = 2, 4, \ldots, 2^{31}$ bằng map.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test:
| Test | n | $a_i$ lớn nhất | Tỉ lệ số > 1000 | Đáp án lớn nhất |
|---|---|---|---|---|
| 1–10 | 2 … 20 | 491 | 0% | 7 |
| 11–30 | 31 … 969 | 939.555.828 | 97% | 284 |
| 31–60 | 763 … 31.878 | 973.077.883 | 23% | 794.908 |
| 61–90 | 13.081 … 39.692 | 973.069.148 | 97% | 48.470 |
| 91–100 | 100.000 … 100.000 | 973.741.824 | 100% | 79.772 |
Đối chiếu subtask của đề với test thật và số test đúng của từng cách:
| Subtask | Đề ghi | Test | Thực tế trong test | Cách 1 (vét cạn) | Cách 2 (mảng đếm) | Cách 3 (map) |
|---|---|---|---|---|---|---|
| 1 (30%) | $n \le 10^3$ | 1–30 | đúng: $n \le 969$ | 30/30 | 10/30 | 30/30 |
| 2 (30%) | $a_i \le 10^3$ | 31–60 | sai: $n$ tới 31.878, khoảng 23% số > 1000 (lớn nhất 973.077.883) | 30/30 | 0/30 | 30/30 |
| 3 (40%) | không thêm | 61–100 | $n$ tới $10^5$ | 30/40 | 0/40 | 40/40 |
Ngoài ra: đáp án lớn nhất trong bộ test chưa tới 1 triệu, nhưng nếu cả $10^5$ số đều bằng 1 thì mọi cặp đều có tổng $2$ – đáp án là $\frac{10^5 (10^5 - 1)}{2} \approx 5 \cdot 10^9$, vượt int. Biến đếm phải là long long.
Ý tưởngMỗi số chỉ có 31 "bạn ghép" tiềm năng
Đứng ở $a_j$, số $a_i$ ($i < j$) ghép được với nó phải có dạng $2^k - a_j$. Vì $2 \le a_i + a_j$ $\le 2 \cdot 10^9 < 2^{31}$ $= 2\,147\,483\,648$ nên $k$ chỉ chạy từ 1 tới 31.
cnt[v] = số lần $v$ đã xuất hiện. Tại mỗi $j$: với $k = 1..31$, cộng cnt[2^k - a[j]] vào đáp án; sau đó mới tăng cnt[a[j]].Một cặp chỉ có đúng một tổng nên không bao giờ bị đếm 2 lần ở 2 giá trị $k$ khác nhau. Thứ tự "cộng trước, tăng sau" đảm bảo mỗi cặp $i < j$ được đếm 1 lần và không có cặp $(j, j)$.
Em nhập dãy số rồi bấm Tiếp (mình chỉ hiện các lũy thừa $2^k$ có $2^k - a_j \ge 1$ và nhỏ hơn 2 lần số lớn nhất cho gọn):
Cách 1Vét cạn mọi cặp – Subtask 1
Thử mọi cặp $i < j$ và kiểm tra $x = a_i + a_j$ có phải lũy thừa của 2 không. Mẹo kiểm tra nhanh: lũy thừa của 2 trong hệ nhị phân chỉ có đúng một bit 1, nên $x \,\&\, (x - 1) = 0$ (phép trừ 1 lật bit 1 đó thành 0 và các bit 0 phía sau thành 1).
Kết quả chạy thật: bản C++ đúng 90/100 test (quá giờ ở test 91–100), test đúng chạy lâu nhất 0.90s; bản Python (chỉ chạy test 1–60) đúng 32/60 test (quá giờ ở test 31–54, 56–59), lâu nhất trên 1s. Ăn trọn subtask 1, và còn "lì" qua được cả các test $n \approx 4 \cdot 10^4$.
Cách 2Mảng đếm theo đúng subtask 2 (và cú lừa)
Nếu đúng như đề ghi $a_i \le 10^3$ thì tổng không quá 2000, chỉ cần thử $2^1..2^{11}$ và dùng mảng cnt[0..1000] thay cho map:
Kết quả chạy thật: bản C++ đúng 10/100 test (sai ở test 11–100), test đúng chạy lâu nhất 0.00s. Code này chỉ đúng khi mọi số $\le 1000$ – điều mà test thật không đảm bảo (xem bảng bộ test). Mình vẫn để ở đây để các bạn thấy: "ăn subtask" bằng code chuyên biệt có thể mất trắng nếu dữ liệu không như đề nói.
Cách 3map + 31 lũy thừa – Full điểm
(1LL << k)là $2^k$ kiểulong long– viết1 << 31kiểuintsẽ bị tràn thành số âm.if(y < 1) continue;: các số đều dương nên $y \le 0$ chắc chắn không có trong map, bỏ qua cho nhanh.- Dùng
cnt.findđể không vô tình thêm khoá rỗng vào map (31 lần mỗi số thì map sẽ phình rất to). - Bản Python đếm theo giá trị:
Countercho biết số lần xuất hiện $c_x$ của mỗi giá trị $x$; ghép $x$ với $y = 2^k - x$: nếu $y > x$ cộng $c_x \cdot c_y$, nếu $y = x$ cộng $\binom{c_x}{2}$ (tránh đếm 2 lần).
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.17s; bản Python đúng 100/100 test, lâu nhất 0.21s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất | Ghi chú |
|---|---|---|---|---|
| 1. Vét cạn $O(n^2)$ | C++ | 90/100 | > 1s | Quá thời gian test 91–100 (n = 10^5) |
| Python | 32/60 | > 1s | Chỉ chạy thử test 1–60; quá thời gian test 31–54, 56–59 | |
| 2. Mảng đếm ($a_i \le 1000$) | C++ | 10/100 | 0.01s | Chỉ đúng test 1–10 – test thật không khớp subtask 2 |
3. map + 31 lũy thừa | C++ | 100/100 | 0.17s | Full điểm |
| Python | 100/100 | 0.21s | Full điểm (Counter theo giá trị) |
Nhận xét
Đăng nhận xét