ผลรวมของเซตย่อยทั้งหมดของเซตที่เกิดจากจำนวนธรรมชาติ n ตัวแรก

ชุดคือชุดขององค์ประกอบข้อมูล เซตย่อยของเซตคือเซตที่สร้างโดยอิลิเมนต์หลังจากเซตพาเรนต์เท่านั้น ตัวอย่างเช่น B เป็นเซตย่อยของ a หากองค์ประกอบทั้งหมดของ B มีอยู่ใน A.

ในที่นี้เราต้องหาผลรวมของเซตย่อยทั้งหมดของเซตที่พบโดยจำนวนธรรมชาติ n ตัวแรก นี่หมายความว่าฉันต้องค้นหาชุดย่อยทั้งหมดที่สามารถเกิดขึ้นได้ แล้วเพิ่มเข้าไป มาดูตัวอย่างกัน

ไม่มี =3

ชุด ={1,2,3}

เซตย่อยที่เกิดขึ้น ={ {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3,} } }

ผลรวม =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 sim of the series is 2815