h2(#pkinv). 'Pkinv':problema/pkinv

Problema este asemanatoare cu problema 'Perm6':/problema/perm6 si ne duce cu gandul, in prima faza, la o dinamica de forma $c[i][j]$ = numarul de permutari de $i$ elemente cu $j$ inversiuni. Recurenta iese usor, gandindu-ne cu cat creste numarul de inversiuni in functie de ultimul numar adaugat in permutare: $c[i][j] = c[i-1][j] + c[i-1][j-1] + ... + c[i-1][max(j-i+1, 0)]$. Din pacate, aceasta dinamica are complexitatea $O(N^2^K)$. Desi dinamica se poate reduce la complexitate $O(N*K)$ folosind sume partiale, ar insemna sa ne indepartam ca idee de solutia optima a problemei. Observam in dinamica de mai sus, ca pentru $K < i &le; N$, functia $max$ va returna mereu valoarea $0$, deci recurenta nu mai variaza in functie de $i$. Astfel, putem considera trecerea de la pasul $i$ la pasul $i+1$ o inmultire de matrici:

Problema este asemanatoare cu problema 'Perm6':/problema/perm6 si ne duce cu gandul, in prima faza, la o dinamica de forma $c[i][j]$ = numarul de permutari de $i$ elemente cu $j$ inversiuni. Recurenta iese usor, gandindu-ne cu cat creste numarul de inversiuni in functie de ultimul numar adaugat in permutare: $c[i][j] = c[i-1][j] + c[i-1][j-1] + ... + c[i-1][max(j-i+1, 0)]$. Din pacate, aceasta dinamica are complexitatea $O(N*K^2^)$. Desi dinamica se poate reduce la complexitate $O(N*K)$ folosind sume partiale, ar insemna sa ne indepartam ca idee de solutia optima a problemei. Observam in dinamica de mai sus, ca pentru $K < i &le; N$, functia $max$ va returna mereu valoarea $0$, deci recurenta nu mai variaza in functie de $i$. Astfel, putem considera trecerea de la pasul $i$ la pasul $i+1$ o inmultire de matrici:

<tex>\begin{pmatrix} c[i][0] & c[i][1] & ... & c[i][k] \end{pmatrix} * \begin{pmatrix} 1 & 1 & ... & 1 \\0 & 1 & ... & 1 \\... \\0 & 0 & ... & 1 \end{pmatrix} = \begin{pmatrix} c[i+1][0] & c[i+1][1] & ... & c[i+1][k]\end{pmatrix}</tex>.
Folosind proprietatea de asociativitate a inmultirii matricilor, putem deduce:

<tex>\begin{pmatrix} c[k+1][0] & c[k+1][1] & ... & c[k+1][k] \end{pmatrix} * \begin{pmatrix} 1 & 1 & ... & 1 \\0 & 1 & ... & 1 \\... \\0 & 0 & ... & 1 \end{pmatrix}^{n-k+1} = \begin{pmatrix} c[n][0] & c[n][1] & ... & c[n][k]\end{pmatrix}</tex>.
Inmultirea a doua matrici $K x K$ are complexitate $O(K^3^)$, iar ridicare la putere are complexitate $O(logN)$. Pentru a calcula dinamica pana la pozitia $K+1$, putem aplica recurenta de mai sus avand o complexitate $O(K^3^)$. Complexitatea finala este $O(K^3^logN)$.

<tex>\begin{pmatrix} c[k+1][0] & c[k+1][1] & ... & c[k+1][k] \end{pmatrix} * \begin{pmatrix} 1 & 1 & ... & 1 \\0 & 1 & ... & 1 \\... \\0 & 0 & ... & 1 \end{pmatrix}^{n-k-1} = \begin{pmatrix} c[n][0] & c[n][1] & ... & c[n][k]\end{pmatrix}</tex>.
Inmultirea a doua matrici $K x K$ are complexitate $O(K^3^)$, iar ridicarea la putere are nevoie de $O(logN)$ astfel de inmultiri. Pentru a calcula dinamica pana la pozitia $K+1$, putem aplica recurenta de mai sus avand o complexitate $O(K^3^)$. Complexitatea finala este $O(K^3^*logN)$.