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

Code mẫu

#include <bits/stdc++.h>

using namespace std;

int n;
long long a[50], x;
map<long long, int> mp;
long long res = 0;

void gen(int p, int en, bool type, long long s = 0) {
    if (p == en) {
        if (type) {
            ++ mp[s];
        } else {
            res += mp[-s];
        }
        return;
    }
    gen(p+1, en, type, s);
    gen(p+1, en, type, s+a[p]);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> x;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
        a[i] -= x;
    }
    int mid = (1 + n) >> 1;
    gen(1, mid + 1, 1);
    gen(mid + 1, n + 1, 0);
    cout << res - 1;
    return 0;
}