Sa notam cu P(N,K) numarul de permutari de N elemente in care exista
    K inversiuni. Nu stiu daca exista vreo formula nerecurenta care sa
    rezolve problema; in cele ce urmeaza insa, vom gasi o formula
    recurenta pentru P(N,K).
    
    I. Sa consideram cazul N=4, P=5. Permutarile de 4 elemente pot incepe
    cu un numar cuprins intre 1 si 4. Permutarile care incep cu 4 sunt
    urmatoarele:
    
    4123, 4132, 4213, 4231, 4312, 4321.
    
    Sa observam ca toate aceste permutari au minim 3 inversiuni, intrucat
    cifra 4 este asezata aiurea in raport cu cifrele 1, 2 si 3. Daca vrem
    sa aflam care din permutarile de mai sus au exact 5 inversiuni, putem
    proceda astfel:
    
    a) Ignoram cifra 4 si obtinem sirul de permutari de 3 elemente:
    
    123, 132, 213, 231, 312, 321.
    
    b) Dintre acestea, numaram permutarile care au 5-3=2 inversiuni (restul
    de 3 inversiuni fiind asigurate de cifra 4), gasind raspunsul 2 (312
    si 231). Important nu este raspunsul in sine, ci faptul ca am regasit
    problema originala de numarare, dar cu parametri mai mici (N'=3, P'=2).
    Asadar P(3,2)=2.
    
    II. Deci cu permutarile care incep cu 4 am terminat. Sa le vedem pe
    cele care incep cu 3:
    
    3124, 3142, 3214, 3241, 3412, 3421
    
    Stim ca cifra 3 genereaza exact 2 inversiuni, deoarece ea este asezata
    alandala in raport cu cifrele 1 si 2. Prin urmare, trebuie sa gasim
    acele permutari in care cifrele 1, 2 si 4 genereaza 5-2=3 inversiuni:
    
    a) Ignoram cifra 4 si obtinem sirul de permutari:
    
    124, 142, 214, 241, 412, 421.
    
    b) Aici regasim din nou o problema de dimensiuni mai mici: N"=3, P"=3.
    Exista o permutare cu 3 inversiuni (421). Deci P(3,3)=1.
    
    III. Cazurile permutarilor care incep cu 2 si cu 1 sunt speciale.
    Cifra 2 la inceputul unei permutari genereaza o singura inversiune
    (inversiunea 2-1), deci trebuie ca cifrele 1, 3 si 4 care ii urmeaza
    sa genereze 4 inversiuni. Acest lucru este imposibil, caci nu exista
    permutari de 3 elemente cu 4 inversiuni. De fapt, o permutare cu N
    elemente poate avea maxim N*(N-1)/2 inversiuni, in cazul permutarii
    inverse:
    
    N N-1 N-2 ... 3 2 1
    
    IV. Similar, cifra 1 la inceputul unei permutari nu genereaza nici o
    inversiune, deci ar trebui ca cifrele 2, 3 si 4 care ii urmeaza sa
    genereze 5 inversiuni, lucru imposibil. Scriem deci ca P(3,4)=P(3,5)=0.
    
    Per total, deoarece o permutare de 4 cifre poate incepe cu orice numar
    intre 1 si 4, obtinem formula:
    
    P(4,5) = P(3,2) + P(3,3) + P(3,4) + P(3,5)
    
    Sa generalizam pentru N si K oarecare. Permutarile de N pot incepe cu
    orice numar intre 1 si N.
    
    - Cele care incep cu N au deja N-1 inversiuni asigurate, deci ultimele
      N-1 cifre trebuie sa creeze K-N+1 inversiuni. Numarul acestor
      permutari este P(N-1, K-N+1).
    
    - Permutarile care incep cu un T oarecare au T-1 inversiuni asigurate,
      deci ultimele N-1 cifre trebuie sa creeze K-T+1 inversiuni. Numarul
      acestor permutari este P(N-1, K-T+1).
    
    - Permutarile care incep cu 1 nu au nici o inversiune asigurata, iar
      ultimele cifre trebuie sa genereze K inversiuni. Numarul acestor
      permutari este P(N-1, K).
    
    Deoarece T poate lua valori intre 1 si N, rezulta formula recurenta:
    
    P(N,K)= P(N-1,K) + P(N-1,K-1) + ... + P(N-1,K-N+1)
    
             N-1
             --
    P(N,K)=  >  P(N-1,K-T)
             --
             T=0
    
    Mai trebuie precizate punctele de oprire din recurenta:
    - daca virgula K<0 sau K>N*(N-1)/2, atunci P(N,K)=0.
    - P(1,0)=1.
    
    AMANUNTE PRIVIND IMPLEMENTAREA:
    
    A) Numerele sunt foarte mari. P(45, 495) are 54 de cifre. Deci este
    nevoie sa operam cu numere mari. Eu unul am preferat sa retin numerele
    ca pe niste vectori de cifre in baza 256, ca sa consum cat mai putina
    memorie. Trebuie observat ca P(N,0) + P(N,1) + ... + P(N, N*(N-1)/2)
    este chiar numarul total de permutari de N elemente, adica N! Cu alte
    cuvinte, P(N,K) poate avea ordinul de marime al lui N!. Numarul de
    cifre al lui P(N,K) este deci O(log(P(N,K)))=O(log(N!))= =O(N log N).
    Asadar orice operatie de adunare/scadere/afisare se face in O(N log N).
    
    B) Cel mai chior algoritm este:
    
    for i:=1 to N do
      for j:=0 to i*(i-1) div 2 do
        Calculeaza_recurent P(i,j)
    
    Calculeaza_recurent efectueaza la randul ei O(N) adunari de numere si
    are complexitatea O(N^2 log N). Per total algoritmul are complexitatea
    O(N^5 log N), sau O(N^4 * C), daca scriem functie de numarul de cifre.
    Programul scris pe aceasta idee merge cam in doua secunde.
    
    C) Optimizarea (si reducerea complexitatii cu un ordin de marime)
    provin din observatia ca P(N,K) si P(N, K-1) se calculeaza recurent ca
    doua sume foarte asemanatoare. Uitati:
    
    P(N,K-1) = P(N-1,K-1) + P(N-1,K-2) + ... + P(N-1,K-N+1) + P(N-1,K-N)
               \------------------- X --------------------/
    
    P(N,K) = P(N-1,K) + P(N-1,K-1) + ... + P(N-1,K-N+2) + P(N-1,K-N+1)
                        \-------------------- X ---------------------/
    
    Rezulta ca P(N,K) = P(N,K-1) - P(N-1,K-N) + P(N-1,K). Ce-i drept,
    devine necesara implementarea scaderii a doua numere mari, dar merita.
    
    Complexitatea noului algoritm este O(N^4 log N) = O(N^3*C). Scuze, am
    calculat gresit complexitatea cand v-am dat enuntul. Sper ca nu ati
    avut prea multe nopti albe in cautarea lui O(N^2 * C) :)
    
    D) P(N,K) depinde numai de elemente de forma P(N-1,K-T). In timpul
    calcularii, nu este nevoie sa retinem in memorie intreaga matrice P,
    ci numai linia i pe care o calculam si linia anterioara i-1. Memoria
    folosita se reduce deci la 2 linii a cate O(N^2) numere mari a cate
    O(N log N) cifre. Necesarul de memorie este O(N^3 log N).