Iunie

Dacă N este impar, răspunsul este 0. Putem simplifica problema astfel:

  • Dându-se un număr N, se cere numărul de moduri în care N / 2 poate fi scris ca sumă de numere naturale nenule.

Ne dăm seama că prin setarea primului număr din scrierea lui N / 2, fie acesta X, cel de-al doilea număr va fi determinat de N / 2 - X. Numărul total de moduri în care putem seta primul număr, X, este (N / 2). Având în vedere că vrem să distingem între ele perechile (i, N / 2 - i) şi (N / 2 - i, i), rezultă că numărul total de moduri în care putem scrie (N / 2) ca sumă de numere naturale nenule este egal cu (N / 2) / 2 şi anume N / 4.

O luna

Pentru rezolvarea acestei probleme, ne vom folosi de observaţiile făcute în problema precedentă. Pentru a obţine perechi distincte de numere, vom "genera" numerele din perechi crescător. Pentru a simplifica problema, o vom enunţa astfel:

  • Dându-se un număr N, se cere numărul de moduri în care N / 2 poate fi scris ca sumă de numere naturale nenule.

Vom seta primul număr din pereche. În total, avem (N / 2) / 3 posibilităţi de a alege acest număr, fie el X (pentru că dorim ca primul număr să fie cel mai mic). Trebuie sa ne ocupam de restul de N / 2 - X. Ştim că numărul de modalităţi de a scrie acest număr ca sumă de două numere naturale nenule este (N / 2 - X) / 2 (din problema precedentă). Dintre acestea, trebuie să scăpăm de cele care încep cu un număr mai mic strict decât X. Cum acestea sunt în număr de X - 1, rezultatul va fi:

  • Sumă din [(N / 2 - i) / 2] - (i - 1), pentru i de la 1 la (N / 2) / 3, adică N / 6, unde [A] reprezintă partea întreagă a lui A.

Această sumă se poate calcula destul de uşor în O(1).

Tot o luna

Ne putem imagina că vrem să împărţim numărul N în K căsuţe. În fiecare căsuţă se va afla un număr par, iar produsul numerelor din căsuţe trebuie să fie egal cu N. Având în vedere că în fiecare căsuţă trebuie să existe un număr par, va trebui să avem cel puţin un factor de 2 în fiecare căsuţă. Prin urmare, dacă numărul N nu are cel puţin K factori de 2 în descompunerea sa, răspunsul va fi 0. Acum urmează să aranjăm aceşti factori de 2 din descompunerea lui N, fie ei F2, în cele K căsuţe, astfel încât să existe cel puţin un factor de 2 în fiecare căsuţă. Altfel spus, va trebui să determinăm numărul de moduri în care F2 poate fi scris ca sumă de exact K numere naturale, mai mari sau egale cu 1. Pentru aceasta, ne putem folosi de metoda programării dinamice:

  • d1[i][j] = numărul de posibilităţi în care poţi scrie j, ca sumă de i numere naturale mai mari sau egale decât 1.

Vom pregenera această matrice pentru a putea aşeza rapid factorii de 2 din scrierea lui N, pentru fiecare query în parte.

Acum, urmează să aşezăm restul factorilor din descompunerea în factori primi ai lui N. Procedeul va fi asemenea cu cel prezentat până acum. De această dată însă, nu suntem interesaţi ca fiecare căsuţă în parte din cele K să conţină cel puţin un factor din cei rămaşi. De aceea, putem pregenera o matrice cu o semnificaţie asemănătoare:

  • d0[i][j] = numărul de posibilităţi în care poţi scrie j, ca sumă de i numere naturale mai mari sau egale decât 0.

Având aceste informaţii disponibile, pentru fiecare query, vom descompune numărul N în factori primi, urmând să calculăm răspunsul folosindu-ne de aceste două matrici, pentru fiecare factor prim în parte şi puterea la care acesta apare.

Solutie alternativa (mai simpla)

Daca N nu e divizibil cu 2K atunci raspunsul e 0. In caz contrar, il impartim pe N la 2K si astfel putem considera ca am plasat cate un 2 in fiecare casuta. Il descompunem pe N in factori primi. Daca un factor apare la puterea X, il putem plasa in casute in comb(X+K-1,K-1) moduri.

Subsecvente