1834 - Memory005

Cerința

Se dă o mulţime A formată din n elemente, numere naturale ( evident distincte ). Aflaţi câte submulţimi nevide ale lui A au suma elementelor număr par.

Date de intrare

Fișierul de intrare memory005.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale distincte, separate prin spații, reprezentând elementele mulţimii A.

Date de ieșire

Fișierul de ieșire memory005.out va conține pe prima linie numărul S, reprezentând numărul submulţimilor nevide ale lui A care au suma elementelor număr par. Rezultatul se va afişa modulo 666013.

Restricții și precizări

• 1 ≤ n ≤ 1.000.000
• numerele de pe a doua linie a fișierului de intrare vor fi distincte şi mai mici decât 2.000.000.000

Exemplu:

memory005.in

4
1 3 8 2

memory005.out

7

Explicație

Avem mulţimea A={1,3,8,2}. Submulţimile nevide ale lui A având suma elementelor număr par sunt: {8}, {2}, {1,3}, {8,2}, {1,3,8}, {1,3,2}, {1,3,8,2}.

Încărcare soluție

Lipește codul aici

<syntaxhighlight lang="python" line="1"> import sys n, cnt, x = 0, 0, 0 MOD = 666013 sys.stdin = open('memory005.in', 'r') sys.stdout = open('memory005.out', 'w')

def put(n):

   p = 1
   for i in range(1, n+1):
       p *= 2
       p %= MOD
   return p

n = int(input()) for i in range(1, n+1):

   x = int(input())
   if x % 2 == 1:
       cnt += 1

if cnt == 0:

   print((put(n) - 1) % MOD)

else:

   print((put(n - 1) - 1) % MOD)

</syntaxhighlight>