Lkperm

Fie f(n) numărul total de permutări de n elemente care respectă proprietatea din enunţ. În momentul în care dorim să calculăm f(n), vom încerca să plasăm elementul maxim, adică pe n. Dacă el este plasat pe prima poziţie a permutării, atunci ea va arăta aşa:
n x1 x2 x3 ... xn-1
Elementul n va fi maximul doar pentru secvenţa n x1 x2 ... xL-1. Aşadar, în acest caz sunt f(n-1) posibilităţi.

Dacă plasăm elementul n pe cea de-a doua poziţie, permutarea va arăta aşa:
x1 n x2 x3 ... xn-1
Elementul n va fi maximul pentru două secvenţe, iar x1 poate lua orice valoare între 1 şi n-1, deoarece el nu poate fi maximul în nicio secvenţa. Aşadar, există (n-1)*f(n-2) posibilităţi.

Dacă plasăm elementul n pe cea de-a p-a poziţie, 1 ≤ p ≤ K permutarea va arăta astfel:
x1 x2 x3 ... xp-1 n xp+1 xp+2 ... xn-1
Elementul n va fi maximul pentru p secvenţe, iar primele p-1 elemente nu vor fi maxime în nicio secvenţă. Prin urmare vor fi (n-1)*(n-2)*(n-3)*...*(n-P-1)*f(n-P) posibilităţi

Aşadar, f(n)=f(n-1)+(n-1)*f(n-2)+(n-1)*(n-2)*f(n-3)+...+(n-1)*(n-2)*...*(n-K+1)*f(n-K), dacă n>L
f(n)=n!, altfel
Implementarea directă a acestei formule aduce 40 de puncte, deoarece are complexitatea O(N*K). Pentru 100 de puncte vom încerca să restrângem egalitatea şi observăm că
f(n-1)=f(n-2)+(n-2)*f(n-3)+...+(n-2)*(n-3)*...*(n-K)*f(n-K-1)
Deci f(n)=f(n-2)+(n-2)*f(n-3)+...+(n-2)*(n-3)*...*(n-K)*f(n-K-1)++(n-1)*f(n-2)+(n-1)*(n-2)*f(n-3)+...+(n-1)*(n-2)*...*(n-K+1)*f(n-K)
f(n)=n*f(n-2)+n*(n-2)*f(n-3)+...+n*(n-2)*(n-3)*...*(n-K+1)*f(n-K)+(n-2)*(n-3)*...*(n-K)*f(n-K-1)
f(n)=n*f(n-1)-(n-1)*(n-2)*...*(n-K)*f(n-K-1)