Prin urmare, am rezolvat acest subtask in $O(k^3^)$.

O implementare bazata pe aceasta idee poate fi vazuta "aici":lying.

O implementare bazata pe aceasta idee poate fi vazuta "aici":https://www.infoarena.ro/job_detail/3147762?action=view-source.

h2. Subtask 7: k ≤ 5000

Observam ca dinamica de mai sus numara functii surjective definite pe ${1,2,3,...,k}$ cu valori in ${1,2,3,...,j}$. Numararea acestor functii este un lucru cunoscut, o putem face prin diverse metode, solutia oficiala se foloseste de "numere Stirling de speta a 2-a":https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind, cu o complexitate finala de $O(maxk^2^ + t·k)$.

Observam ca dinamica de mai sus numara functii surjective definite pe ${1,2,3,...,k}$ cu valori in ${1,2,3,...,j}$. Numararea acestor functii este un lucru cunoscut, o putem face prin diverse metode, solutia oficiala se foloseste de "numere Stirling de speta a 2-a":https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind, cu o complexitate finala de $O(maxk^2^ + t·k)$.
 
O implementare bazata pe aceasta idee poate fi vazuta "aici":https://www.infoarena.ro/job_detail/3147763?action=view-source.