Numărarea submulțimilor — 2 la puterea n

De ce sunt 2^n submulțimi

O submulțime se obține alegând, pentru fiecare element, dacă îl iei sau nu. Gândește-te la cele n elemente la rând. Pentru primul element ai 2 alegeri (în submulțime sau afară). Pentru al doilea, tot 2 alegeri, independent de primul. Și așa mai departe, până la al n-lea.

Cum alegerile sunt independente, înmulțești numărul de variante:

2 · 2 · 2 · ... · 2   (de n ori)  =  2^n

Fiecare combinație de decizii „în/afară” dă o submulțime distinctă, și fiecare submulțime corespunde unei singure combinații de decizii. Deci numărul total este fix 2^n. Acest total include două cazuri speciale care se uită ușor:

• mulțimea vidă — ai răspuns „afară” la toate elementele;
• mulțimea totală — ai răspuns „în” la toate elementele.

Exemplu pas cu pas: n = 3

Fie mulțimea {a, b, c}. Avem 2^3 = 8 submulțimi. Le enumerăm pe toate, ordonate după câte elemente conțin:

• {} — mulțimea vidă (0 elemente)
• {a}, {b}, {c} — submulțimile cu 1 element
• {a, b}, {a, c}, {b, c} — submulțimile cu 2 elemente
• {a, b, c} — mulțimea totală (3 elemente)

Numără: 1 + 3 + 3 + 1 = 8. Se potrivește cu 2^3. Observă și că numărul de submulțimi de o anumită mărime k este o combinare C(n, k): aici C(3,0) = 1, C(3,1) = 3, C(3,2) = 3, C(3,3) = 1. Dacă vrei doar submulțimile de o mărime fixă, folosești combinări — vezi lecția de combinări din acest capitol. Suma tuturor combinărilor dă, firește, tot 2^n.

Implementare C++

Calculul direct cu long long merge doar pentru n mic. Apoi numerele explodează, de aceea convenția capitolului este să lucrezi modulo un prim, de regulă MOD = 1000000007.

#include <iostream>
using namespace std;

const long long MOD = 1000000007;

// 2^n exact, fara modulo - corect doar pentru n mic (n <= 62)
long long submultimiExact(int n) {
    long long total = 1;        // pornim de la 2^0 = 1
    for (int i = 0; i < n; i++) {
        total = total * 2;      // dublam de n ori
    }
    return total;
}

// 2^n modulo MOD - sigur pentru orice n, fara overflow
long long submultimiModulo(int n) {
    long long total = 1;
    for (int i = 0; i < n; i++) {
        total = (total * 2) % MOD;   // reducem la fiecare pas
    }
    return total;
}

int main() {
    int n = 3;
    cout << submultimiExact(n) << "\n";   // 8
    cout << submultimiModulo(n) << "\n";  // 8 (n mic, nu se schimba)

    int m = 100;
    // submultimiExact(100) ar da overflow; folosim varianta modulo
    cout << submultimiModulo(m) << "\n";  // 2^100 mod 1000000007
    return 0;
}

Reducerea cu % MOD la fiecare înmulțire ține valoarea mereu sub MOD, deci produsul total * 2 nu poate depăși long long. Atât timp cât te interesează restul modulo MOD, rezultatul rămâne corect.

Complexitate

Recapitulare

• O mulțime cu n elemente are 2^n submulțimi: fiecare element intră sau nu, produs de n factori de 2; totalul include mulțimea vidă și mulțimea totală.
• Submulțimile de mărime exact k se numără cu combinări C(n, k), iar suma tuturor combinărilor redă 2^n.
• 2^n crește exponențial și depășește repede long long, deci la concurs calculezi modulo un prim (MOD = 1000000007), reducând la fiecare înmulțire.