Đếm số tập con có trung vị cũng nằm trong tập con đó trong C++

Cho một mảng arr[] chứa các số dương. Mục tiêu là tìm các tập con của các phần tử của arr[] sao cho trung vị của các giá trị của tập con cũng có mặt trong tập con đó.

Ví dụ

Đầu vào

arr[] = { 1,2,3 }

Đầu ra

Số tập con có trung vị cũng nằm trong tập con là: 4

Giải thích

Các tập có trung vị trong tập đó là: [1], trung vị là 1; [2], trung vị là 2; [3], trung vị là 3; [1,2,3], trung vị là 2

Đầu vào

arr[] = { 4,6,5 }

Đầu ra

Số tập con có trung vị cũng nằm trong tập con là: 4

Giải thích

Các tập có trung vị trong tập đó là: [4], [6], [5], [4,6,5]

Phương pháp sử dụng

Trong phương pháp này, chúng ta sẽ kiểm tra cho số phần tử chẵn và lẻ. Sau đó có thể tìm trung vị dựa trên thực tế rằng đối với số lượng phần tử lẻ, trung vị có mặt trong cùng tập con như phần tử giữa. Vì vậy chúng ta sẽ thêm 2^n - 1 vào biến đếm. Đối với tập con độ dài chẵn, chúng ta sẽ kiểm tra xem có hai phần tử giống nhau không, vì vậy đếm cho các tập con độ dài chẵn có hai phần tử giữa.

Nhận mảng arr[] các số dương.
Hàm median_subset(arr, size) nhận arr và trả về số lượng tập con có trung vị cũng nằm trong tập con đó.
Hàm check(int temp) nhận một số nguyên và trả về giai thừa của số đó bằng vòng lặp for từ i=2 đến i<=temp.
Tính count = count * i, và trả về nó ở cuối vòng lặp làm giai thừa.
Hàm com(int n, int r) nhận n và r và trả về giá trị tổ hợp nCr. Bên trong lấy temp = check(r) * check(n - r) và temp_2 = check(n) / temp. Trả về temp_2 là giá trị tính được.
Hàm power(int n, int r) nhận n và r và trả về giá trị n^r.
Nếu r là 0 thì đáp án sẽ là 1 nên trả về 1.
Lấy total = power(n, r / 2) (n^(r/2)).
Cập nhật total với total^2 % mod. Trong đó mod=1000000007.
Nếu r là chẵn thì trả về temp là (total * n) % mod, ngược lại trả về total.
Bên trong hàm median_subset(), lấy count = power(2, size - 1) là số tập con độ dài lẻ.
Sắp xếp mảng arr[] bằng sort(arr, arr + size).
Sử dụng vòng lặp while, chúng ta sẽ kiểm tra cho mỗi phần tử phần tử giữa bên trái cho đến khi chúng bằng nhau.
Lấy temp_2 = size - 1 - temp là số phần tử bên phải của phần tử giữa bên phải.
Lấy temp_3 = i là số phần tử bên trái của phần tử giữa bên trái.
Thêm các tập con độ dài chẵn được chọn vào biến đếm: count = (count + com(temp_3 + temp_2, temp_3)) % mod.
Cuối cùng của vòng lặp while, chúng ta sẽ có biến đếm.
Trả về biến đếm làm kết quả.

Ví dụ mã

#include <algorithm> 
#include <iostream> 
using namespace std; 

#define mod 1000000007

int check(int temp) {
    int count = 1;
    for (int i = 2; i <= temp; i++) {
        count = count * i;
    }
    return count;
}

int com(int n, int r) {
    int temp = check(r) * check(n - r);
    int temp_2 = check(n) / temp;
    return temp_2;
}

int power(int n, int r) {
    if (r == 0) {
        return 1;
    }
    int total = power(n, r / 2);
    total = (total * total) % mod;
    if (r % 2) {
        int temp = (total * n) % mod;
        return temp;
    } else {
        return total;
    }
}

int median_subset(int* arr, int size) {
    int count = power(2, size - 1);
    sort(arr, arr + size);
    
    for (int i = 0; i < size; ++i) {
        int temp = i + 1;
        while (temp < size && arr[temp] == arr[i]) {
            int temp_2 = size - 1 - temp;
            int temp_3 = i;
            count = (count + com(temp_3 + temp_2, temp_3)) % mod;
            temp++;
        }
    }
    
    return count;
}

int main() {
    int arr[] = { 4, 5, 4, 6 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Số tập con có trung vị cũng nằm trong tập con là: " << median_subset(arr, size);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số tập con có trung vị cũng nằm trong tập con là: 9