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

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)