3639 - Subset Fight
Cerința
Un război se apropie, va trebui să ajuți combatanții să afle șansele lor de victorie.
Se dă un vector cu n numere naturale, unde v[i] reprezintă numărul de valori egale cu i. Un scenariu în care omenirea câștigă e un scenariu în care suma numerelor dintr-o submulțime este multiplu de n.
De exemplu, dacă vectorul din enunț este 1 2 3, valorile pe care le avem de fapt sunt 1 2 2 3 3 3, valori pe care le putem nota ca facând parte dintr-un nou vector, vectorul a, iar numărul de valori pe care îl avem este egal cu x = v[1]+v[2]+...+v[n].
Astfel, trebuie să aflați câte din cele 2x
submulțimi ale vectorului a au suma multiplu de n, modulo 109+7
Date de intrare
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, unde v[i] reprezintă numărul de valori egale cu i.
Date de ieșire=
Programul va afișa pe ecran răspunsul cerut.
Restricții și precizări
1 ≤ n ≤ 100 cele n numere citite vor fi mai mici decât 200000 Pentru 20 de puncte, suma numerelor din vector nu va depăși 20. Pentru 60 de puncte, suma numerelor din vector nu va depăși 100000. ==Exemplu==: Intrare
3 1 1 1 Ieșire
4 ==Exemplu== 2 Intrare
5 69 420 1017 128 953 Ieșire
985611225
Rezolvare
MOD = 10**9 + 7
def numar_submultimi(n, v):
# Inițializăm tabelul DP cu 0 DP = [[0] * n for _ in range(2)]
# Setăm valoarea inițială pentru submulțimile vide DP[0][0] = 1
for i in range(1, n + 1): # Trecem la o nouă matrice DP (pară/impară) current = i % 2 previous = 1 - current
for j in range(n): # Copiem valorile din matricea anterioară DP[current][j] = DP[previous][j]
# Actualizăm matricea curentă adăugând valorile corespunzătoare din vector DP[current][(j + i) % n] = (DP[current][(j + i) % n] + DP[previous][j]) % MOD
return DP[n % 2][0] - 1
if __name__ == "__main__":
# Citim datele de intrare n = int(input()) v = list(map(int, input().split()))
# Calculăm rezultatul și afișăm rezultatul rezultat = numar_submultimi(n, v) print(rezultat)
python combatanti.py