A - Biscuits
最初は2^50のbit全探索を考えました。
2^50は「1.1258999e+15」ですね。
どう見てもTLEです。
python
import math
N, P = list(map(int, input().split()))
A = list(map(int, input().split()))
res = 0
for bit in range(0, 2 ** N):
total = 0
for i in range(0, N):
if (bit >> i) & 1:
total += A[i]
if total % 2 == P:
res+=1
print(res)
ここで奇数と偶数に注目しました。
p=0の時、数列の偶数の要素をnとした時の組み合わせは、
V1 = 1 (n = 0) \\
V1 = \sum_{k=1}^{n} {}_nC_k
p=0の時、数列の奇数の要素をN-nとした時の組み合わせは、
奇数を偶数だけ取り除いた物がP=0になります。
V2 = 1 (N-n = 0) \\
V2 = \sum_{k=0}^{N-n} {}_nC_k (k = 0, 2, 4, ... )
組み合わせの積の法則により、
合計 = V1 * V2
p=1の時、数列の偶数の要素をnとした時の組み合わせは、
V1 = 1 (n = 0) \\
V1 = \sum_{k=1}^{n} {}_nC_k
p=1の時、数列の奇数の要素をN-nとした時の組み合わせは、
奇数を奇数だけ取り除いた物がP=1になります。
V2 = \sum_{k=1}^{N-n} {}_nC_k (k = 1, 3, 5, ... )
組み合わせの積の法則により、
合計 = V1 * V2
python
import math
def combinations_count(n, r):
return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N, P = list(map(int, input().split()))
A = list(map(int, input().split()))
res = 0
for i in range(0, N):
if A[i] % 2 == P:
res += 1
if P == 0:
V1 = 0
total = (len(A) - res)
for i in range(0, total+1, 2):
V1 += combinations_count(total, i)
total = res
V2 = 0
for i in range(0, total+1, 1):
V2 += combinations_count(total, i)
if V1 == 0:
V1 = 1
if V2 == 0:
V2 = 1
res = V1 * V2
else:
V1 = 0
total = (len(A) - res)
for i in range(0, total+1, 1):
V1 += combinations_count(total, i)
total = res
V2 = 0
for i in range(1, total+1, 2):
V2 += combinations_count(total, i)
if V1 == 0:
V1 = 1
res = V1 * V2
print(res)
感想
自力でACできたので組み合わせの勉強の成果が出たと思います。