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

<syntaxhighlight lang="python3" line="1"> 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>