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:
import math

if __name__ == '__main__':
    N, P = list(map(int, input().split()))
    A = list(map(int, input().split()))
    zero_or_one = [(i % 2) for i in A]

    count_zero = zero_or_one.count(0)
    count_one = zero_or_one.count(1)

    if P == 0:
        sum_combination_zero = 0
        for i in range(0, count_zero + 1):
            sum_combination_zero += math.factorial(count_zero) / (math.factorial(i) * math.factorial(count_zero - i))

        sum_combination_one = 0
        for i in range(0, count_one + 1, 2):
            sum_combination_one += math.factorial(count_one) / (math.factorial(i) * math.factorial(count_one - i))

        ans = sum_combination_zero * sum_combination_one
        print(int(ans))
    else:
        sum_combination_zero = 0
        for i in range(0, count_zero + 1):
            sum_combination_zero += math.factorial(count_zero) / (math.factorial(i) * math.factorial(count_zero - i))

        sum_combination_one = 0
        for i in range(1, count_one + 1, 2):
            sum_combination_one += math.factorial(count_one) / (math.factorial(i) * math.factorial(count_one - i))

        ans = sum_combination_zero * sum_combination_one
        print(int(ans))

Submission status: Accepted

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

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

def f(n,r):
    res= 1
    for i in range(n-r+1 ,n+1):
        res *=  i
    for i in range(1,r+1):
        res //=i
    #print(n,r,res)
    return int(res)



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

even = N-odd

if P==1:
    if odd==0:
        print(0)
        exit()
    ans = 2**even
    tmp = 0
    for i in range(1, odd + 1, 2):
        tmp += f(odd, i)
        #print(tmp)
    print(ans * tmp)
else:
    ans = 2 ** even
    tmp=0
    for i in range(0, odd+1, 2):
        tmp += f(odd, i)
        #print(tmp)
    print(ans*tmp)

Submission status: Accepted

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

f = [1]
for n in range(1, N+2):
    f.append(f[-1] * n)

def ncr(n,r):
    return f[n] // f[n-r] // f[r]

oddc = 0
for i in range(odd+1):
    if i%2 != P : continue
    oddc += ncr(odd,i)

print (pow(2,even) * oddc)

Submission status: Accepted

Solution code:
import math


def ncr(n, r):
    f = math.factorial
    return f(n) // f(r) // f(n - r)

n, p = [int(i) for i in input().split()]
nbiss = [int(i) for i in input().split()]
ret = 0
num = [0, 0]
for x in nbiss:
    num[x % 2] += 1
if p > num[1]:
    print(0)
else:
    for i in range(p, num[1]+1, 2):
        ret += ncr(num[1], i)
    ret *= (2 ** num[0])
    print(ret)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

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

def com(n, k):
    if n == 0 or k == 0 or n == k:
        return 1
    return int(reduce(mul, range(1, n + 1)) / (reduce(mul, range(1, k + 1)) * reduce(mul, range(1, n - k + 1))))


odd_num = 0
for a_i in a:
    if a_i % 2 == 1:
        odd_num += 1

ans_odd = 0
for i in range(1, odd_num + 1, 2):
    ans_odd += com(odd_num, i)

ans_odd *= 2**(N - odd_num)
if P == 1:
    print(ans_odd)
else:
    print(2**N - ans_odd)

Submission status: Accepted

Solution code:
import numpy as np
import math

def comb(n, k):
    if k<0 or n<k:
        return 0
    return round(math.factorial(n)/math.factorial(k)/math.factorial(n-k))

N,P=[int(_) for _ in input().split()]
a=np.array([int(_) for _ in input().split()])


retVal=0
if P==0:
    retVal+=1
    
even=0
for i in range(N):
    if a[i]%2==0:
        even+=1
odd=N-even

for k in range(1, N+1):        
    i=(P+k)%2    
    while i<=min(even,k):
        retVal+=comb(even, i)*comb(odd,k-i)
        i+=2        
print(retVal)

Submission status: Accepted

Solution code:
N,mod=map(int,raw_input().split())
packs=map(int,raw_input().split())
odd=0
even=0

def nCk(n,k):
    result=1
    for i in range(n-k+1,n+1):
        result*=i
    for i in range(1,k+1):
        result/=i
    return result

