214 Subsiruri

[•PlayLikeNeverB4]

Asa ti se cere in enunt. La alte probleme poate fi alt numar.

[•VisuianMihai]

am pus modulo si iau 80 pct cu WA pe testele 8 si 10... au ceva special???un plus la karma nu costa nimic :D

[•pauldb]

Nu exista nici o logica pentru care a fost ales exact numarul 9901. Dar cerand rezultatul modulo un numar x, nu trebuie sa implementezi numere mari plecand de la urmatoarele observatii:

(a+b) % x = ((a % x) + (b % x)) % x
(a*b) % x = ((a % x) * (b % x)) % x.

Pe scurt, aceste observatii spun ca e ok sa pastrezi la fiecare pas doar restul modulo x al numarului cautat.

[•SebiSebi]

Ambele cerinte se pot rezolva in O(n * log N) folosind normalizare si apoi un arbore de intervale, dar nu este necesara complexitatea asta aici. Se poate lua 100 cu O(n^2). 

[•SebiSebi]

Nu, normalizarea a n numere cuprinse intre 1 si X inseamna sa atribui fiecarui numar o valoare cuprinsa intre 1 si N (de obicei) astfel incat relatiile de ordine sa se pastreze, adica daca numarul i > numarul j inainte de normalizare expresia trebuie sa fie adevarata si dupa. Ex: trebuie sa normalizam numerele  10,5,20,15,13,18 , vom avea : 2,1,6,4,3,5.
Normalizarea se poate face usor sortand numerele si pastrand pozitiile lor in sirul initial.