Tích tất cả các dãy con kích thước K trừ phần tử min và max trong C++

Cho mảng arr[n] chứa n số nguyên và số nguyên k để xác định kích thước; nhiệm vụ là in tích của tất cả các dãy con kích thước k trừ đi phần tử nhỏ nhất và lớn nhất.

Giả sử ta có tập 4 phần tử {1, 2, 3, 4} và k = 2, các tập con sẽ là – {1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 3}, {2, 4}

Loại bỏ phần tử lớn nhất 4 và nhỏ nhất 1, các phần tử còn lại sẽ là –

2, 3, 3, 3, 2, tích của chúng là –

2 * 3 * 3 * 3 * 2 = 108

Tương tự ta phải giải bài toán này.

Ví dụ

Đầu vào: arr[] = {3, 4, 1, 7}, k = 3 
Đầu ra: 144 
Giải thích: các tập con sẽ là {3, 4, 1}, {4, 1, 7}, {3, 1, 7}, {3, 4, 7}
Loại bỏ giá trị max 7 và min 1 ta được: {3, 4}, {4}, {3}, {3, 4}, nhân cho: 3 * 4 * 4 * 3 = 144

Đầu vào: arr[] = {1, 2, 3, 4}, k = 3 
Đầu ra: 36

Cách tiếp cận để giải bài toán trên –

Có nhiều cách để đạt được giải pháp. Có cách tiếp cận là sinh tất cả các dãy con có thể một bởi một, và nhân tất cả các phần tử trừ max và min của tập. Cách này dễ thực hiện nhưng độ phức tạp rất cao và không hiệu quả.

Có cách tiếp cận hiệu quả hơn: trước tiên sắp xếp mảng, bỏ qua việc xét các dãy con hay không.

Sau đó đếm số lần xuất hiện của từng phần tử một by one.

Một số có thể xuất hiện C(k-1, n-1) dãy con trong đó C(k-1, i) lần xuất hiện như phần tử lớn nhất, C(k-1, n-i-1) lần xuất hiện như phần tử nhỏ nhất của dãy con đó.

Do đó, phần tử thứ i sẽ xuất hiện –

C(k-1, n-1) - C(k-1, i) - C(k-1, n-i-1) lần.

Bây giờ, trước tiên ta giải x cho mỗi phần tử trong arr[i], vì câu trả lời có thể rất lớn nên ta dùng định lý Fermat nhỏ.

Lưu ý – Vì kết quả có thể rất lớn nên in kết quả theo modulo 10^9+7.

Thuật toán

Bắt đầu
Bước 1 -> Khai báo hàm tính tổ hợp
    void pairs(int a, int b)
    Khai báo int i, j
    Vòng lặp Với i = 0 đến i <= a và i++
        Vòng lặp Với j = 0 đến j <= min(i, b) và j++
            NẾU (j == 0 || j == i)
                Gán c[i][j] = 1
            Kết thúc
            NGƯỢC LẠI
                Gán c[i][j] = (c[i-1][j-1] % val + c[i-1][j] % val) % val
            Kết thúc
        Kết thúc
    Kết thúc

Bước 2 -> Khai báo hàm lũy thừa
    LL power(LL x, unsigned LL y)
    Khai báo unsigned LL temp = 1
    Gán x = x % val
    Vòng lặp Khi (y > 0)
        NẾU (y & 1)
            Gán temp = (temp * x) % val
        Kết thúc
        Gán y = y >> 1
        Gán x = (x * x) % val
    Kết thúc
    trả về temp % val

Bước 3 -> Khai báo hàm tính tích tất cả dãy con
    unsigned LL product(LL arr[], int size, int k)
    Khai báo và gán unsigned LL temp = 1
    Gọi hàm sắp xếp mảng sort(arr, arr + size)
    Khai báo và gán LL pow = c[size-1][k-1]
    Vòng lặp Với i = 0 đến i < size và i++
        Khai báo và gán LL pow_l = c[i][k-1]
        Khai báo và gán LL pow_f = c[size-i-1][k-1]
        Khai báo và gán LL pow_e = ((pow % val) - (pow_l + pow_f) % val + val) % val
        Khai báo và gán unsigned LL mul = power(arr[i], pow_e) % val
        Gán temp = ((temp % val) * (mul % val)) % val
    Kết thúc
    trả về temp % val

Bước 4 -> Trong main()
    Gọi pairs(100, 100)
    Khai báo và gán LL arr[] = {3, 4, 1, 7}
    Tính size = sizeof(arr) / sizeof arr[0]
    Khai báo và gán int k = 3
    Khai báo và gán unsigned LL temp = product(arr, size, k)
    In temp
Kết thúc

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
#define val 1000000007
#define LL long long
#define max 101
LL c[max - 1][max - 1];

LL power(LL x, unsigned LL y) {
    unsigned LL temp = 1;
    x = x % val;
    while (y > 0) {
        if (y & 1) {
            temp = (temp * x) % val;
        }
        y = y >> 1;
        x = (x * x) % val;
    }
    return temp % val;
}

void pairs(int a, int b) {
    int i, j;
    for (i = 0; i <= a; i++) {
        for (j = 0; j <= min(i, b); j++) {
            if (j == 0 || j == i)
                c[i][j] = 1;
            else
                c[i][j] = (c[i - 1][j - 1] % val + c[i - 1][j] % val) % val;
        }
    }
}

// Hàm tính tích tất cả dãy con
unsigned LL product(LL arr[], int size, int k) {
    unsigned LL temp = 1;
    // sắp xếp mảng
    sort(arr, arr + size);
    LL pow = c[size - 1][k - 1];
    for (int i = 0; i < size; i++) {
        LL pow_l = c[i][k - 1];
        LL pow_f = c[size - i - 1][k - 1];
        LL pow_e = ((pow % val) - (pow_l + pow_f) % val + val) % val;
        unsigned LL mul = power(arr[i], pow_e) % val;
        temp = ((temp % val) * (mul % val)) % val;
    }
    return temp % val;
}

int main() {
    // tổng tất cả các cặp
    pairs(100, 100);
    LL arr[] = {3, 4, 1, 7};
    int size = sizeof(arr) / sizeof arr[0];
    int k = 3;
    unsigned LL temp = product(arr, size, k);
    cout << "tích tất cả dãy con kích thước k trừ min và max là: " << temp << endl;
    return 0;
}

Đầu ra

tích tất cả dãy con kích thước k trừ phần tử nhỏ nhất và lớn nhất là: 144