for i in packs:
    if i%2==1:
        odd+=1
    else:
        even+=1

base=(2**even)
result=0
if mod==1:
    for i in range(1,odd+1,2):
        result+=base*nCk(odd,i)
elif mod==0:
    for i in range(0,odd+1,2):
        result+=base*nCk(odd,i)
print result

Submission status: Accepted

Solution code:
def combination(n, k):
    result = 1
    for i in xrange(1,n+1):
        result*=i
    for i in xrange(1,k+1):
        result/=i
    for i in xrange(1,n-k+1):
        result/=i
    return result

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

even = len([i for i in a if i % 2 == 0])
odd = len(a) - even

fact_even = 0
for k in xrange(0,even+1):
    fact_even+=combination(even,k)

fact_odd = 0
for k in xrange(p,odd+1,2):
    fact_odd+=combination(odd,k)

print fact_even * fact_odd

Submission status: Accepted

Solution code:
s = input().split()
N = int(s[0])
P = int(s[1])
s = input().split()
a = [int(i) for i in s]

import itertools
import math
import scipy.misc as scm

#あまりはあまりの和なので、各袋の2で割ったあまりを求める
b = [i % 2 for i in a]   #0 or 1の配列になる
zeros = b.count(0)
ones = b.count(1)

if P == 0 : 
    ## P == 0 の時は何も選ばないが１通りあるのでそれを加える
    #0になる組み合わせの数  zerosC0 + zerosC1 zerosC2 + ... zerosCzeros = 2^zeros
    #2になる組み合わせの数 onesC2 * 2^zeros
    #4になる組み合わせの数 onesC4 * 2^zeros
    lim = math.floor(ones / 2)
    cnt = 0
    for i in range(lim + 1) : 
        onesCx = scm.comb(ones , 2 * i , 1) * 2**zeros
        cnt += onesCx

else : 
    ## P == 1の時
    #1になる組み合わせは onesC1 * 2^zeros
    #3になる組み合わせは onesC3 * 2^zeros
    lim = math.floor(ones / 2)
    cnt = 0
    for i in range(lim + 1) : 
        onesCx = scm.comb(ones , 2 * i + 1 , 1) * 2**zeros
        cnt += onesCx

print(cnt)

Submission status: Accepted

Solution code:
#! /usr/bin/env python3
import itertools
import math
N, P = map(int, input().split())
A = list(map(int, input().split()))
cnt = 0
for i in A:
    if i % 2 : cnt += 1
