Revizia anterioară Revizia următoare
Pkinv
Problema este asemanatoare cu 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][j-1] + ... + c[i-1][max(j-i+1, 0]. Din pacate, aceasta dinamica are complexitatea O(N2K). 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 ≤ 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:
![\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}](https://www.infoarena.ro/static/images/latex/cdff120394a98cc5e26db673290622d7_22.50023pt.gif "\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}")
.
Folosind proprietatea de asociativitate a inmultirii matricilor, putem deduce:
![\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}](https://www.infoarena.ro/static/images/latex/3e2eba6079ee9ff4c84591a7e6247b2a_22.50023pt.gif "\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}")
.
Inmultirea a doua matrici K x K are complexitate O(K3), 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(K3). Complexitatea finala este O(K3logN).
