Editorial for Bedao Mini Contest 07 - MARKET
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Nhận xét #1: Giá sử dãy ~s[1...m]~ có trung bình cộng bằng ~x~ thì: ~s[1]+...+s[m] = x \times m~
~\leftrightarrow~ ~s[1]+...+s[m] - x*m = 0~
~\leftrightarrow~ ~(s[1]-x) + …. + (s[m]-x) = 0~
Vì vậy bài toán quay về đếm số dãy con có tổng bằng ~0~ trong dãy sau: ~a[1]-k, \dots, a[n]-k~
Subtask 1:
Vì ~n~ khá bé, ta có thể quay lui để sinh mọi dãy con rồi kiểm tra xem bao nhiêu dãy con trong đó có tổng bằng ~0~.
Độ phức tạp: ~O(2^n)~
Subtask 2:
Chia dãy làm ~2~ nửa bằng nhau (mỗi nửa có kích thước bé hơn hoặc bằng ~18~), ~\frac{n}{2}~ phần tử đầu làm nửa bên trái, ~\frac{n}{2}~ phần tử cuối làm nửa bên phải.
~\rightarrow~ Vậy ~1~ dãy con bất kỳ sẽ rơi vào 3 trường hợp sau:
- TH1: Nằm hoàn toàn trong nửa bên trái
- TH2: Nằm hoàn toàn trong nửa bên phải
- TH3: Có cả phần tử nằm ở nửa bên trái và bên phải
~\rightarrow~ Trường hợp (1) và (2) ta có thể dễ dàng đếm số dãy con có tổng bằng ~0~ tương tự như subtask 1, trường hợp 3 chúng ta sẽ xử lý như sau:
- Gọi tổng phần tử của các dãy con nằm nửa bên trái là ~s_1~, và tương tự nửa bên phải là ~s_2~. Dễ thấy nếu các dãy con có tổng bằng ~0~ thì ~s_1+s_2 = 0~ hay ~s2 = -s1~.
- Tạo ~2~ map ~cnt_1~, ~cnt_2~ tương ứng với mỗi nửa. ~cnt_1(s_1)~ là số dãy con có tổng bằng ~s_1~ trong nửa bên trái, tương tự với ~cnt_2(s_2)~ và nửa bên phải.
- Đáp án là tổng các ~\sum cnt_1(s_1) \times cnt2(-s_1)~ với mọi giá trị ~s_1~ tồn tại.
Độ phức tạp: ~O(2^{\frac{n}{2}} \times \frac{n}{2})~
Comments