# PBinfo #4487 – moser – Rezolvare C++

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

## Enunț

Cerința
Se consideră un cerc. Pe cerc se desemnează N puncte oarecare. Dacă tragem linii între toate perechile de puncte, care este numărul maxim de bucăți în care poate fi descompus cercul? Să se răspundă la Q astfel de scenarii.

Date de intrare
Programul citește de la tastatură numărul Q și pe următoarele Q linii va citi câte un numar N, reprezentând numărul de puncte din scenariul respectiv.

Date de ieșire
Pe următoarele Q linii, programul va afișa răspunsurile pentru fiecare dintre scenarii, modulo 1.000.000.007.

Restricții și precizări

Se recomandă folosirea fastio
1 ≤ Q ≤ 100.000
1 ≤ N ≤ 1.000.000.000
pentru 25% din teste: Q ≤ 5.000, N ≤ 5.000
pentru alte 50% din teste: Q ≤ 100.000, N ≤ 1.000.000
pentru restul testelor, nicio restricție suplimentară
deoarece răspunsul poate fi foarte mare, va fi afișat modulo 1.000.000.007.

Exemplu:
Intrare

6
1
2
3
4
5
6
Ieșire

1
2
4
8
16
31
Explicație
Pentru al patrulea scenariu, una dintre posibilele aranjări optime ale celor 4 puncte este următoarea:

## Cod sursă C++

```cpp
// Problema moser - solutie in O(Q+max(N)^2) timp si O(N^2) spatiu - 25 puncte
#include <iostream>
// Valoarea noastra MOD.
const int MOD = 1000000007;
// comb[i][j] = C(i,j)
int comb[5001][5001];
// Precalculam toate combinarile folosind formula:
// C(n,k) = C(n-1,k) + C(n-1,k-1)
void preprocess() {
	comb[0][0] = 1;
	for (int i = 1; i < 5001; i++) {
		comb[i][0] = 1;
		for (int j = 1; j <= i; j++) {
			comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
			if (comb[i][j]>=MOD) {
				comb[i][j] -= MOD;
			}
		}
	}
}
// In sol, evitam folosirea operatiilor modulo pentru a optimiza mai departe programul.
int sol(int x) {
	int ret = 1 + comb[x][2] + comb[x][4];
	while (ret>=MOD) {
		ret -= MOD;
	}
	return ret;
}
int main() {
	// Fastio
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	// Precalculam triunghiul lui Pascal
	preprocess();
	// Citim si raspundem la query-uri.
	int q;
	std::cin >> q;
	while (q--) {
		int x;
		std::cin >> x;
		std::cout << sol(x) << "\n";
	}
}
```

## Resurse

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