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:
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

n,p = map(int,input().split())
a = list(map(int,input().split()))
zero,one = 0,0
for i in range(n):
    if a[i]%2==1:
        one += 1
    else:
        zero += 1
res = 0
if p==0:
    for i in range(0,one+1,2):
        res += cmb(one,i)
else:
    for i in range(1,one+1,2):
        res += cmb(one,i)
res *= 2**zero
print(res)

Submission status: Accepted

Solution code:
def pascal(n):
    ret = [[] for _ in range(n+1)]
    for i in range(n+1):
        for j in range(i+1):
            if j == 0 or j == i:
                ret[i].append(1)
            else:
                ret[i].append(ret[i-1][j-1]+ret[i-1][j])
    return ret


N, P = map(int, input().split())
A = [int(x) for x in input().split()]
comb = pascal(N)
count = [0, 0]
for i in A:
    count[i % 2] += 1
ans = 0
if P == 0:
    for i in range(0, count[1]+1, 2):
        ans += comb[count[1]][i]
else:
    for i in range(1, count[1]+1, 2):
        ans += comb[count[1]][i]
ans = ans * (2**count[0])
print(ans)

Submission status: Accepted

Solution code:
import math
n,p = map(int,input().split())
a = list(map(int,input().split()))
ze = 0
on = 0
for i in range(n):
  if a[i] %2 == 0:
    ze+=1
  else:
    on += 1
con = 0
if p == 0:
  for i in range(0,on+1,2):
    con += math.factorial(on)//math.factorial(on-i)//math.factorial(i)
else:
  for i in range(1,on+1,2):
    con += math.factorial(on)//math.factorial(on-i)//math.factorial(i)
ans = (2**ze)*con
print(ans)

Submission status: Accepted

Solution code:
from math import factorial as f

n,p=map(int,input().split())
m=sum(map(lambda x:int(x)%2,input().split()))
o=n-m

a=2**o
b=0

if m:
  if p:
    for i in range(1,m+1,2):
      b+=f(m)//(f(m-i)*f(i))
  else:
    for i in range(0,m+1,2):
      b+=f(m)//(f(m-i)*f(i))
  print(a*b)
else:
  if p==0:
    print(a)
  else:
    print(0)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=list(map(int,input().split()))
odd=0
even=0
p=0
for i in s:
    if i%2==1:
        odd+=1
    else:
        even+=1
even=2**even
from math import factorial
def f(n,m):
    return factorial(n)//(factorial(n-m)*factorial(m))
for i in range(1,odd+1,2):
    p+=f(odd,i)
if m==1:
    print(p*even,)
else:
    print(2**(len(s))-p*even)

Submission status: Accepted

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

b0 = 0
b1 = 0

fib = [1]
num = 1
for i in range(1, n+1):
    num *= i
    fib.append(num)

def com(n, r):
    return fib[n] // fib[r] // fib[n - r]

for i in range(n):
    if a[i] % 2 == 0:
        b0 += 1
    else:
        b1 += 1

c0 = 0
c1 = 0

for i in range(b0+1):
    c0 += com(b0, i)

if p == 0:
    for i in range(b1+1):
        if i % 2 == 1:
            continue
        c1 += com(b1, i)
    print(c0 * c1)
else:
    for i in range(b1+1):
        if i % 2 == 0:
            continue
        c1 += com(b1, i)
    print(c0 * c1)

Submission status: Accepted

Solution code:
from collections import Counter

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

cnt = Counter([0, a[0]])

for ai in a[1:]:
    temp = Counter()
    for k, v in cnt.items():
        temp[k + ai] = v
        
    cnt += temp

ans = 0
for k, v in cnt.items():
    if k % 2 == p:
        ans += v
        
        
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

N, P = map(int, raw_input().split())
A = map(int, raw_input().split())
cnt = 0

for a in A:
    if a % 2 == 1:
        cnt += 1

