Hướng dẫn giải của Hoàng Tử Lai

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Hướng tiếp cận

Với $N \leq 36$ , duyệt tất cả $2^{36} \approx 6.9 \times 10^{10}$ tập con là quá chậm. Ta sử dụng kỹ thuật Meet-in-the-Middle: chia $N$ nguyên liệu thành hai nửa, duyệt $2^{N / 2}$ tập con mỗi nửa, rồi kết hợp kết quả bằng bảng băm.

Nhận xét quan trọng

Chia $N$ nguyên liệu thành nửa trái ( $N / 2$ ) và nửa phải ( $N - N / 2$ ). Mỗi nửa có tối đa $2^{18} = 262144$ tập con — hoàn toàn khả thi.
Với mỗi tập con của nửa trái, ta tính cặp $(s_{a}, s_{b})$ là tổng độ chua và tổng độ đắng. Lưu vào bảng băm: $(s_{a}, s_{b}) \to$ số lượng.
Với mỗi tập con của nửa phải có tổng $(s_{a}^{'}, s_{b}^{'})$ , ta cần tìm trong nửa trái các tập con có tổng $(A - s_{a}^{'}, B - s_{b}^{'})$ .
Cần dùng cả hai tính chất $(a, b)$ làm khóa. Nếu chỉ dùng một tính chất sẽ đếm thừa.

Thuật toán

Chia đôi: Nửa trái gồm nguyên liệu $0, 1, \dots, N / 2 - 1$ . Nửa phải gồm nguyên liệu $N / 2, \dots, N - 1$ .
Duyệt nửa trái: Với mỗi bitmask $0 \leq m a s k < 2^{N / 2}$ :
- Tính $(s_{a}, s_{b})$ = tổng $(a_{i}, b_{i})$ của các nguyên liệu trong mask
- Thêm vào bảng băm: map[(s_a, s_b)]++
Duyệt nửa phải và kết hợp: Với mỗi bitmask $0 \leq m a s k < 2^{N - N / 2}$ :
- Tính $(s_{a}^{'}, s_{b}^{'})$ = tổng của các nguyên liệu trong mask
- Tra bảng băm: ans += map[(A - s'_a, B - s'_b)]
Kết quả: In ans.

Độ phức tạp

Thời gian: $O (2^{N / 2} \cdot N)$ — duyệt $2^{N / 2}$ tập con mỗi nửa, mỗi tập con tốn $O (N / 2)$ để tính tổng. Với $N = 36$ : $2 \times 2^{18} \times 18 \approx 10^{7}$ .
Bộ nhớ: $O (2^{N / 2})$ — lưu bảng băm cho nửa trái.

Bình luận

Không có bình luận tại thời điểm này.