# PBinfo #4579 – Descompunere prin reuniune – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Se consideră o mulţime A cu n elemente (distincte).
Determinaţi numărul de posibilităţi de a scrie pe A ca reuniune de m mulţimi. Două moduri de scriere B1 U B2 U ... U Bm şi C1 U C2 U ... U Cm diferă dacă există cel puţin un indice i din mulțimea {1,2 … m} astfel încât mulţimile Bi şi Ci diferă prin cel puţin un element.

Date de intrare
Fişierul de intrare descompunere_prin_reuniune.in conţine pe prima linie doua numere naturale separate printr-un spaţiu n m, cu semnificaţia din enunţ.

Date de ieșire
Fişierul de iesire descompunere_prin_reuniune.out va conţine o singură linie pe care va fi scris numărul reprezentând valoarea cerută modulo 2011.

Restricții și precizări

1 ≤ n, m ≤ 1000000000
Pentru 20% din punctaj 1 <= n, m <= 8

Exemplu:
descompunere_prin_reuniune.in

2 2
descompunere_prin_reuniune.out

9
Explicație
Cele 9 posibilităţi de descompunere a mulţimii {1,2} în doua mulţimi conform enunţului sunt:
{1}U{1,2}, {1}U{2}, {2}U{1,2}, {2}U{1}, {1,2}U{1}, {1,2}U{2}, {1,2}U{1,2}, {1,2}U∅, ∅U{1,2}

## Cod sursă C++

```cpp
#include<stdio.h>
#define MOD 2011
int putere(int a, int b) {
	int p, p2;
	p = 1;
	p2 = a%MOD;
	while (b) {
		if (b&1) {
			p = (p*p2)%MOD;
		}
		b>>=1;
		p2 = (p2*p2)%MOD;
	}
	return p;
}
int n,m,k;
int main(){
	FILE *f = fopen("descompunere_prin_reuniune.in","r");
    FILE *g = fopen("descompunere_prin_reuniune.out","w");
	fscanf(f,"%d %d",&n, &m);
	fclose(f);
	k = putere(2,m);
	k--;
	if (k<0)
		k+=MOD;
	k = putere(k,n);
	fprintf(g,"%d",k);
	fclose(g);
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4579)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4579/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4579/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)