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})~