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:
.
Folosind proprietatea de asociativitate a inmultirii matricilor, putem deduce:
.
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).