m = {}
def comb(n, k):
    if (n, k) in m:
        return m[(n, k)]
    if n == k or k == 0:
        m[(n, k)] = 1
        return 1
    m[(n, k)] = comb(n - 1, k) + comb(n - 1, k - 1)
    return m[(n, k)]

ans = 0
rem = N - cnt
for i in range(0, cnt + 1, 2):
    ans += comb(cnt, i)
if P == 1:
    ans = 2 ** cnt - ans
print ans * (2 ** rem)

Submission status: Accepted

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

dp = [[0]*2 for _ in range(n+1)]
dp[0][0] = 1

for k in range(n):
    for i in range(2):
        dp[k+1][i] = dp[k][i] + dp[k][(i+a[k])%2]
print(dp[-1][p])

Submission status: Accepted

Solution code:
from collections import Counter
n,p=map(int,input().split())
a=Counter([int(i) % 2 for i in input().split()])

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

Submission status: Accepted

Solution code:
from sys import stdin

n, p = map(int, stdin.readline().split(' '))
a = map(int, stdin.readline().split(' '))

dp = [ range(n+1), range(n+1) ]
dp[p][n] = 1
dp[p^1][n] = 0
for i in xrange(n-1, -1, -1):
   for k in [0,1]: dp[k][i] = dp[k][i+1] + dp[(k+a[i])%2][i+1]

#print dp

res = dp[0][0]

print res

Submission status: Accepted

Solution code:
'''
2で割った余り == p
p:0
1を偶数個と0を任意の数
p:1
1を奇数個と0を任意の数
'''

def comb(n, r):
    ret = 1
    if (n == r) or (n == 0) or (r == 0):
        ret = 1
    else:
        for i in range(1, n + 1):
            ret *= i
        for i in range(1, r + 1):
            ret //= i
        for i in range(1, n - r + 1):
            ret //= i
##    print('comb', n, r, ret)
    return ret

if __name__ == '__main__':
    n, p = map(int, input().split())
    a = list(map(int, input().split()))
    a_mod2 = list(map(lambda x: x % 2, a))
    cnt_0 = a_mod2.count(0)
    cnt_1 = a_mod2.count(1)
    cnt_odd_1 = cnt_1 if cnt_1 % 2 == 1 else cnt_1 - 1
    cnt_even_1 = cnt_1 if cnt_1 % 2 == 0 else cnt_1 - 1

##    print('a', a)
##    print('a_mod2', a_mod2)
##    print('cnt_0', cnt_0)
##    print('cnt_1', cnt_1)
##    print('cnt_odd_1', cnt_odd_1)
##    print('cnt_even_1', cnt_even_1)

    ans = 0
    if p == 0:
        rng = list(range(0, cnt_even_1 + 1))[::2]
        for i in rng:
            ans += comb(cnt_1, i)
        ans *= (2 ** cnt_0)
    elif p == 1:
        rng = list(range(1, cnt_odd_1 + 1))[::2]
        for i in rng:
            ans += comb(cnt_1, i)
        ans *= (2 ** cnt_0)
    print(ans)

Submission status: Accepted

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


def main():
    n, p = list(map(int, input().split()))
    a = list(map(int, input().split()))
    odd_count = sum([1 for ai in a if ai % 2 == 1])

    # See:
    # https://www.youtube.com/watch?v=5usHNxVUzqk
    if odd_count == 0:
        if p == 0:
            print(2 ** n)
        else:
            print(0)
    else:
        print(2 ** (n - 1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
A = list(map(int, input().split()))
even = 0
for a in A:
	if a % 2 == 0:
		even += 1
if even == N:
	if P == 0:
		print(2 ** N)
	else:
		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()))
flag = True
for ele in a:
  if ele%2==1:
    flag = False
if flag:
  if p==1:
    print(0)
  else:
    print(2**n)
else:
  print(2**(n-1))

Submission status: Accepted

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

