3639 - Subset Fight: Difference between revisions
Pagină nouă: ==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 ve... |
No edit summary |
||
| Line 37: | Line 37: | ||
985611225 | 985611225 | ||
==Rezolvare== | ==Rezolvare== | ||
<syntaxhighlight lang="python3"> | |||
MOD = 10**9 + 7 | MOD = 10**9 + 7 | ||
def numar_submultimi(n, v): | 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__": | 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) | |||
</syntaxhighlight> | |||
Revision as of 17:41, 11 January 2024
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
<syntaxhighlight lang="python3"> 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)
</syntaxhighlight>