1834 - Memory005
Cerința[edit | edit source]
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[edit | edit source]
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[edit | edit source]
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[edit | edit source]
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:[edit | edit source]
memory005.in
4 1 3 8 2
memory005.out
7
Explicație[edit | edit source]
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[edit | edit source]
Lipește codul aici[edit | edit source]
<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>