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-1][j-1] + ... + c[i-1][max(j-i+1, 0)]. Din pacate, aceasta dinamica are complexitatea O(N*K2). 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}.
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}.
Inmultirea a doua matrici K x K are complexitate O(K3), 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(K3). Complexitatea finala este O(K3*logN).