_cnt = len(A) - cnt
if P == 0:
    a = 0
    for i in range(0, cnt + 1, 2):
        a += (math.factorial(cnt) // math.factorial(cnt-i)) // math.factorial(i)
    print(2 ** _cnt * a)
else:
    a = 0
    for i in range(1, cnt + 1, 2):
        a += (math.factorial(cnt) // math.factorial(cnt-i)) // math.factorial(i)
    print(2 ** _cnt * a)

Submission status: Accepted

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

a = [x for x in A if x % 2 == 1]
b = [x for x in A if x % 2 == 0]
x = len(a)
y = len(b)
z = x // 2
w = (x + 1) // 2
S = 0
T = 0

if P == 0:
	for k in range(z+1):
		s = factorial(x) // (factorial(x-2*k) * factorial(2*k))
		S += s
	for k in range(y+1):
		t = factorial(y) // (factorial(y-k) * factorial(k))
		T += t
	U = S * T
	print(U)
else:
	for k in range(w):
		s = factorial(x) // (factorial(x-2*k-1) * factorial(2*k+1))
		S += s
	for k in range(y+1):
		t = factorial(y) // (factorial(y-k) * factorial(k))
		T += t
	U = S * T
	print(U)

Submission status: Accepted

Solution code:
import math as ma

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

e = 0
for ai in a:
  if ai % 2 == 0:
    e += 1

o = len(a) - e
ans = 0


nck = {(o,0): 1}
for k in range(0, o+1):
  nck[(o,k+1)] = nck[(o,k)] * (o-k) / (k+1)

if p % 2 == 0:
  ans = 2 ** e
  if o >= 2:
    t = 0
    for k in range(0, o+1, 2):
      t += nck[(o,k)]
    ans *= t
  print ans

else:
  if o >= 1:
    t = 0
    for k in range(1, o+1, 2):
      t += nck[(o,k)]
    print t * (2 ** e)
  else:
    print 0

Submission status: Accepted

Solution code:
import math

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


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

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

ans = 0


if P == 0:
    k = 0
    for i in range(0, odd+1):
        if i%2==1 :
            continue
        elif i > odd:
            break
        k += nCm(odd, i)
    ans = (2**even)*k
        
else:
    k = 0
    for i in range(1, odd+1):
        if i%2==0 :
            continue
        elif i > odd:
            break
        k += nCm(odd, i)
    ans = (2**even)*k
print(int(ans))

Submission status: Accepted

Solution code:
# ------ combination -------
N, MOD = 10**5 + 1, 10**9 + 7
fc, ifc = [0] * (N+1), [0] * (N+1)

def power(n, a):
    res, exp = 1, n
    while(a):
        if a & 1:
            res = res * exp % MOD
        exp = exp * exp % MOD
        a = a >> 1
    return res

fc[0] = 1
for i in range(1, N+1):
    fc[i] = fc[i-1] * i % MOD
ifc[N] = power(fc[N], MOD-2)
for i in range(N-1, -1, -1):
    ifc[i] = ifc[i+1] * (i+1) % MOD

def Comb(n, r):
    if n < 0 or r < 0 or n < r:
        return 0
    return fc[n] * ifc[r] % MOD * ifc[n-r] % MOD

# --------------------------

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

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

ans = 0
for i in range(1, odd + 1, 2):
    ans += (Comb(odd, i) * (2**(N-odd)))

if P == 0:
    ans = 2**N - ans
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import scipy.misc as scm
hoge = input()
hoge = list(map(int,hoge.split(" ")))
N = hoge[0]
P = hoge[1]
A = input()
A = list(map(int,A.split(" ")))
A = np.array(A)

odd = len(A[A %2 == 1])
even = N -odd
perm = 0
if P == 0:
    for i in range(0,odd+1,2):
        perm +=scm.comb(odd,i,1)
else:
    for i in range(1,odd+1,2):
            perm +=scm.comb(odd,i,1)
ans = 2**even * perm
print(ans)

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:
# encoding:utf-8
import math

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

	n_odd = sum([x % 2 for x in biscuits])
	n_even = N - n_odd

	out = calcNPtrn_odd(n_odd, P) * calcNPtrn_even(n_even)
	print(out)
	
def calcComb(n, m):
	return(math.factorial(n)/math.factorial(m)/math.factorial(n-m))

def calcNPtrn_odd(n, is_odd):
	if n == 0:
		if is_odd == 1:
			return(0)
		else:
			return(1)

	count = 0
	if is_odd == 1:
		for i in range(1, n + 1, 2):
			count += calcComb(n, i)
	else:
		for i in range(0, n + 1, 2):
			count += calcComb(n, i)

	return(int(count))

def calcNPtrn_even(n):
	if n == 0:
		return(1)

	count = 1
	for i in range(1, n + 1):
		count += calcComb(n, i)
	return(int(count))

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def ncr(n, r):
	s = 1
	for i in range(n - r + 1, n + 1):
		s = s * i / (i - (n - r))
	return s

a, b = map(int, raw_input().split())
l = map(int, raw_input().split())

c1 = len([i for i in l if i % 2 == 1])
c2 = len([i for i in l if i % 2 == 0])
s1 = 0
s2 = 0

for i in range(c1 + 1):
	if i % 2 == 0:
		s2 += ncr(c1, i)
	else:
		s1 += ncr(c1, i)

s3 = 2 ** c2

if b == 1:
	print s1 * s3
else:
	print s2 * s3

Submission status: Accepted

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

#N = 3
#P = 0
#A = [1, 1, 1]
#N = 45
#P = 0
#A = [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]

A = [i%2 for i in A]

if(A[0]==0 and P==0):
    dp = 2
elif(A[0]==0 and P==1):
    dp = 0
elif(A[0]==1 and P==0):
    dp = 1
else:
    dp = 1

for i in range(N-1):
    if(A[i+1]==0):
        dp = 2*dp
    else:
        dp = 2**(i+1)
print(dp)

Submission status: Accepted

Solution code:
(N,P) = map(int, raw_input().split())
A = map(int, raw_input().split())
n_even = 0
m_odd = 0
for i in range(N):
	if A[i] % 2==0:
		n_even += 1
	else:
		m_odd += 1
N = 2**n_even
def calC(a,b):
	l1 = 1
	l2 = 1
	l3 = 1
	for i in range(a):
		l1 *= (i+1)
	for i in range(b):
		l2 *= (i+1)
	for i in range(a-b):
		l3 *= (i+1)
	return l1/l2/l3
M = 0
i = 0	
while i*2+P <= m_odd:
	M += calC(m_odd, i*2+P)
	i += 1

print N*M

Submission status: Accepted

Solution code:
import math
L=raw_input().split()
L1=[int(i) for i in L]
LA=raw_input().split()
L2=[int(i) for i in LA]
e=o=ans=0
for i in L2: 
	if i%2: o+=1
	else: e+=1
if L1[1]==0:
	for i in range(0,o+1,2):
		ans+=(math.factorial(o)/(math.factorial(i)*math.factorial(o-i)))
	print ans*(1<<e)
else:
	for i in range(1,o+1,2):
		ans+=(math.factorial(o)/(math.factorial(i)*math.factorial(o-i)))
	print ans*(1<<e)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
even = 0
odd = 0
l = list(map(int, input().split()))
for i in l:
    if i%2 == 0: even+=1
    else: odd+=1

ans = 0
if p == 1 and odd == 0:
    print(ans)
elif p == 0 and even == 0 and odd < 2:
    print(ans)
else:
    f = [1 for i in range(51)]
    f[0] = 1
    f[1] = 1
    for i in range(2, 51):
        f[i] = i*f[i-1]
    partieO = [1 for i in range(51)]
    partieE = [1 for i in range(51)]
    partieO[0] = 1
    partieE[0] = 1
    for i in range(1, odd+1):
        partieO[i] = f[odd]/(f[i]*f[odd-i])
    for i in range(1, even+1):
        partieE[i] = f[even]/(f[i]*f[even-i])
    if p == 0:
        t = 0
        for i in range(even+1):
            for j in range(0, odd+1, 2):
                t += partieE[i]*partieO[j]
        print(int(t))
    else:
        t = 0
        for i in range(even+1):
            for j in range(1, odd+1, 2):
                t += partieE[i]*partieO[j]
        print(int(t))

Submission status: Accepted

Solution code:

def ncr(n, r):
	return fact[n] // (fact[r] * fact[n-r]);


fact = [0 for x in range(100)];

fact[0] = 1
for i in range(1, 60):
	fact[i] = i * fact[i-1]

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

x = 0
y = 0

arr = list(map(int, input().split()))

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

if (p == 0):
	i = 0
else:
	i = 1

ans = 0
while i <= y:
	ans += ncr(y, i)
	i += 2
print(ans * (2 ** x))

Submission status: Accepted

Solution code:
s = raw_input().split()
n = int(s[0])
p = int(s[1])
s = raw_input().split()

ans = 0
cnt = [0, 0]

def f(b, e):
	c = 1
	while e:
		if e%2:
			c = (c*b)
		e /= 2
		b = (b*b)
	return c

for i in range(n):
	j = int(s[i])
	cnt[j%2] += 1

if p == 0:
	if cnt[1] == 0:
		ans = f(2, cnt[0])
	else:
		ans = f(2, n-1);
else:
	if cnt[1] != 0:
		ans = f(2, n-1)

print ans

Submission status: Accepted

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N, P = ILI()
    A = ILI()
    return N, P, A


def nCr(n, r):
    if r == 0:
        return 1

    return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))


