Subsir100

Exista o bijectie intre multimea subsirurilor "interesante" din sirul dat si multimea subsirurilor "interesante" din sirul obtinut prin ordonarea sirului dat (Tema demonstratia).
Fie A[1...N] sirul obtinut prin ordonarea sirului dat, iar X[i] numarul de subsiruri "interesante" din sirul A[i...N] , oricare ar fi i un numar natural nenul cu proprietatea i ≤ N.
Evident X[N] = 1 si X[i] = X[i+1] + X[j] + 1, unde j este cel mai mic numar natural nenul ( i < j ≤ N ) cu proprietatea ca A[j] != A[i]. In cazul in care nu exista un astfel de j, adunam 0 in loc de X[j]. Relatia de recurenta se explica astfel:
Numarul subsirurilor "interesante" din A[i...N] este egal cu numarul subsirurilor "interesante" din A[i...N] care nu il contin pe A[i], plus numarul subsirurilor "interesante din" A[i...N] care il contin pe A[i]. Iar numarul subsirurilor "interesante" din A[i...N] care nu il contin pe A[i] este egal cu numarul subsirurilor "interesante" din A[i+1...N] ( A[i+1...N] nu il contine pe A[i], iar aici ma refer la termenul A[i] si nu la valoarea lui). Pentru a obtine toate subsirurile "interesante" din A[i...N] care il contin pe A[i] trebuie sa eliminam din sirul A[i...N] toti termenii care au valoarea egala cu valoarea lui A[i] ( Intr-un subsir "interesant" toate valorile sunt distincte ) si sa il adaugam pe A[i] la inceputul fiecarui subsir "interesant" din sirul ramas. La acestea se adauga sirul care contine un singur termen si anume pe A[i]. Raspunsul cautat va fi in X[1].