Indicatii Subset Fight

Indicații de rezolvare


Pentru 20 de puncte, se poate folosi metoda Backtracking pentru a genera submulțimile.

Pentru 60 de puncte, se poate defini următoarea recurență:

dp[i][j] = numărul de submulțimi ce conțin elemente dintre primele i, astfel încât restul la împărțirea cu n să fie j.

Pentru 100 de puncte, se pot precalcula pentru fiecare din cele i numere, câte submulțimi de numere au restul j la împărțirea la n, iar apoi se va folosi recurența de la soluția de 60 de puncte cu noile valori aflate.