def solve(N, P, A):
    n_even = 0
    n_odd = 0
    for a in A:
        if a % 2 == 1:
            n_odd += 1
        else:
            n_even += 1

    ans = 0
    if P == 0:
        sum_even = 2 ** n_even
        n_odd_div = n_odd // 2
        sum_odd = 0
        for i in range(0, n_odd_div + 1):
            sum_odd += nCr(n_odd, i * 2)
        ans = sum_even * sum_odd

    elif P == 1:
        if n_odd == 0:
            ans = 0
        else:
            sum_even = 2 ** n_even
            n_odd_div = n_odd // 2
            sum_odd = 0
            for i in range(n_odd_div):
                sum_odd += nCr(n_odd, i * 2 + 1)
            ans = sum_even * sum_odd

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
def fr(i):
    s = 1
    for j in range(i+1):
        s*=j
    return s

def f():
    n,p = list(map(int,input().split(" ")))
    a = list(map(int,input().split(" ")))
    a.sort()
    m0 = 0
    m1 = 0
    for i in a:
        if i%2==0:
            m0 += 1
        else:
            m1 += 1
    s = 0
    if p==0:
        
        
        for i in range(0,m1+1,2):
            s_ = (2**m0)
            
            for j in range(0,i):
                s_ *= m1-j
            for j in range(1,i+1):
                s_ /= j
            s += s_
    if p==1:
        if m1 == 0:
            print("0")
            return
        s = 0
        for i in range(1,m1+1,2):
            s_ = (2**m0)
            for j in range(0,i):
                s_ *= m1-j
            for j in range(1,i+1):
                s_ /= j
            s += s_
    print(int(s))

