Tổng tất cả các tập con của tập n số tự nhiên đầu tiên

Tập con là tập chỉ chứa phần tử của tập cha. Tìm tổng tất cả tập con của tập n số tự nhiên đầu tiên. Ví dụ N=3: tập {1,2,3}, các tập con: {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}. Tổng = 24.

Sắp xếp lại: 1 xuất hiện 4 lần, 2 xuất hiện 4 lần, 3 xuất hiện 4 lần. Tổng = 4*(1+2+3) = 24.

Công thức chung: 2ⁿ*(n² + n + 2) – 1.

Ví dụ

#include <stdio.h>
#define mod (int)(1e9 + 7)

int power(int x, int y) {
    int res = 1;
    x = x % mod;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % mod;
        y = y >> 1;
        x = (x * x) % mod;
    }
    return res;
}

int main() {
    int n = 45;
    n--;
    int ans = n * n;
    if (ans >= mod)
        ans %= mod;
    ans += n + 2;
    if (ans >= mod)
        ans %= mod;
    ans = (power(2, n) % mod * ans % mod) % mod;
    ans = (ans - 1 + mod) % mod;
    printf("The sum of the series is %d \n", ans);
    return 0;
}

Kết quả

The sim of the series is 2815