Lista de probleme 3

Fie a și b două numere naturale 0 < a ≤ b. Să se determine numărul de fracții \( \frac{x}{y} \) diferite, ce se pot forma utilizând numere naturale nenule, având proprietățile: \( \frac{a}{b} \leq \frac{x}{y} \leq \frac{b}{a} \) și 2 ≤ x + y ≤ a + b.

Se dă un șir V cu N valori naturale nenule, memorate pe poziții consecutive începând cu poziția 1. Notăm cu S următoarea secvență de cod aplicată asupra sa:

(C/C++)
maxim = 0;
rep = 0;
for(i = 1; i <= N; i++)
	if(V[i] > maxim)
		maxim = V[i];
	else
		if(V[i] == maxim)
			rep++;

Considerăm operația de eliminare din V a elementului de pe o anumită poziție dată P. În urma operației de eliminare elementele de pe pozițiile P + 1, P + 2, ..., N ajung pe o poziție cu 1 mai mică iar N scade cu 1.

Dându-se mai multe operații de eliminare(independente una de alta, adică fiecare se aplică asupra șirului inițial, nu după operația anterioară), să se determine valoarea variabilei rep dacă am aplica secvența S asupra șirului obținut după fiecare operație de eliminare.

Fie un șir a de N numere întregi. Trebuie construit un nou șir b (tot cu N elemente) astfel:

• dacă \( {a}_{i}>0 \), atunci \( {b}_{i}={a}_{i} \)
• dacă \( {a}_{i}=0 \), atunci \( {b}_{i} \) poate avea orice valoare strict pozitivă
• dacă \( {a}_{i}<0 \), atunci \( {b}_{i} \) poate avea orice valoare strict pozitivă cu excepția lui \( -{a}_{i} \)

Se garantează că \( {a}_{1} \) și \( {a}_{N} \)au valori strict pozitive și între oricare două valori strict pozitive se va afla cel mult una strict negativă.

Știindu-se șirul a, să se calculeze numărul de moduri de a forma șirul b astfel încât acesta să fie crescător (nu neapărat strict). Deoarece acest număr poate fi foarte mare, se va afișa doar restul împărțirii la 1.000.000 007.