Problem:


Score : 200 points

Problem Statement

There are N bags of biscuits. The i-th bag contains A_i biscuits.

Takaki will select some of these bags and eat all of the biscuits inside.
Here, it is also possible to select all or none of the bags.

He would like to select bags so that the total number of biscuits inside is congruent to P modulo 2.
How many such ways to select bags there are?

Constraints

1 \leq N \leq 50

P = 0 or 1

1 \leq A_i \leq 100

Input

Input is given from Standard Input in the following format:

N P
A_1 A_2 ... A_N

Output

Print the number of ways to select bags so that the total number of biscuits inside is congruent to P modulo 2.

Sample Input 1

2 0
1 3

Sample Output 1

2

There are two ways to select bags so that the total number of biscuits inside is congruent to 0 modulo 2:

Select neither bag. The total number of biscuits is 0.

Select both bags. The total number of biscuits is 4.

Sample Input 2

1 1
50

Sample Output 2

0

Sample Input 3

3 0
1 1 1

Sample Output 3

4

Two bags are distinguished even if they contain the same number of biscuits.

Sample Input 4

45 1
17 55 85 55 74 20 90 67 40 70 39 89 91 50 16 24 14 43 24 66 25 9 89 71 41 16 53 13 61 15 85 72 62 67 42 26 36 66 4 87 59 91 4 25 26

Sample Output 4

17592186044416



Sample input:
2 0
1 3


Sample output:
2

Submission status: Accepted

Solution code:
from collections import Counter
import itertools
import math

n, p = map(int, input().split())
alist = map(int, input().split())

d = Counter()
for a in alist:
    d[a % 2] += 1

# print(d)

zeros = 2 ** d[0]


ones = 0
if p == 0:
    for i in range(d[1]+1):
        if i % 2 == 0:
            ones += math.factorial(d[1]) // (math.factorial(d[1] - i) * math.factorial(i))
        # print(i)
        # print(ones)
else:
    for i in range(d[1]+1):
        if i % 2 == 1:
            ones += math.factorial(d[1]) // (math.factorial(d[1] - i) * math.factorial(i))
        # print(i)
        # print(ones)

# print(zeros)
# print(ones)

print(zeros * ones)

Submission status: Accepted

Solution code:
import math
def C(n, k):
    return math.factorial(n) / math.factorial(k) / math.factorial(n - k)

n, p = map(int, raw_input().split())
a = [int(i) for i in raw_input().split()]

even = 0
for ai in a:
  if ai % 2 == 0:
    even += 1
 
odd = len(a) - even
ans = 0

for x in range(0, even + 1):
    for y in range(0, odd + 1):
        if (y % 2 == p):
            ans += C(even, x) * C(odd, y)
print ans

Submission status: Accepted

Solution code:
def solve():
    N, P = list(map(int, input().split()))
    A = list(map(int, input().split()))
    if all([x % 2 == 0 for x in A]):
        if P == 0:
            print(2 ** N)
        else:
            print(0)
    else:
        print(2 ** (N-1))

solve()

Submission status: Accepted

Solution code:
input1 = list(map(int,input("").split(" ")))
A = list(map(int,input("").split(" ")))
N = input1[0]
P = input1[1]

even = []
odd = []
for a in A:
	if a % 2 == 0:
		even.append(a)
	else:
		odd.append(a)

if len(odd) == 0:
	if P == 0:
		result = 2**N
	else:
		result = 0
else:
	result = 2**len(even) * 2**(len(odd)-1)

print(result)

Submission status: Accepted

Solution code:

input1s = input()
input2s = input()

input1 = [int(i) for i in input1s.split(' ')]
N = input1[0]
P = input1[1]
array = [int(i) for i in input2s.split(' ')]

count = 0

for i in range(len(array)):
  if(array[i]%2 == 1):
    count = 1

if(count == 0):
  if(P == 0): print (2**N)
  else: print(0)
else:
  print (2**(N-1))

Submission status: Accepted

Solution code:
import sys

N, P = map(int, input().split())
A = list(map(int, input().split()))
dp = [[1 - i for _ in range(N + 1)] for i in range(2)]

for i in range(N):
    # 食べない
    dp[0][i + 1] = dp[0][i]
    dp[1][i + 1] = dp[1][i]

    # 食べる
    if A[i] % 2:
        dp[0][i + 1] += dp[1][i]
        dp[1][i + 1] += dp[0][i]
    else:
        dp[0][i + 1] += dp[0][i]
        dp[1][i + 1] += dp[1][i]

