ผลรวมของทุก Subset ของเซตที่ประกอบด้วย n จำนวนธรรมชาติแรก

เซต (Set) คือ ชุดข้อมูล Subset คือ เซตที่สมาชิกทุกตัวอยู่ในเซตแม่ เช่น B เป็น Subset ของ A ถ้าสมาชิก B ทั้งหมดอยู่ใน A

โจทย์: หาผลรวมของทุก Subset ของเซตที่ประกอบด้วย n จำนวนธรรมชาติแรก หา Subset ทั้งหมดที่เป็นไปได้ แล้วบวกสมาชิกทั้งหมด ตัวอย่าง N=3:

Set = {1,2,3}

Subsets = { {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }

Sum = 1+1+2+1+3+2+2+3+3+1+2+3 = 24

เรียงใหม่: 1+1+1+1+2+2+2+2+3+3+3 = 4(1+2+3) = 24

มีสูตรทั่วไป: 2^n * (n^2 + n + 2) - 1

ตัวอย่าง

#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;
}

ผลลัพธ์

The sum of the series is 2815