Arbori

Problema se rezolva prin programare dinamica. Se construieste o matrice A[i][j][k] numarul de arbori cu urmatoarele proprietati:

  • au i noduri
  • gradul radacinii este j (mod M)
  • ultimul fiu al radacinii este un subarbore cu k noduri
  • fiecare nod intern din arbore (mai putin radacina) are gradul K (mod M)

Raspunsul se va gasi in A[N][K][N]. Arborii fiind neetichetat, ordinea fiilor nu conteaza, asadar putem considera ca fiecare nod are fiii in ordine crescatoare a numarului de noduri din subarbore.

Pentru a calcula A[i][j][k] vom itera o variabila x dupa numarul de fii ai radacinii cu fix k noduri in subarbore. Astfel, pentru fiecare x intre 0 si i/k vom aduna la A[i][j][k] valoarea A[i-x*k][(j-x) mod M][k-1] * Nr(k, x) unde Nr(k, x) este numarul de moduri in care se pot aranja x subarbori cu k noduri fiecare. Stim ca pentru subarborii de k noduri avem A[k][(K-1) mod M][N] posibilitati (K-1 deoarece ii legam de o radacina). Dintre toate aceste posiblitati trebuie sa alegem x, tinand cont de faptul ca ordinea nu conteaza. Numarul pe care il cautam va fi Nr(k, x) = Comb(A[k][(K-1) mod M][N]+x-1, x), deoarece Comb(n+k-1, k) reprezinta numarul de moduri in care n obiecte identice pot fi distribuite in k cutii distincte.
Complexitatea spatiu a rezolvarii este O(N2*M), iar complexitatea timp este O(N2*M*lg N), deoarece N/1+N/2+N/3...N/N = N*lg N (cand iteram x iteram doar pana la i/x). Desigur, am presupus ca putem calcula combinarile in O(1). Acest lucru chiar este posibil, presupunand ca avem valoarea combinarii pentru x, putem determina valorea pentru x+1 in O(1). Datorita limitelor mici, se putea obtine punctaj maxim si calculand combinarile in O(x), obtinand astfel o solutie O(N3*M). Rezolvarea se mai poate optimiza folosind tehnica de memoizare.