f()

Submission status: Accepted

Solution code:
import math
f = math.factorial
def comb(n,k):
    return f(n)//(f(n-k) * f(k))

N, P = map(int, input().split())
a = list(map(int, input().split()))
ma = [e % 2 for e in a]
nOdd = ma.count(1)
nEven = N - nOdd

ce = 0    
for i in range(nEven + 1):
    ce += comb(nEven, i)

co = 0
for i in range(nOdd + 1):
    if i % 2 == P:
        co += comb(nOdd, i)

print(ce * co)

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import itertools

N,P = map(int, sys.stdin.readline().rstrip().split())
As = list(map(int, sys.stdin.readline().rstrip().split()))

odds = sum(item % 2 == 1 for item in As)
evens = N - odds

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

count = 0
for j in range(P, odds+1, 2): # 奇数を何個とるか
    for k in range(evens+1): # 偶数を何個とるか
        count += comb(odds, j) * comb(evens, k)
print(int(count))

exit(0)

Submission status: Accepted

Solution code:
n, p = map(int, raw_input().split())
a = map(int, raw_input().split())
dp = [[0]*5500 for _ in xrange(n + 1)]
dp[0][0] = 1
for i in xrange(n):
    for j in xrange(5001):
        dp[i + 1][j + a[i]] += dp[i][j]
        dp[i + 1][j] += dp[i][j]
ans = 0
for j in xrange(5001):
    if j % 2 == p:
        ans += dp[n][j]
print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__ import division, print_function
from math import factorial
import sys


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


def main():
    n, p = map(int, sys.stdin.readline().strip().split(" "))
    a = map(int, sys.stdin.readline().strip().split(" "))
    evens, odds = 0, 0
    for i in a:
        if i % 2 == 0:
            evens += 1
        else:
            odds += 1


    if p % 2 == 0:
        r = 0
        for j in range(0, odds + 1, 2):
            r += combinations(odds, j)
        print(2 ** evens * r)
    else:
        r = 0
        if odds == 0:
            print(0)
        else:
            for j in range(1, odds + 1, 2):
                r += combinations(odds, j)
            print(2 ** evens * r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

n, p = map(int, raw_input().rstrip().split(' '))
a = map(int,raw_input().rstrip().split(' '))
ct = Counter(ai%2 for ai in a)
even, odd = ct[0], ct[1]
c_even = 2**even
nCk = 1
n = odd
k = 0
d = n
c_odd = 0
while k <= n:
    if k % 2 == p:
        c_odd += nCk
    k += 1
    nCk = nCk * d / k
    d -= 1
print c_even * c_odd

Submission status: Accepted

Solution code:
n,p=input().split()
a=list(input().split())
n,p=int(n),int(p)
num0=0
for i in range(0,n):
	a[i]=int(a[i])%2
	if a[i]<1:num0+=1
num1=n-num0
ans,mul=1<<num0,0
def fac(n):
	res=1
	for i in range(1,n+1):res*=i
	return res
def C(n,m):return fac(n)//fac(m)//fac(n-m)
for i in range(p,num1+1,2):mul+=C(num1,i)
print(ans*mul)

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()]
c0 = 0; c1 = 0
for i in a:
    if (i % 2 == 0):
        c0 += 1
    else:
        c1 += 1
        
