subpermutari

Subpermutari

== include(page="template/taskheader" task_id="subpermutari") ==

Fie $P$ o permutare de lungime $N$. Spunem ca o alta permutare $R$ (de lungime $M ≤ N$) este o subpermutare a lui $P$ pe pozitia $i$ ( $i ≤ N - M + 1$ ) daca oricare ar fi $j$ si $k$ intre $1$ si $M$ cu $j < k$ si $R[j] < R[k]$ atunci $P[j + i - 1] < P[k + i - 1]$.

Fie $P$ o permutare de lungime $N$. Spunem ca o alta permutare $R$ (de lungime $M ≤ N$) este o subpermutare a lui $P$ pe pozitia $i$ ( $i ≤ N - M + 1$ ) daca oricare ar fi $j$ si $k$ intre $1$ si $M$ cu $j ≠ k$ si $R[j] < R[k]$ atunci $P[j + i - 1] < P[k + i - 1]$.

De exemplu permutarea $1 2$ este o subpermutare a lui $1 3 2 4$ pe pozitiile $1$ si $3$.

Voua vi se da o permutare $P$ si vi se cere pentru fiecare permutare $R$ care apare cel putin o data ca subpermutare in $P$ de cate ori apare. Pentru simplititate vi se cere suma patratelor acestor numere.

Voua vi se da o permutare $P$ si vi se cere pentru fiecare permutare $R$ care apare cel putin o data ca subpermutare in $P$ să-i contorizaţi frecvenţa apariţiilor în $P$. Pentru simplititate vi se cere suma patratelor acestor numere.

h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $subpermutari.out$ trebuie sa se aflu un singur numar, cel cerut in cerinta problemei.

În fişierul de ieşire $subpermutari.out$ trebuie sa se afle un singur număr, cel cerut in cerinta problemei.

h2. Restricţii