Cho mảng arr[] kích thước N. Tính tổng của tích các phần tử của mọi tập con (subset) không rỗng.
Ví dụ
arr = {4, 5, 6}
Tập con: {4},{5},{6},{4,5},{5,6},{4,6},{4,5,6}
Tích: 4, 5, 6, 20, 30, 24, 120
Tổng = 209
Cách 1: Sinh tất cả tập con O(N·2ᴺ)
Duyệt mask từ 1 đến 2ᴺ-1, tính tích các phần tử được chọn.
Cách 2: Công thức toán học O(N)
Xét biểu thức: (1+a₁)(1+a₂)...(1+aₙ).
Khai triển ra sẽ có tất cả các tích của tập con (kể cả tập rỗng = 1).
Vậy: Tổng = (1+a₁)(1+a₂)...(1+aₙ) - 1.
Chương trình C++
#include <iostream>
using namespace std;
long long sumOfSubsetProducts(int arr[], int n) {
long long prod = 1;
for (int i = 0; i < n; i++)
prod *= (arr[i] + 1LL);
return prod - 1;
}
int main() {
int arr[] = {5, 6, 8, 9};
int n = 4;
cout << "Tong tich tat ca tap con = " << sumOfSubsetProducts(arr, n); // 3779
return 0;
}Kết quả
Tong tich tat ca tap con = 3779
Lưu ý
- Kết quả tăng rất nhanh, dễ tràn
long long. Cần big integer cho N lớn. - Công thức này giả sử các phần tử không âm. Với số âm vẫn đúng đại số.