ans = 0
for x in range(0, c0 + 1):
    for y in range(0, c1 + 1):
        if (y % 2 == p):
            ans += C(c0, x) * C(c1, y)
            
print ans

Submission status: Accepted

Solution code:
comb = [[1] for _ in range(51)]

for i in range(1, 51):
    for j in range(1, i):
        comb[i].append(comb[i - 1][j - 1] + comb[i - 1][j])
    comb[i].append(1)

n, p = map(int, input().split())
a = list(map(int, input().split()))
even = 0
odd = 0
for ai in a:
    if ai % 2 == 0:
        even += 1
    else:
        odd += 1
ans = 0
for i in range(p, odd + 1, 2):
    ans += 2 ** even * comb[odd][i]

print(ans)

Submission status: Accepted

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

odd_n = 0
even_n = 0

for A in A_list:
    if A % 2 == 0:
        even_n += 1
    else:
        odd_n += 1

ncr = 1
odd_odd_cnt = 0
even_odd_cnt = 1

for i in range(1, odd_n+1):
    ncr *= odd_n-(i-1)
    ncr /= i
    if i % 2 == 0:
        even_odd_cnt += ncr
    else:
        odd_odd_cnt += ncr


if P == 0:
    print(int(even_odd_cnt * pow(2, even_n)))
else:
    print(int(odd_odd_cnt * pow(2, even_n)))

Submission status: Accepted

Solution code:
def ncr(n, r):
    ans = 1
    if r * 2 > n:
        return ncr(n, n - r)
    for i in xrange(n - r + 1, n + 1):
        ans *= i
    for i in xrange(1, r + 1):
        ans //= i
    return ans


def main():
    n, p = [int(_) for _ in raw_input().split()]
    o = 0
    e = 0
    for ai in (int(_) for _ in raw_input().split()):
        if ai % 2 == 1:
            o += 1
        else:
            e += 1
    t = 2 ** e
    ans = 0
    for q in xrange(p, o + 1, 2):
        ans += t * ncr(o, q)
    return ans


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

Submission status: Accepted

Solution code:
n, p = [int(x) for x in input().split(' ')]
dp1 = [0,0]
dp2 = [0,0]
data = [int(x) for x in input().split(' ')]
count = 0
for i in range(n):
    tmp = data[i]
    if(tmp % 2 == 1):
        count += 1
if(count == 0):
    if(p == 0):
        print(2**n)
    else:
        print(0)
    exit()
print(2**(count - 1) *2 ** (n - count))

Submission status: Accepted

Solution code:
from math import *

N, P = [int(s) for s in input().split()]

A = [int(e) for e in input().split()]

counter = [0, 0]

for a in A:
    counter[a % 2] += 1

even = 0

def nCk(n, k):
    res = 1
    for i in range(k):
        res *= (n - i)
    res //= factorial(k)
    return res

for c in range(counter[0] + 1):
    even += nCk(counter[0], c)

ans = 0
if P == 0:
    for i in range(0, counter[1] + 1, 2):
        ans += nCk(counter[1], i) * even
else:
    for i in range(1, counter[1] + 1, 2):
        ans += nCk(counter[1], i) * even

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import re
import string

N, P = map(int, input().split())
As = list(map(int, input().split()))
odd = sum(1 for x in As if x % 2 == 1)
even = N - odd

def C(n, k):
    ans = 1
    for i in range(n - k + 1, n + 1):
        ans *= i
    for j in range(1, k + 1):
        ans //= j
    return ans

even_way = 0
for i in range(even + 1):
    even_way += C(even, i)

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

Submission status: Accepted

Solution code:
import sys

# sys.stdin = open('a1.in')


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


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    n, p = read_int_list()
    a = read_int_list()
    a = map(lambda x: x % 2, a)
    o = sum(a)
    e = n - o
    res = 0
    c = 1
    for k in range(o + 1):
        if k % 2 == p % 2:
            res += c
        c *= o - k
        c //= k + 1
    res *= 2 ** e
    return res


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

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:
n,p = map(int,raw_input().split())

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

