h1. 'Subsir100':problema/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 &le 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 &le 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:

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$ &le $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$ &le $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]$.