a = [int(x) for x in input().split()]

odd = 0
even = 1

for i in range(n):
    if a[i] % 2 == 0:
        odd, even = odd*2, even*2
    else:
        odd, even = odd+even, odd+even

if p == 0:
    print(even)
else:
    print(odd)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# A - Biscuits
# https://beta.atcoder.jp/contests/agc017/tasks/agc017_a

# A_Biscuits.py

import math

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

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

even_combi = 2 ** even

odd_combi = 0
m = int(odd/2)
#print("m:", m)
for i in range(m+1):
    if P == 0:
        odd_combi += math.factorial(odd) / (math.factorial(i*2) * math.factorial(odd-i*2))
    else:
        if odd-(i*2+1) > 0:
            odd_combi += math.factorial(odd) / (math.factorial(i*2+1) * math.factorial(odd-(i*2+1)))

#print(even_combi, odd_combi)
print(int(even_combi*odd_combi))

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
A = list(map(int, input().split()))
DP = []
for _ in range(N) :
    DP.append([0,0])
    
DP[0][0] += 1
DP[0][A[0]%2] += 1
for i in range(1,N) :
    for j in range(2) :
        DP[i][ (A[i]+j)%2 ] += DP[i-1][j]
        DP[i][j] += DP[i-1][j]
        
print(DP[N-1][P])

Submission status: Accepted

Solution code:
import math
n, p = map(int,raw_input().split())

arr = map(int,raw_input().split())

odd = 0
even = 0

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

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

def C(n, r):
	return P(n, r)//math.factorial(r)

oddnum = 0
for i in range(1,odd+1,2):
	oddnum += C(odd,i)

if p == 1:
	print oddnum * 2**even
else :
	print 2**n-(oddnum*2**even)

Submission status: Accepted

Solution code:
from math import factorial
N, P = map(int, input().split())
A = [int(i) for i in input().split()]
o = []
e = []

def c(n,r):
    a = 1
    for i in range(n-r+1,n+1):
        a *= i
    return a//factorial(r)
for a in A:
    if a % 2: o.append(a)
    else: e.append(a)
ans = 0
if P:
    for i in range(1, len(o) + 1):
        if not i % 2: continue
        ans += c(len(o), i)
        for j in range(1, len(e)+1):
            ans += c(len(e), j) * c(len(o), i)
else:
    ans += 1
    for i in range(1, len(e) + 1):
        ans += c(len(e), i)
    for i in range(1, len(o) + 1):
        if i % 2: continue
        ans += c(len(o), i)
        for j in range(1, len(e) + 1):
            ans += c(len(e), j) * c(len(o), i)
print(ans)

Submission status: Accepted

Solution code:
N, P = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]

Pw = [1]
for i in range(1, 51):
    Pw.append(Pw[-1] * i)

def C(n, m):
    return Pw[n] // Pw[n - m] // Pw[m]

odd = sum(x % 2 for x in A)
even = N - odd

r = 0
for i in range(0, odd + 1, 2):
    r += C(odd, i) * (2**even)

if P == 1:
    r = 2**N - r

print(r)

Submission status: Accepted

Solution code:
n, p = [int(_) for _ in input().split(' ')]
a = [int(x) % 2 == 0 for x in input().split(' ')]
if all(a):
    if p == 1:
        print(0)
    else:
        print(1 << n)
