Hoàng Tử Lai

Hướng tiếp cận

Với $N\le 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

1. 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.

2. 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.

3. Với mỗi tập con của nửa phải có tổng $(s_a^{\prime },s_b^{\prime })$, ta cần tìm trong nửa trái các tập con có tổng $(A-s_a^{\prime },B-s_b^{\prime })$.

4. 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

1. 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$.

2. Duyệt nửa trái: Với mỗi bitmask $0\le mask<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)]++

3. Duyệt nửa phải và kết hợp: Với mỗi bitmask $0\le mask<2^{N-N/2}$:

   • Tính $(s_a^{\prime },s_b^{\prime })$ = 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)]

4. Kết quả: In ans.

Độ phức tạp

• Thời gian: $O(2^{N/2}·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.