Lista de probleme 3

Se consideră un şir format din M x N termeni a căror valoare poate fi 0 sau 1, cele Q poziţii în care se găsesc termenii egali cu 1 fiind P1, P2, …, PQ. Termenii şirului sunt memorați într-o matrice inițială cu M linii și N coloane, astfel încât șirul se obține dacă se parcurge matricea linie cu linie, în ordine, de sus în jos, și fiecare linie de la stânga la dreapta. Pentru un număr K dat, se obține o matrice nouă, cu M • K linii și N coloane, prin scrierea matricei inițiale de K ori, de sus în jos, astfel încât fiecare copie este plasată sub cea de la pasul anterior. Un grup-1 în matrice este format din una sau mai multe valori 1 și se consideră că două valori egale cu 1 fac parte din acelaşi grup-1 dacă se poate ajunge de la una la cealaltă parcurgând matricea pe un traseu format doar din elemente egale cu 1. Se cere numărul grupurilor-1 din matricea cu M •K linii şi N coloane formată.

În clasa lui Ionuț sunt N elevi numerotați cu numere naturale de la 1 la N așezați în ordinea din catalog. Fiecare elev i (1 ≤ i ≤ N ) are ceea ce se numește un coeficient de popularitate \(A_i\) , un număr natural nenul. Fiecare elev din clasă are un grup de simpatizanți. Grupul de simpatizanți ai elevului i, notat cu \(G_i\) este reprezentat de cea mai lungă secvență de elevi din șirul dat în catalog, care îl conține pe elevul i, astfel încât coeficientul de popularitate al fiecărui elev j din secvență, \(A_j\) , să fie divizor al lui \(A_i\) . Lungimea secvenței, deci numărul elevilor din grupul de simpatizanți ai lui i, se notează cu \(|G_𝑖|\). Evident, elevul i face parte din propriul său grup de simpatizanți. Dacă elevul i face parte din grupul de simpatizanți ai elevului j, atunci nu este neapărat necesar ca și j să facă parte din grupul de simpatizanți ai elevului i.

După ore, unii elevi își invită la cofetărie grupul de simpatizanți, pentru câte o înghețată. Pentru un grup de simpatizanți \(G_i\) , elevul i merge și îi cere vânzătoarei exact \(|G_i|\) înghețate, dar vânzătoarea are o fire năstrușnică și îi spune că este disponibil doar un anumit număr de arome k, mereu cel mult egal cu numărul de înghețate cerute (\(1 ≤ 𝑘 ≤ |G_𝑖|\)). Elevii, creativi, calculează numărul de moduri în care se poate cumpăra înghețată pentru grup, astfel încât să achiziționeze fiecare sortiment cel puțin o dată; pentru grupul \(G_i\) , acest număr se notează cu \(v_i(k)\).

1. Determinați numărul de ordine din catalog al elevului care are cel mai numeros grup de simpatizanți. Se garantează că există un singur astfel de elev.
2. Lui Ionuț îi place foarte mult să analizeze vânzările magazinelor de înghețată și vă lansează Q întrebări de tipul: (i, st, dr) (cu \(1 ≤ i ≤ N\) și \(1 ≤ st ≤ dr ≤ |G_i|\)); pentru fiecare determinați valoarea expresiei: \(v_i(st) + v_i(st + 1) + \cdots + v_i(dr)\); cum valoarea poate fi foarte mare, luați în considerare restul împărțirii ei la \(10^9 + 7\).

Se dă următorul algoritm misterios, care are ca date de intrare numerele naturale N și K, precum și un șir de N numere naturale A (A[1], A[2], …, A[N]), iar ca date de ieșire termenii șirului B (B[1], B[2], …, B[N]). De asemenea, algoritmul utilizează și un șir auxiliar T (T[0], T[1], …, T[N−1]).

1: 	x ← 0
2: 	y ← −1
3: 	pentru i ← 1, N execută
4:		cât timp x ≤ y și A[i] > T[y] execută
5:			y ← y−1
6:		sfârșit cât timp
7:	  	dacă x ≤ y și i − K ≥ 1 și T[x] = A[i−K] atunci
8:		  	x ← x + 1
9:		sfârșit dacă
10:		y ← y + 1
11:		T[y] ← A[i]
12:		B[i] ← y − x + 1
13:	sfârșit pentru

Dându-se N , K și cei N termeni ai unui șir B, să se determine termenii unui șir A, cu 1 ≤ A[i] ≤ N, pentru orice i de la 1 la N , care ar trebui citiți ca date de intrare în cadrul algoritmului misterios, astfel încât în urma executării acestuia să se obțină ca date de ieșire termenii șirului B dat. Dacă există mai multe soluții, oricare dintre acestea este considerată validă.