C++ Số mảng con có đúng m số lẻ

Cho mảng và m, đếm mảng con chứa đúng m số lẻ. Ví dụ:

Input: {6,3,5,8,9}, m=2 → Output: 5
Mảng con: {3,5}, {6,3,5}, {3,5,8}, {5,8,9}, {6,3,5,8}, {3,5,8,9}

Input: {1,6,3,2,5,4}, m=2 → Output: 6

Phương pháp 1: Vét cạn O(n²)

Sinh mọi mảng con, đếm số lẻ, nếu =m thì tăng kết quả.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a[]={1,6,3,2,5,4}, n=6, m=2, count=0;
    for (int i=0; i

Phương pháp 2: Hiệu quả O(n) với mảng tiền tố
prefix[i] = số mảng con bắt đầu từ đầu có i số lẻ. Duyệt mảng, cập nhật odd_count. Khi odd_count ≥ m, kết quả += prefix[odd_count - m].

Ví dụ
#include <bits/stdc++.h>
using namespace std;

int main() {
    int array[]={1,6,3,2,5,4}, n=6, m=2, count=0, odd=0;
    int prefix[n+1]={0};
    for (int i=0; i= m) count += prefix[odd-m];
    }
    cout << "Số mảng con: " << count;
    return 0;
}

Kết quả
Số mảng con: 6

Giải thích
prefix[odd] đếm số prefix có odd số lẻ. Khi odd ≥ m, các prefix có (odd-m) số lẻ tạo thành mảng con có đúng m số lẻ khi kết hợp với phần hiện tại.

Kết luận
Đã trình bày 2 cách: vét cạn O(n²) và tối ưu O(n) với mảng tiền tố đếm số lẻ. Hy vọng hữu ích.