Solutia problemei Omida Mincinoasa

Pentru inceput, observam ca C(n,i)·i^k inseamna de fapt sa alegem un subsir de lungime i a multimii {1,2,3,...,n}, si dupa aceea sa alegem o tupla de lungime k din subsirul respectiv. In acest fel, numaram toate perechile de tipul (subsir,tupla), dar acest lucru este echivalent cu a numara perechi de tipul (tupla, subsir). Observam in continuare ca pentru a alege un subsir care acopera o tupla de valori depinde doar de numarul de valori distincte x din tupla, iar numarul de moduri sa alegem subsirul este 2^n-x. Astfel daca vom gasi un mod prin care sa calculam numarul de tuple cu x valori distincte, am rezolvat problema.

Subtask 6: k ≤ 500

Putem folosi urmatoarea dinamica pentru a numara tuple: dp[i][j] = numarul de tuple de lungime i care contin toate valorile din [1,j]. Ca recurenta, sa spunem ca tupla noastra contine k > 1 valori egale cu j, atunci dp[i][j] += dp[i-k][j-1]·C(i,k).

Prin urmare, am rezolvat acest subtask in O(k³).

O implementare bazata pe aceasta idee poate fi vazuta aici.

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, cu o complexitate finala de O(maxk² + t·k).

O implementare bazata pe aceasta idee poate fi vazuta aici.