print(dp, file=sys.stderr)
print(dp[P][N])

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


def nCr_table(n):
    table = [[None] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        for j in range(i + 1):
            if j == 0 or j == i:
                table[i][j] = 1
            else:
                table[i][j] = table[i - 1][j - 1] + table[i - 1][j]
    return table


def main():
    N, P = map(int, input().split())
    A_list = list(map(int, input().split()))

    nCr = nCr_table(100)

    e, o = 0, 0
    for a in A_list:
        e += a % 2 == 0
        o += a % 2 == 1

    a = 0
    for i in range(0, e + 1):
        a += nCr[e][i]
    if P == 0:
        b = sum([nCr[o][i] for i in range(0, o + 1, 2)])
        print(a * b)
    else:
        b = sum([nCr[o][i] for i in range(1, o + 1, 2)])
        print(a * b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def biscuits():
	n,p = map(int, raw_input().split(" "))
	a = map(int, raw_input().split(" "))
	from math import pow
	has_odd = False
	for item in a:
		if item%2!=0:
			has_odd = True
			break
	if not has_odd:
		if p==0:
			print int(pow(2, n))
		else:
			print 0
	else:
		print int(pow(2, n-1))

if __name__ == "__main__":
	biscuits()

Submission status: Accepted

Solution code:
N,P=map(int,input().split())
A=list(map(int,input().split()))
odd=0
for i in range(N):
  if A[i]%2==1: odd+=1
if odd==0:
  if P==1: print(0)
  else: print(2**N)
else:
  print(2**(N-1))

Submission status: Accepted

Solution code:
N,P=list(map(int,input().strip().split(' ')))
A=list(map(int,input().strip().split(' ')))
import math
odd=0
even=0
for i in range(len(A)):
    if A[i]%2==0:
        even+=1
    else:
        odd+=1
ans=0
def bino(a,b):
    return math.factorial(a)//(math.factorial(a-b)*math.factorial(b))


if P==0:
    for i in range(even+1):
        for j in range(0,odd+1,2):
            ans+=bino(even,i)*bino(odd,j)
else:
    for i in range(even+1):
        for j in range(1,odd+1,2):
            ans+=bino(even,i)*bino(odd,j)    
print(ans)

Submission status: Accepted

Solution code:
from math import factorial


def nCk(n, k):
    return factorial(n) // factorial(k) // factorial(n-k)


N, P = map(int, input().split())
A = [int(x) & 1 for x in input().split()]
even, odd = A.count(0), A.count(1)
print((1 << even) * sum(nCk(odd, i) for i in range(P == 1, odd + 1, 2)))

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
A = map(int, input().split())

n_even = len(list(filter(lambda x: x % 2 == 0, A)))
n_odd = N - n_even
ans = (2 ** max(0, n_odd - 1)) * (2 ** n_even)
if P == 1 and n_odd == 0:
    print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
(n, k) = tuple(map(lambda x: int(x), input().split(' ')))
x = input().split(' ')
cnt = 0
for i in range(0, n):
    if int(x[i]) % 2 == 1: cnt += 1

ans = 2 ** (n - cnt)
if cnt % 2 == 1:
    ans *= 2 ** (cnt - 1)
else:
    cur = cnt
    if k == 0: cur = 1
    counter = cur
    for m in range(k, cnt - 1, 2):
        # print(cnt, m, cur)
        cur = cur * (cnt - m) * (cnt - m - 1) // ((m + 1) * (m + 2)) 
        # print(cnt, m, cur)
        counter += cur
    ans *= counter
print(ans)

Submission status: Accepted

Solution code:
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(input().split())
 
n, p = rli()
a = rli()
 
odd = 0
even = 0
for i in a:
    if(i % 2 == 0):
        even += 1
    else:
        odd += 1
ans = 2**max(0, odd-1)*2**(even)
if(p == 1 and odd == 0):
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

# AtCoder Grand Contest 017
# A - Biscuits

import sys, re

def solve(N, P, A):
  m = len([a for a in A if a % 2 != 0])  # the num of odd numbers in A
  if m > 0:
    return 2 ** (N-1)
  else:
    return 2 ** N if P == 0 else 0

def splitIntoNums(line):
  words = re.split(r'\s+', line.strip())
  return [int(w) for w in words]  # convert to int

while True:
  l1 = sys.stdin.readline()
  l2 = sys.stdin.readline()
  if not l1: break
  N, P = splitIntoNums(l1)
  A    = splitIntoNums(l2)
  if len(A) != N: raise
  print(solve(N, P, A))


# 以降, コメント:
#
# 奇数枚のビスケットが入っている袋数を m とする
# (偶数枚のビスケットが入っている袋数は N-m).
#
# 補題:
# m > 0 とする. m個の物のうち偶数個を選ぶ選び方は 2 ** (m-1) 通り,
# 奇数個を選ぶ選び方も 2 ** (m-1) 通りである.
# (mに関する数学的帰納法で示せる.)
#
# m > 0 の場合:
#   P == 0 のとき:
#     奇数枚のビスケットが入っている袋を偶数個選ぶ必要がある.
#     偶数枚のビスケットが入っている袋は何個選んでもよい.
#     m個の袋から偶数個選ぶ選び方は 2 ** (m-1) 通り.
#     N-m個の袋から任意の個数選ぶ選び方は 2 ** (N-m) 通り.
#     従って, 選び方は全部で 2 ** (N-1) 通り.
#   P == 1 のときも同様に, 選び方は全部で 2 ** (N-1) 通り.
# m == 0 の場合:
#   どのように選んでもビスケットは偶数枚になる. 従って,
#    P == 0 ならば 2 ** N 通り, P == 1 ならば 0 通り.

Submission status: Accepted

Solution code:
from collections import Counter
from scipy.misc import comb

n, p = map(int, input().split())
ac = Counter(int(x) & 1 for x in input().split())
print(sum(comb(ac[1], c, exact=True) for c in range(p, ac[1] + 1, 2)) << ac[0])

Submission status: Accepted

Solution code:
from collections import Counter
from scipy.misc import comb

n, p = map(int, input().split())
ac = Counter(int(x) & 1 for x in input().split())

ans = 0

for c in range(p, ac[1] + 1, 2):
    ans += comb(ac[1], c, exact=True)

ans <<= ac[0]

print(ans)

Submission status: Accepted

Solution code:
n, a = list(map(int, input().strip().split(' ')))
d = list(map(int, input().strip().split(' ')))

even = sum([1 for i in d if i%2==0])
odd  = sum([1 for i in d if i%2==1])
ret = 0
if odd == 0:
    if a == 0:
        ret = 2**even
else:
    ret = (2**even) * (2**(odd-1))
print(ret)

Submission status: Accepted

Solution code:
n, p = [int(i) for i in input().split()]
odd_a = any([int(i) % 2 == 1 for i in input().split()])
if odd_a:
    print(2**(n-1))
elif p == 0:
    print(2**n)
else:
    print(0)

Submission status: Accepted

Solution code:
import math

def C(n, r):
    if (n == r or r == 0):
        return 1
    if (r > n):
        return 0
    f = math.factorial

    ret = f(n) / (f(r) * f(n - r))
    return int(ret)


n,p = map(int, input().split())
x = list(map(int, input().split()))

odd = even = ans = 0

for i in range(n):
    if (x[i] % 2 == 0):
        even+=1
    else:
        odd+=1

print("")

for i in range(n + 1):
    for j in range(i + 1):
        if (p == 1 and j % 2 == 1) or (p == 0 and j % 2 == 0):
            ans += C(even, i - j) * C(odd, j)

print(ans)

Submission status: Accepted

Solution code:
def f():
 for x in a:
  if x%2==0:
   continue
  else:
   return False
 return True

n,p=map(int,raw_input().split())
a=map(int,raw_input().split())

if f()==True and p==0:
 print 2**n
elif f()==True and p==1:
 print 0
else:
 print 2**(n-1)

Submission status: Accepted

Solution code:
N,P =map(int, input().split())
A = list(map(int, input().split()))
l0,l1=0,0

for a in A:
    if a%2==0:
        l0 +=1
    else:
        l1 +=1

if P==1 and l1==0:
    print(0)
elif P==0 and l1==0:
    print(2**N)
else:
    print(2**(N-1))

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
a=list(map(int,input().split()))
k=m=0
for i in a:
    if i%2==0:
        k +=1
m=n-k

ans_x=ans_y=0

def cbn(b,c):
    z=1
    for i in range(2,b+1):
        z *= i
    for i in range(2,c+1):
        z //= i
    for i in range(2,b-c+1):
        z //= i
    return(z)


if p==0:

    for i in range(k+1):
        ans_x += cbn(k,i)
    for i in range(0,m+1,2):
        ans_y += cbn(m,i)

    print(ans_x * ans_y)

else:

    for i in range(k+1):
        ans_x += cbn(k,i)
    for i in range(1,m+1,2):
        ans_y += cbn(m,i)

    print(ans_x * ans_y)

Submission status: Accepted

Solution code:
#AGC017A

def f():
 res=1
 for x in a:
  if x%2==0:
   res*=1
  else:
   res=0
   return res
 return res

n,p=map(int,raw_input().split())
a=map(int,raw_input().split())

if f()==1 and p==0:
 print 2**n
elif f()==1 and p==1:
 print 0
else:
 print 2**(n-1)

Submission status: Accepted

Solution code:
N, P = list(map(int, input().split(" ")))
A = list(map(int, input().split(" ")))

odd_flag = False
for a in A:
    if a % 2 == 1:
        odd_flag = True
        break
        
if odd_flag == True:
    print(2**(N-1))
elif((odd_flag == False) and (P == 0)):
    print(2**N)
else:
    print(0)

Submission status: Accepted

Solution code:
def comb(a,b):
    if b == 0:
        return 1
    elif a < b:
        return 0
    else:
        return comb(a-1,b-1) * a / b

n,p = map(int, raw_input().split())
l = map(int, raw_input().split())
en = len(filter(lambda x: x % 2 == 0, l))
on = n - en
if p == 1:
    ct = 0
    for i in range(1,on+1,2):
        ct += comb(on, i)
else:
    ct = 0
    for i in range(0,on+1,2):
        ct += comb(on,i)
print ct * (2**en)

Submission status: Accepted

Solution code:
import math

def main():
    N, P = map(int, input().split())
    A = tuple(map(int, input().split()))

    for i in range(N):
        if A[i] % 2:
            odd = 1
            break
    else:
        odd = 0

    if odd:
        ans = 2 ** (N - 1)
    else:
        if P:
            ans = 0
        else:
            ans = 2 ** N

    print(ans)

main()

Submission status: Accepted

Solution code:
import math
 
 
def comb(n, r):
    return math.factorial(n) / math.factorial(r) / math.factorial(n - r)
 
 
def main():
    n, p = map(int, input().split())
    a = tuple(map(lambda x: int(x) % 2, input().split()))
 
    if n == 1 and a[0] % 2 != p:
        print(0)
        return 0
 
    t = len(tuple(filter(lambda x: x == 1, a)))
    f = n - t
 
    f_comb = 0
    for j in range(f + 1):
        f_comb += comb(f, j)
 
    t_comb = 0
    if p == 0:
        for i in range(t + 1):
            if i % 2 == 0:
                t_comb += comb(t, i)
    else:
        for i in range(t + 1):
            if i % 2 == 1:
                t_comb += comb(t, i)
 
    print(int(t_comb * f_comb))
 
    return 0
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, p = map(int, input().split())

count = {0: 0, 1: 0}
for a in input().split():
    count[int(a) % 2] += 1

if count[1] == 0:
    if p == 0:
        print(pow(2, n))
    else:
        print(0)
else:
    print(pow(2, n - 1))

Submission status: Accepted

Solution code:
N,P = map(int,raw_input().split());
A = map(int,raw_input().split());
odd = sum(map(lambda x:x%2,A));
even = N - odd;
ans = 1 << even;

if P:
    if odd == 0: ans = 0;
    else:
        ans *= (1 << odd) >> 1;
else:
    if odd != 0: ans *= (1 << odd) >> 1;

print(ans);

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
import itertools, math
N, P = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
odd = [ tmp for tmp in a if tmp%2 != 0]
even = [ tmp for tmp in a if tmp%2 == 0]
d = math.factorial(len(odd))
e = math.factorial(len(even))
if P == 0:
    ans += 1
    b = sum([ (d//math.factorial(len(odd)-tmp))//math.factorial(tmp) for tmp in range(2, len(odd)+1, 2) ])
else:
    b = sum([ (d//math.factorial(len(odd)-tmp))//math.factorial(tmp) for tmp in range(1, len(odd)+1, 2) ])
c = [ (e//math.factorial(len(even)-tmp))//math.factorial(tmp) for tmp in range(1, len(even)+1) ]
for tmp in c:
    ans += tmp*b
else:
    if P == 0:
        ans += b+sum(c)
    else:
        ans += b
print(ans)

Submission status: Accepted

Solution code:
def makePascal(n):  # l[m][k] で mCk を取り出せるリストを返す
	res = [[1]]

	for m in range(1, n+1):
		l = []
		for k in range(m + 1):
			if k == 0 or k == m:
				l.append(1)
			else:
				tmp = res[m-1][k-1] + res[m-1][k]
				l.append(tmp)
		res.append(l)

	return res

N, P = map(int, input().split())
A = list(map(int, input().split()))

for i in range(N):
	if A[i] % 2 == 0:
		A[i] = 0
	else:
		A[i] = 1

ans = 0
comb = makePascal(N)
if P == 0:
	vol = 2 ** A.count(0)
	odds = A.count(1)
	i = 0
	while True:
		if i > odds:
			break
		else:
			ans += comb[odds][i] * vol
			i += 2
else:
	vol = 2 ** A.count(0)
	odds = A.count(1)
	i = 1
	while True:
		if i > odds:
			break
		else:
			ans += comb[odds][i] * vol
			i += 2
	
print(ans)

Submission status: Accepted

Solution code:
import math


def comb(n, r):
    return math.factorial(n) / math.factorial(r) / math.factorial(n - r)


def main():
    n, p = map(int, input().split())
    a = tuple(map(lambda x: int(x) % 2, input().split()))

    if n == 1 and a[0] % 2 != p:
        print(0)
        return 0

    t = len(tuple(filter(lambda x: x == 1, a)))
    f = n - t

    f_comb = 0
    for j in range(f + 1):
        f_comb += comb(f, j)

    t_comb = 0
    if p == 0:
        for i in range(t + 1):
            if i % 2 == 0:
                t_comb += comb(t, i)
    else:
        for i in range(t + 1):
            if i % 2 == 1:
                t_comb += comb(t, i)

    print(int(t_comb * f_comb))

    return 0


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, P = list(map(int, input().split()))
A = list(map(int, input().split()))

odd = len([a for a in A if a % 2 == 1])

if P == 1 and odd == 0:
    print(0)
elif P == 0 and odd == 0 :
    print(2 ** N)
else:
    print(2 ** (N - 1))

Submission status: Accepted

Solution code:
_, P = map(int, input().split())
A = [int(s) % 2 == 0 for s in input().split()]

evens = len(list(filter(lambda x: x == True, A)))
odds = len(A) - evens

evens_x = pow(2, evens)

if odds == 0 and P == 0:
    print(int(evens_x))
elif odds == 0 and P == 1:
    print(0)
else:
    odds_x = pow(2, odds - 1)
    print(int(evens_x * odds_x))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

N,P = map(int, raw_input().split())
a = map(int, raw_input().split())

count_0 = 0
count_1 = 0
number = 0

def comb(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i in range(r)]
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= numerator[k]
    return result

for i in range(N):
    if a[i] % 2 == 0:
        count_0 += 1
    else:
        count_1 += 1


if P == 0:
    if count_1 == 0:
        number = 1
    else:
        for j in range(count_1 /2 +1):
            number += comb(count_1,2*j)
else:
    if count_1 != 0:
        if count_1 % 2 == 0:
            for j in range(1,count_1 / 2 + 1):
                number += comb(count_1,2*j - 1)
        else:
            for j in range(1,count_1/2 + 2):
                number += comb(count_1, 2*j - 1)

if number != 0:
    print number * (2**count_0)
else:
    print number

Submission status: Accepted

Solution code:
import functools

import math

@functools.lru_cache()
def combinations(n, r):
    return math.factorial(n) / math.factorial(r) / math.factorial(n - r)


def main():
    n, p = map(int, input().split())
    a = tuple(map(lambda x: int(x) % 2, input().split()))

    if n == 1 and a[0] % 2 != p:
        print(0)
        return 0

    t = len(tuple(filter(lambda x: x == 1, a)))
    f = n - t

    count = 0

    if p == 0:
        for i in range(t + 1):
            if i % 2 == 0:
                c = 0
                for j in range(f + 1):
                    c += combinations(f, j)
                count += combinations(t, i) * c
    else:
        for i in range(t + 1):
            if i % 2 == 1:
                c = 0
                for j in range(f + 1):
                    c += combinations(f, j)
                count += combinations(t, i) * c

    print(int(count))

    return 0

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

n,p =input().split()
n = int(n)
p = int(p)

a_list = input().split()
a_list = [int(x) for x in a_list]
a_array = np.array(a_list)

amari = a_array % 2

zero_count = np.sum(amari == 0)
one_count = np.sum(amari == 1)

zero_pattern = 2**zero_count
if p == 0:
    if one_count >= 2:
        one_pattern = 2**one_count/2
    else:
        one_pattern = 1
else:
    if one_count >= 1:
        one_pattern = 2**one_count/2
    if one_count < 1:
        one_pattern = 0
        
print(int(zero_pattern * one_pattern))

Submission status: Accepted

Solution code:
import math
import itertools

N,P = [int(i) for i in input().split(" ")]
A = [int(i) for i in input().split(" ")]
k = 0
for i in range(N):
    if int(A[i] % 2) == P:
        k += 1

if k == 0:
    if P == 0:
        tmp = 0
        i = 0
        while i <= N-k:
            tmp += int(math.factorial(N-k)/(math.factorial(N-k-i)*math.factorial(i)))
            i += 2
        print(tmp)
    elif P == 1:
        print(0)
else:
    tmp = 0
    i = 0
    while i <= N-k:
        tmp += int(math.factorial(N-k)/(math.factorial(N-k-i)*math.factorial(i)))
        i += 2
    print(pow(2,k)*tmp)

Submission status: Accepted

Solution code:
n,p=map(int,raw_input().split())
a=map(int,raw_input().split())
od=sum(k%2 for k in a)
ev=sum(1-k%2 for k in a)
if p==0:
	if od==0: print 2**n
	else: print 2**(n-1)
else:
	if od==0: print 0
	else: print 2**(n-1)

Submission status: Accepted

Solution code:
import sys

n, p = map(int, input().split(" "))

a = list(map(int, input().split(" ")))

def combi(n, k):
    # if k == 0 or n == k:
        # return 1
    # c = min(k, n - k)
    a = 1
    b = 1
    for i in range(k):
        a *= i+1
        b *= n-i
    return b // a

oddcnt = 0

for i in a:
    if i % 2 == 1:
        oddcnt += 1

evencnt = n - oddcnt

if oddcnt == 0 and p == 1:
    print(0)
    sys.exit()

evencomb = 0
for i in range(0, evencnt+1):
    evencomb += combi(evencnt, i)

oddcomb = 0
for i in range(p, oddcnt+1, 2):
    oddcomb += combi(oddcnt, i)

if evencomb != 0:
    if oddcomb != 0:
        print(evencomb * oddcomb)
    else:
        print(evencomb)
else:
    print(oddcomb)

Submission status: Accepted

Solution code:
def spaceinput():
    return list(map(int,input().split(" ")))

N,P=list(map(int,input().split(" ")))
a=spaceinput()

dp=[[0,0] for i in range(N)]

if a[0]%2==0:
    dp[0][0]=2
    dp[0][1]=0
else:
    dp[0][0]=1
    dp[0][1]=1


for k in range(1,len(a)):
    if a[k]%2==0:
        dp[k][0]=dp[k-1][0]*2
        dp[k][1]=dp[k-1][1]*2
    else:
        dp[k][0]=dp[k-1][1]+dp[k-1][0]
        dp[k][1]=dp[k-1][0]+dp[k-1][1]


print(dp[N-1][P])

Submission status: Accepted

Solution code:
import sys

def biscuit(N, P, As):
    n_even = 0
    n_odd = 0
    for a in As:
      if int(a) % 2 == 0:
        n_even += 1
      else:
        n_odd +=1
    v = 2**n_even
    #print(n_even, n_odd)
    if n_odd == 0:
      v *= (0 if int(P) == 1 else 1)
    else:
      v *= 2**(n_odd -1)
    return v

N, P = sys.stdin.readline().strip().split()
As = sys.stdin.readline().strip().split()
print(biscuit(N, P, As))

Submission status: Accepted

Solution code:
import math

def main():
    N, P = map(int, input().split())
    A = tuple(map(int, input().split()))

    even = 0
    odd = 0
    for i in range(N):
        if A[i] % 2:
            odd += 1
        else:
            even += 1

    if P:
        i = 1
    else:
        i = 0
    bisket1 = 0
    while i <= odd:
        bisket1 += (math.factorial(odd) // math.factorial(odd - i)) // math.factorial(i)
        i += 2

    bisket2 = 0
    i = 0
    while i <= even:
        bisket2 += (math.factorial(even) // math.factorial(even - i)) // math.factorial(i)
        i += 1

    print(bisket1 * bisket2)

main()

Submission status: Accepted

Solution code:
def make_comb_dp(n):
    dp = [[0] * (n + 1) for i in xrange(n + 1)]
    for i in xrange(n + 1):
        dp[i][0] = 1
        dp[i][i] = 1
    for i in xrange(2, n + 1):
        for j in xrange(1, i):
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
    return dp



[N,P]=map(int,raw_input().split())
A= [int(x)%2 for x in raw_input().split()]
odd=A.count(1)
even=A.count(0)
dp=make_comb_dp(N)
#P=0
ans=1
for n in range(1,N+1):
    for i in range(0,odd/2+1):
            ans+=dp[odd][i*2]*dp[even][n-i*2]
if P:
    ans=sum(dp[N]) -ans
print ans

Submission status: Accepted

Solution code:
import math
n, p = [int(i) for i in input().split()]
a = [int(i) % 2 for i in input().split()]
def nCr(n, r):
    f = math.factorial
    return f(n) // f(r) // f(n-r)
print(sum([nCr(a.count(1), i) for i in range(p, a.count(1) + 1, 2)]) * (2**a.count(0)))

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
A = map(int, input().split())

even = odd = 0

def fact(n):
    if n == 0: return 1
    return n * fact(n-1)

for a in A:
    if a % 2 == 0:
        even += 1
    else:
        odd += 1

odd_even = 0
for i in range(odd + 1):
    if i % 2 == 0:
        odd_even += fact(odd)/(fact(i)*fact(odd-i))

if P == 0:
    print(int(2**even * odd_even))
else:
    print(int(2**even * (2**odd - odd_even)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

N, P = map(int, input().split())

A_temp = list(map(int, input().split()))
A = []

for a in A_temp:
    A.append(a % 2)

zero_num = A.count(0)
one_num = A.count(1)

def Combination(n, m):
    #print(str(n) + "C" + str(m))
    f = math.factorial
    return f(n) // f(m) // f(n - m)

combination_for_one = 0
if P == 0:
    for i in range(0, one_num + 1, 2):
        combination_for_one += Combination(one_num, i)
else:
    for i in range(1, one_num, 2):
        combination_for_one += Combination(one_num, i)

ans = combination_for_one * (2 ** zero_num)
print(ans)

Submission status: Accepted

Solution code:
def odd(n):
    return n % 2 == 1
    
def even(n):
    return n % 2 == 0

from math import factorial as fact
def c(n, r):
    if n < r:
        return 0
    if n == 0:
        return 0
    if r == 0:
        return 1
    return fact(n) // (fact(n-r) * fact(r))

n, p = map(int, input().split())
a = list(map(int, input().split()))
o = [i for i in a if odd(i)]
e = [i for i in a if even(i)]
x = len(o)
y = len(e)
yc = 0
for i in range(y):
    yc += c(y, i + 1)
ans = 0
if p == 0:
    ans += 1
i = 2 - p
while True:
    if i > x:
        break
    ans += c(x, i)
    ans += c(x, i) * yc
    i += 2
if p == 0:
    ans += yc
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import scipy.misc as scm

N, P = map(int, input().split())
A = list(map(int, input().split()))
A = np.array(A)

evens = A[A%2==0]
le = len(evens)
odds = A[A%2==1]
lo = len(odds)
ans = 0

for i in range(N+1) :
    for j in range(P,i+1,2) :
        ans += scm.comb(lo, j, 1)*scm.comb(le, i-j, 1)

print(ans)

Submission status: Accepted

Solution code:
# from itertools import combinations
N, P = list(map(int,input().split()))
A = list(map(int,input().split()))
count = 0
# for i in range(N+1):
# 	for a in combinations(A, i):
# 		if sum(a) % 2 == P:
# 			count += 1
for a in A:
	if a % 2 == 0:
		count+=1
# print(count, N-count)
evenans = 1
oddans = 0
for i in range(1,count+1):
	c = 1
	m = 1
	# print(i+1, end=':')
	for j in range(i):
		c*=(count-j)
		m*=(j+1)
	evenans += c/m
	# print(evenans)
if P == 0:
	oddans += 1
	for i in range(2, N-count+1,2):
		c = 1
		m = 1
		# print(i, end=':')
		for j in range(i):
			c*=(N-count-j)
			m*=(j+1)
		oddans += c/m
		# print(oddans)
else:
	for i in range(1, N-count+1,2):
		c = 1
		m = 1
		# print(i, end=':')

		for j in range(i):
			c*=(N-count-j)
			m*=(j+1)
		oddans += c/m
		# print(oddans)
print(int(evenans*oddans))

Submission status: Accepted

Solution code:
#Biscuits

N,P = list(map(int, input().split()))
A = list(map(int, input().split()))

#奇数の数
k = 0
for a in A:
    k += a%2
if ( k ==0 ):
    ans = (3-P)%2 * 2**N
else:
    ans = 2**(N-1)
print(ans)

Submission status: Accepted

Solution code:
import math


def nCm(n, m):
    return math.factorial(n) / (math.factorial(m) * (math.factorial(n - m)))


N, P = map(int, input().split())
A = map(int, input().split())
A = list(map(lambda X: X % 2, A))
OddNumber = A.count(1)
EvenNumber = len(A) - OddNumber
AllNumber = 2 ** len(A)

i = 2
OddCount = 0
while OddNumber >= i:
    OddCount += nCm(OddNumber, i)
    i += 2
ans = (1 + OddCount) * (2 ** EvenNumber)
if P == 0:
    print(int(ans))
else:
    ans = AllNumber - int(ans)
    print(int(ans))

Submission status: Accepted

Solution code:
def nCk(n, k):
    ans = 1
    i = 0
    while i < k:
        ans *= n - i
        i += 1
    i = 1
    while i <= k:
        ans /= i
        i += 1
    return ans

def main():
    [N, P] = map(int, raw_input().split())
    even = 0
    odd = 0
    A = map(int, raw_input().split())
    i = 0
    while i < N:
        if 0 == A[i] & 1:
            even += 1
        else:
            odd += 1
        i += 1
    i = P
    k = 0
    while i <= odd:
        k += nCk(odd, i)
        i += 2
    print((2 ** even) * k)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def a():
    # import math
    # import itertools
    import scipy.misc as scm

    n, p = map(int, input().split())
    A = [int(a)%2 for a in input().split()]
    odd = A.count(1)
    even = A.count(0)
    def combination(pick_from, pick_how_many):
        # return math.factorial(pick_from) / math.factorial(pick_how_many)
        # return len(list(itertools.combinations(range(pick_from), pick_how_many)))
        return scm.comb(pick_from, pick_how_many, 1)

    result = 0
    for o in range(0+p, odd+1, 2):
        for e in range(0, even+1):
            result += combination(even, e) * combination(odd, o)
    print(result)

a()

Submission status: Accepted

Solution code:
import itertools

n, p = map(int, input().split())
a = list(map(int, input().split()))

even = list(filter(lambda x: x%2 == 0, a))
odd = list(filter(lambda x: x%2, a))

fact = [0]
r = 1
for i in range(1, 100):
    r *= i
    fact.append(r)

def c(a, b):
    if a == b: return 1
    return fact[a] / (fact[a - b] * fact[b])
if p == 0:
    e = 2**len(even)
    r = 1
    for i in range(2, len(odd) + 1, 2):
        r += c(len(odd), i)
    print(int(r * e))

if p == 1:
    e = 2**len(even)
    r = 0
    for i in range(1, len(odd) + 1, 2):
        r += c(len(odd), i)
    print(int(r * e))

Submission status: Accepted

Solution code:
def main():
  N,P = map(int,input().split())
  n0 = 0
  n1 = 0
  for a in map(int,input().split()):
    if a%2 == 0:
      n0 += 1
    else:
      n1 += 1
  if P == 1 and n1 == 0:
    print(0)
    return
  print(2**(n0+max(n1-1,0)))

main()

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
A_list=map(int, input().split())
# N=7
# P=1
# A_list=[1,1,1,1,1,1,1]
count=len([A for A in A_list if int(A)%2==P])
if count==(N*(not P)):
    print((not P) * (2**N))
else:
    print(2**(N-1))