else:
    print(1 << (n - 1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,P = map(int,input().split(" "))
A = list(map(int,input().split(" ")))
B = [1,0]
for _ in range(N):
    a = A.pop()%2
    p,q = B
    B = [p+q,q+p] if a else [2*p,2*q]
print(B[P])

Submission status: Accepted

Solution code:
from math import factorial

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

#print(comb(3, 1))

n, p = map(int, input().split())
b = list(map(int, input().split()))
a = [b[i] % 2 for i in range(n)]
zero = a.count(0)
one = n - zero


if p == 0:
	if one == 0:
		print(2 ** zero)
	else:
		num = 1
		for i in range(2, one + 1, 2):
			num += comb(one, i)
		print(num * (2 ** zero))

else:
	if one == 0:
		print(0)
	else:
		num = 0
		for i in range(1, one + 1, 2):
			num += comb(one, i)
		print(num * (2 ** zero))

Submission status: Accepted

Solution code:
from math import factorial
N, P = map(int, input().split(' '))
biscuits = list(map(int, input().split(' ')))
bis_odd = len([i for i in biscuits if i % 2 != 0])
bis_even = len([i for i in biscuits if i % 2 == 0])

if bis_even == len(biscuits):
    if P == 0: print(2**N)
    else: print(0)
else:
    print(2**(N-1))

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
array = [int(x) for x in input().split()]

even = 0
odd = 0

for item in array:
    if item % 2 == 0:
        even += 1
    else:
        odd += 1

if even == n:
    if p == 0:
        print(2**n)
    else:
        print(0)
else:
    print(2**(n-1))

Submission status: Accepted

Solution code:
def a_biscuits(N, P, A):
    is_include_odd = False  # 数列Aの要素に奇数のものはあるか
    for k in A:
        if k % 2 == 1:
            is_include_odd = True
    # 枚数が奇数の袋kに注目し、残りN-1個の袋からいくつか袋を選ぶとする。
    # それらの袋の中の枚数の合計が奇数にせよ偶数にせよ、kを選ぶ選ばないで
    # 枚数の合計を奇数にも偶数にもできる。よって 2^(N-1) 通り。
    # 枚数が奇数の袋がない場合は、どのように袋を選んでも偶数にしかできない。
    if is_include_odd:
        ans = pow(2, N - 1)
    else:
        ans = pow(2, N) if P == 0 else 0
    return ans

N, P = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(a_biscuits(N, P, A))

Submission status: Accepted

Solution code:
def cc(Nb,j):
    ANS = 1
    for i in range(j):
        ANS = ANS * (Nb-i)/(i+1)
    return int(ANS)


def main():
    N, P = map(int, input().split())
    A = list(map(int, input().split()))
    Na = 0
    Nb = 0
    for i in range(N):
        if A[i]%2 == 0:
            Na += 1
        else:
            Nb += 1
    if P==0:
        S = 0
        if Nb==0:
            return 2**Na
        for j in range(0,Nb+1,2):
            S += cc(Nb,j)
        return (2**Na) * S
    else:
        S=0
        if Nb==0:
            return 0
        for j in range(1,Nb+1,2):
            S += cc(Nb,j)
        return (2**Na) * S


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
a=list(map(int,input().split()))
odd_cnt=0
for i in range(n):
    if a[i]%2==1:
        odd_cnt=1
if odd_cnt==0:#全て偶数
    if p==0:
        print(2**n)
    else:
        print(0)
else:
    print(2**(n-1))

Submission status: Accepted

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


def biscuits():
    dp = [[[0 for i in range(2)] for j in range(n+1)] for i in range(n+1)]

    for i in range(n+1):
        dp[i][0][0] = 1

    for i in range(1, n+1):
        for j in range(i+1):
            for k in range(2):
                if j > 0:
                    dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-a[i-1] % 2]
                else:
                    dp[i][j][k] = dp[i-1][j][k]

    ans = 0
    for j in range(n+1):
        ans += dp[n][j][p % 2]

    return ans


def main():
    print(biscuits())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import factorial as f

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

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

even_choice = 2**num_even

def c(n, k):
    return f(n)//(f(k)*f(n-k))

odd_choice = 0
for i in range(0, num_odd+1):
    if i % 2 == P:
        odd_choice += c(num_odd, i)

print(even_choice*odd_choice)

Submission status: Accepted

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

if all(a%2==0 for a in src):
    if P:
        print(0)
    else:
        print(2**N)
    exit()
print(2**(N-1))

Submission status: Accepted

Solution code:
N,P = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

is_include_odd = False
for k in A:
  if k % 2 == 1:
    is_include_odd = True
    
if is_include_odd:
  print(pow(2,N-1))
else:
  if P == 0:
    print(pow(2,N))
  else:
    print(0)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
a = list(map(int, input().split()))
    
odd = 0
for num in a:
    if(num % 2 == 1):
        odd += 1
if(odd == 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())
N=list(input().split())
for i in range (len(N)):
    N[i]=int(N[i])%2
count1=N.count(1)
count0=N.count(0)
if count1<1 and P==1:
    print (0)
    sys.exit()
if count0==0 and count1<2 and P==0:
    print (0)
    sys.exit()
import math
count0_c=0
count1_c=0
if count0!=0:
    for k in range (0,count0+1):
        count0_c+=math.factorial(count0)/(math.factorial(k)*math.factorial(count0-k))
else:
    count0_c=1

if count1!=0:
    for j in range (0,count1//2+1-P):
        count1_c+=math.factorial(count1)/(math.factorial(2*j+P)*math.factorial(count1-2*j-P))
else:
    count1_c=1
print(int(count0_c*count1_c))

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
a=list(map(int,input().split()))
judge=True
for i in range(n):
    if a[i]%2!=0:
        judge=False
if judge==True:
    if p==0:
        print(2**n)
    else:
        print(0)
else:
    print(2**(n-1))

Submission status: Accepted

Solution code:
def read():
    return int(input())


def readlist():
    return list(map(int, input().split()))


def readmap():
    return map(int, input().split())


N, P = readmap()
A = readlist()

for i in range(N):
    A[i] = A[i] % 2

cnt_0 = A.count(0)
cnt_1 = A.count(1)


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


def nCr(n,r):
    return fact(n)/(fact(r)*fact(n-r))


if P == 0:
    ans = 2 ** cnt_0
    num = 0
    for i in range(cnt_1 // 2 + 1):
        num += nCr(cnt_1, 2*i)
    ans *= num
    print(int(ans))
else:
    ans = 2 ** cnt_0
    num = 0
    for i in range((cnt_1 - 1) // 2 + 1):
        num += nCr(cnt_1, 2 * i + 1)
    ans *= num
    print(int(ans))

Submission status: Accepted

Solution code:
tmp = list(map(int,input().split()))
As = list(map(int,input().split()))
n,p = tmp[0],tmp[1]
o ,e  = 0,0
for i in range(n):
  if As[i] % 2:
    o += 1
  else:
    e += 1
def comb(j,k):
  if k == 0:
    return(1)
  else:
    return comb(j-1,k-1) * j / k
ans = 0
if p == 0:
  for i in range(o+1):
    if not i % 2:
      ans += int(comb(o,i))
else:
  for i in range(o+1):
    if i % 2:
      ans += int(comb(o,i))
ans *= (2 ** e)
print(ans)

Submission status: Accepted

Solution code:
import math

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

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

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

ans = 0

odd = len(list(filter(lambda x:x%2==1,A)))
even = len(list(filter(lambda x:x%2==0,A)))

i = 0 if P==0 else 1
while(i<=odd):
    ans += C(odd,i)
    i+=2
    
for i in range(even):
    ans *= 2

print(ans)

Submission status: Accepted

Solution code:
n, p = list(map(int,input().split()))
a = list(map(int,input().split()))
count = 0
for i in range(n):
    if a[i]%2 == 1:
        count =1
        break

if count == 1:
    print(2**(n-1))
else:
    if p == 0:
        print(2**n)
    else:
        print(0)

Submission status: Accepted

Solution code:
N,P=map(int,input().split())
A=[int(x) for x in input().split()]
e=0
o=0
for i in range(N):
  if A[i]%2==0:
    e+=1
  else:
    o+=1 

#階乗計算
factorial=[1]
for i in range(1,N+1):
    factorial.append(factorial[i-1]*i)
    
def nCr(n,r):
  return int(factorial[n]/(factorial[r]*factorial[n-r]))
  
ans=0
for i in range(1,o+1):
  if i%2==1:
    cnt=nCr(o,i)
    for j in range(0,e+1):
      ans+=cnt*(nCr(e,j))
if P==1:
  print(ans)
else:
  ans=(1<<N)-ans
  print(ans)

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
a=list(map(int,input().split()))
if all(elem %2==0 for elem in a):
    if p==0:
        print(2**n)
    else:
        print(0)
else:
    print(2**(n-1))

Submission status: Accepted

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

    editorial(N, P, A)

def editorial(N, P, A):
    odds = [a for a in A if a % 2 == 1]
    odd = len(odds)
    even = N - odd

    if odd == 0:
        if P == 1:
            print(0)
        else:
            print(2 ** N)
        return
    
    # ある奇数袋を取り除いて、残りでの組み合わせ(選ぶ選ばないの2通りがN-1)
    ans = 2 ** (N - 1)
    # s = 組み合わせのビスケット枚数
    # P=0,s:奇数であるとき、加えるのは1通り
    # P=0,s:奇数でないとき、加えないのは1通り
    # P=1,s:奇数であるとき、加えないのは１通り
    # P=1,s:奇数でないとき、加えるのは1通り
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

if all(map(lambda x: x % 2 == 0, A)):
    if P == 0:
        print(2**N)
    else:
        print(0)
else:
    print(2**(N-1))

Submission status: Accepted

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

    odd = sum(a % 2 for a in A)
    even = N - odd
    o, e = 0, 0
    # 奇数枚の袋の選び方
    # P=0: 奇数個含まれる袋から足して２の倍数になる袋の組合せ(袋0でもよい)
    # P=1: 奇数なので奇数枚の袋を奇数個
    for i in range(P, odd+1, 2):
        o += ncr(odd, i)

    for i in range(even+1):
        e += ncr(even, i)
    ans = o * e

    print(ans)


def _factorial(n):
    if n < 0:
        raise ValueError("factorial() not defined for negative values")
    a = 1
    for i in range(1, n + 1):
        a *= i
    return a


def npr(n, r):
    if n < r:
        return 0
    a = 1
    for i in range(r):
        a *= n - i
    return a


def ncr(n, r):
    _npr = npr(n, r)
    if _npr == 0:
        return 0
    return _npr // _factorial(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


n,p=map(int,input().split())
a=list(map(int,input().split()))
c=0
for i in a:
    if(i%2!=0):
        c+=1
if(c==0):
    if(p==0):print(2**n)
    else:print(0)
else:
    print(2**(n-1))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys, math, copy
# import fractions, itertools
# import numpy as np
# import scipy

HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

def fact(i):
    res = 1
    for j in range(1, i + 1):
        res *= j
    return res

def combi(n, i):
    assert 0 <= i <= n
    return fact(n) // (fact(i) * fact(n - i))

def main():
    n, p = map(int, input().split())
    ai = list(map(int, input().split()))
    assert len(ai) == n

    evens = 0
    odds = 0
    for a in ai:
        if a % 2 == 0:
            evens += 1
        else:
            odds += 1
    way_evens = 2 ** evens
    way_odds = 0
    for no in range(p, odds + 1, 2):
        way_odds += combi(odds, no)

    print(way_evens * way_odds)

main()

Submission status: Accepted

Solution code:
from math import factorial
n,p = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
x = 0
for i in a:
	if i%2==0: x+=1
y = n-x
if p==0:
	num,fy = 0,factorial(y)
	for i in range(0,y+1,2):
		num += fy//(factorial(i)*factorial(y-i))
	print((2**x)*num)
else:
	num,fy = 0,factorial(y)
	for i in range(1,y+1,2):
		num += fy//(factorial(i)*factorial(y-i))
	print((2**x)*num)

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
N,P=map(int,input().split())
nums = list(map(int,input().split()))
even,odd = 0,0
for num in nums:
  if num%2 == 0:
    even +=1
  else:
    odd +=1
if odd == 0:
  if P == 1:
    print(0)
  else:
    print(2**even)
else:
  print((2**even)*(2**odd)//2)

Submission status: Accepted

Solution code:
'''
方針：各Aiをそれぞれ見て、いくつ偶数があっていくつ奇数があるかを数える。
以下偶数がX個、奇数がY個あるとする。(X+Y=N,0≦X,Y)
そしてこの問題は偶数の集合の中からの選ぶことと奇数の集合の中から選ぶことを独立に考えることができる。
よって（偶数の集合からの選び方）×（奇数の集合からの選び方）で求めることができる。
（偶数の集合からの選び方）については、どのように選んでも全体の合計を2で割った余りは変わらないので全事象を考えることができる。
よって2^Xである。
（奇数の集合からの選び方）についてはY個のうちk個（k≡P mod 2）である場合の数の合計なので
Σ[k:0→Y and k≡P mod 2]C(Y,k)である。
ただし、C(Y,k)は二項係数を表していて、Σ[k:0→Y and k≡P mod 2]は0≦k≦Nかつk≡P mod 2であるものすべてを足し合わせたという意味である。
'''
def C(n,m):
    S=1
    for i in range(1,n+1):
        S=S*i
    for i in range(1,m+1):
        S=S//i
    for i in range(1,n-m+1):
        S=S//i
    return S
N,P=map(int,input().split())
A=[int(i) for i in input().split()]
X=0;Y=0
#X:偶数
#Y:奇数
for i in range(N):
    if A[i]%2==0:
        X+=1
    else:
        Y+=1
Z=0
for i in range(Y+1):
    if i%2==P:
        Z+=C(Y,i)
print(Z*2**(X))

Submission status: Accepted

Solution code:
def C(n,m):
    S=1
    for i in range(1,n+1):
        S=S*i
    for i in range(1,m+1):
        S=S//i
    for i in range(1,n-m+1):
        S=S//i
    return S
N,P=map(int,input().split())
A=[int(i) for i in input().split()]
X=0;Y=0
#X:偶数
#Y:奇数
for i in range(N):
    if A[i]%2==0:
        X+=1
    else:
        Y+=1
Z=0
for i in range(Y+1):
    if i%2==P:
        Z+=C(Y,i)
print(Z*2**(X))

Submission status: Accepted

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

if any(map(lambda x: x % 2 == 1, A)):
    print(2**(N-1))
else:
    if P == 0:
        print(2**N)
    else:
        print(0)

Submission status: Accepted

Solution code:
def combination(total, selected):
    foo = 1
    for i in xrange(selected):
        foo *= total-i
        foo /= i+1
    return foo

def process(a, p):
    odds = 0
    even = 0
    for x in a:
        if (x%2)==0:
            even += 1
        else:
            odds += 1
    foo = 0
    for i in xrange(p, odds+1, 2):
        foo += combination(odds, i)
    foo *= 1<<even
    return foo

def main():
    n, p = [int(x) for x in raw_input().strip().split()]
    a = [int(x) for x in raw_input().strip().split()]
    print process(a, p)

if __name__ == '__main__':
    main()

Submission status: Accepted

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


for i in range(len(A)):
	A[i] = A[i] % 2

num1 = A.count(1)
num0 = A.count(0)

if P == 0:
	if num1 <= 1:
		print(2 ** (num0))
	else:
		print(2 ** (num0 + num1 - 1))
else:
	if num1 == 0:
		print(0)
	else:
		print(2 ** (num0 + num1 - 1))

Submission status: Accepted

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

C = {(0,0):1}
def comb(n,k):
    if n == 0 or k == 0 or k == n:
        return 1
    else:
        if (n,k) in C:
            return C[(n,k)]
        else:
            C[(n,k)] = comb(n-1,k) + comb(n-1,k-1)
            return C[(n,k)]
m = 0
if P == 0:
    for i in range(0,odd+1,2):
        m += int(comb(odd,i))
else:
    for i in range(1,odd+1,2):
        m += int(comb(odd,i))
print(m*(2**even))

Submission status: Accepted

Solution code:
def cmb(n, k):
  s = 1
  for j in range(n - k + 1, n + 1, 1):
    s *= j
  for j in range(1, k+1):
    s //= j
  return s

n, p = map(int, input().split())
aa = list(map(lambda x: int(x) % 2, input().split()))
odd = sum(aa)
even = n - odd
if p == 0:
  c = 2**even * sum(cmb(odd, k) for k in range(0, odd+1, 2))
  print(c)
else:
  c = 2**even * sum(cmb(odd, k) for k in range(1, odd+1, 2))
  print(c)

Submission status: Accepted

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

s = 1; t = 0
for a in A:
    if a % 2:
        s, t = s+t, s+t
    else:
        s, t = 2*s, 2*t
print([s, t][P])

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
a=list(map(lambda x: x%2, map(int,input().split())))
e=a.count(0)

ans=2**(n-1)
if p==1 and e==n:
    ans=0
if p==0 and e==n:
    ans=2**n
print(ans)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
a = list(map(lambda x: x & 1, map(int, input().split())))

b, c = a.count(1), a.count(0)
d = 2 ** b // 2  * 2 ** c 
if p == 1:
    print(d)
else:
    print(2 ** n - d)

Submission status: Accepted

Solution code:
N, P = map(int,input().split())
bis = list(map(int, input().split()))
if P == 0:
    ans = 2 ** N
else:
    ans = 0

for i in range(N):
    if bis[i] % 2 == 1:
        ans = 2 ** (N-1)
        break
print(ans)

Submission status: Accepted

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

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

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

temp1 = 0
for e in range(even + 1):
    temp1 += nCr(even, e)

temp2 = 0
if P == 0:
    for o in range(odd + 1):
        if o % 2 == 0:
            temp2 += nCr(odd, o)
else:
    for o in range(odd + 1):
        if o % 2 != 0:
            temp2 += nCr(odd, o)
ans = temp1 * temp2
print(ans)

Submission status: Accepted

Solution code:
import math

def fact(x):
    return math.factorial(x)

N, P = map(int, raw_input().split())
A = map(int, raw_input().split())
ec = sum(map(lambda n: 1 - (n & 1), A))
oc = sum(map(lambda n: (n & 1), A))
ocv = [i for i in range(oc + 1)]
ocv = map(lambda n: fact(oc) / (fact(n) * fact(oc - n)), ocv)
print pow(2, ec) * sum(ocv[P::2])

Submission status: Accepted

Solution code:
import itertools

N, P = [int(i) for i in input().split()]
biscuits = [int(i) for i in input().split()]
even = 0
odd = 0
buffer_count = 1
even_c = 1

for i in biscuits:
    if i % 2 == 0:
        even += 1
    elif i % 2 == 1:
        odd += 1

if P == 0:
    # even
    odd_c = 1
elif P == 1:
    # odd
    odd_c = 0

if even > odd:
    for i in range(1, even+1):
        even_c += 2 ** (i-1)
        if i == odd:
            buffer_count = even_c
elif odd >= even:
    for i in range(1, odd+1):
        buffer_count += 2 ** (i-1)
        if i == even:
            even_c = buffer_count

if P == 0:
    # even
    if buffer_count > 2:
        odd_c = (buffer_count / 2)
elif P == 1:
    # odd
    if buffer_count > 1:
        odd_c = (buffer_count / 2)

print(int(even_c * odd_c))