odd = 0
even = 0

f = []

f.append(1)
f.append(1)

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

for x in a:

	if x%2 == 1:
		odd+=1
	else:
		even+=1

ans = 0

poweven = pow(2,even)

if p == 1:

	for i in range(1,odd+1,2):
		ans += poweven*f[odd]//(f[i]*f[odd-i])

else:

	for i in range(0,odd+1,2):
		ans += poweven*f[odd]//(f[i]*f[odd-i])

print ans

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
a = list(map(int, input().split()))
cnt = [0 for i in range(5001)]
cnt[0] = 1
for i in range(n):
    for j in range(5000-i, -1, -1):
        if cnt[j] > 0:
            cnt[j+a[i]] += cnt[j]
total = 0
for i in range(p, 5001, 2):
    total += cnt[i]

print(total)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

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

ans = 0
zero = 1
one = 0
for i in xrange(N):
    if A[i] % 2 == 0:
        zero *= 2
        one *= 2
    else:
        zero, one = zero + one, zero + one

print zero if P == 0 else one

Submission status: Accepted

Solution code:
n, p = map(int, raw_input().split())
a = map(int, raw_input().split())
t = [1, 0]
for x in a:
    x %= 2
    t = [t[0] + t[1], t[0] + t[1]] if x else [t[0] * 2, t[1] * 2]
print t[p]

Submission status: Accepted

Solution code:
from sys import stdin 
import math
n,p = map(int,stdin.readline().split())
total = 1<<n
even = 0 
odd = 0
a = map(int,stdin.readline().split())
for i in a:
    if i%2:
        odd+=1
    else:
        even+=1
fir = (1<<even)        
if odd:        
    fir*= (1<< (odd-1))
if p==0:
    print fir
else:
    print total - fir

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n,p = LI()
    a = LI()

    r = [0] * 5005
    r[0] = 1
    for c in a:
        for i in range(5000,c-1,-1):
            r[i] += r[i-c]

    rr = 0
    for i in range(5005):
        if i%2 == p:
            rr += r[i]

    return rr


print(main())

Submission status: Accepted

Solution code:

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

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

dp0=[1]*(n+1)
dp1=[0]*(n+1)

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

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

if p==0:
    print(dp0[n])
else:
    print(dp1[n])

Submission status: Runtime Error

Solution code:
import math

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

if __name__ == '__main__':  
    N, P = map(int, input().split())
    A = list(map(int, input().split()))

    ans = 0
    if P == 0:
        if i==1:
            print(0)
            quit()
        for i in range(0, N+1, 2):
            ans += comb(N, i)
    else:
        for i in range(1, N+1, 2):
            print(i)
            ans += comb(N, i)
    print(ans)

Submission status: Runtime Error

Solution code:
from scipy.special import comb
n, p = map(int, input().split())
a = list(map(int, input().split()))
ev, od = 0, 0
for i in a:
    if i%2 == 0:
        ev += 1
    else:
        od += 1
ans = 0
if p == 0:
    for i in range(0, od+1, 2):
        for j in range(ev+1):
            ans += comb(od, i, exact = True)*comb(ev, j, exact = True)
else:
    for i in range(1, od+1, 2):
        for j in range(ev+1):
            ans += comb(od, i, exact = True)*comb(ev, j, exact = True) 
print(ans)

Submission status: Runtime Error

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

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

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

print(res)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import math

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

memo = [[0 for _ in range(50)] for _ in range(50)]

def c(n,k):
  if memo[n][k] != 0:
      return memo[n][k]
  if(k<=0 or n<=k):
      memo[n][k] = 1
      return 1
  else:
      ans = c(n-1, k-1) + c(n-1, k)
      memo[n][k] = ans
      return ans

for i in range(50):
  pascal_triangle.append([c(i,j) for j in range(i+1)])

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

Select_0_count = sum(pascal_triangle[N - Numbers_1])

ans = 0

for i in range(Numbers_1+1):
    if i % 2 == P:
        ans += pascal_triangle[Numbers_1][i] * Select_0_count

print(ans)