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: Wrong Answer

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:
	ans += f(2, cnt[0])
	if cnt[1] != 0:
		ans += f(2, cnt[1]-1);
else:
	if cnt[1] != 0:
		ans = f(2, n-1)

print ans

Submission status: Wrong Answer

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

od = 0
ev = 0
for i in xrange(n):
    if a[i] % 2 == 1:
        od += 1
    else:
        ev += 1

res = 2 ** ev
if p == 1 and od == 0:
    res = 0
else:
    res *= 2 ** (od-1)

print res

Submission status: Wrong Answer

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[0] != 0:
		ans += f(2, cnt[0])
	if cnt[1] != 0:
		ans += f(2, cnt[1]-1);
else:
	if cnt[1] != 0:
		ans = f(2, n-1)

print ans

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
aa = list(map(int, input().split()))
cnt = 0
for bit in range(1<<n):
  bs = 0
  for i in range(n):
    if bit &(1<<n):
      bs += aa[i]
  if bs % 2 == p:
    cnt += 1
print (cnt//2)

Submission status: Time Limit Exceeded

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

    for bit in range(1<<N):
        eat = []
        for i in range(N):
            if bit>>i&1:
                eat.append(i)
        s = 0
        for e in eat:
            s += A[e]

        if s%2 == P:
            ans += 1

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,p = map(int,input().split())
a = list(map(int,input().split()))
z = 0
for i in range(2**n):
    x = i
    y = 0
    for j in range(n):
        if x % 2 != 0:
            y += a[j]
        x = x // 2
        if x == 0:
            break
    if y % 2 == p:
        z += 1
print(z)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

n, p = map(int, input().split())
A = list(map(int, input().split()))         
C =[list(combinations(A, i)) for i in range(1, n+1)]

#print(C)
if p==0:
  cnt = 1
  for cs in C:
    for c in cs:
      if sum(c) % 2 == 0:
        #print(sum(c))
        cnt += 1
if p==1:
  cnt = 0
  for cs in C:
    for c in cs:
      if sum(c) % 2 == 1:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(2**n):
    cnt = 0
    for j in range(n):
        if ((i>>j)&1):
            cnt += a[j]
    if cnt%2 == p:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f(n, p, a):
    if n == 1:
        if p == 0 and a[0] % 2 == 0:
            print(2)
        elif p == 0 and a[0] % 2 == 1:
            print(1)
        elif p == 1 and a[0] % 2 == 0:
            print(0)
        elif p == 1 and a[0] % 2 == 1:
            print(1)
    else:
        import itertools
        bin = list(itertools.product([0, 1], repeat=n))
        count = 0
        for i in bin:
            total = sum([a[j] for j in i if j == 1])
            if total % 2 == p:
                count += 1
        print(count)

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

Submission status: Time Limit Exceeded

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

ans = 0

for i in range(0, 2 ** n):
    ix = (bin(i)[2:]).zfill(n)
    s = sum([a[j] * int(ix[j]) for j in range(n)])
    if (s % 2 == p):
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(2**N):
    total = 0
    for j in range(N):
        if ((i>>j)&1):
            total += A[N-j-1]
    if total%2==P:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from itertools import combinations

MOD = 2  # type: int


def solve(N: int, P: int, A: "List[int]"):
    c = 0
    for i in range(N+1):
        for com in combinations(A, i):
            if sum(com) % 2 == P:
                c += 1
    print(c)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n,p = readInts()
    A = readInts()
    cnt = 0
    for bit in range(1 << n):
        now = 0
        for i in range(n):
            if bit & (1 << i):
                now += A[i]
        if now % 2 == p:
            cnt += 1
    print(cnt)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import  itertools

n,p=map(int,input().split())
a=list(map(int,input().split()))
ans=0
nums=[0,1]


def judge(C):
    er=0
    for i,cnt in enumerate (C):
        if cnt==1:
            er+=a[i]
    if er%2==p:
        return True
    else:
        return False


for biscuits in itertools.product(nums,repeat=n):
    t=list(biscuits)
    if judge(t):
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, m = map(int, input().split())
a = list(map(int, input().split()))
count = 0
for i in range(len(a) + 1):
    for j in itertools.combinations(a, r=i):
        if sum(j) % 2 == m:
            count += 1
print(count)

Submission status: Time Limit Exceeded

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

#bit全探索
count = 0
for i in range(2**N):
    sum = 0
    for j in range(N):
        if (i>>j)&1:
            sum = sum + A[j]
    if sum%2==P:
        count = count + 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N,P = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
for i in range(2**N):
  pattern = str(bin(i)[2:].zfill(N))
  count = 0
  for j in range(N):
    if pattern[j] == '1':
      count += A[j]
  if count%2 == P:
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(1 << n):
    biscuits = 0
    for j in range(n):
        if i >> j & 1:
            biscuits = (biscuits + a[j] % 2) % 2
    if biscuits % 2 == p:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

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

    # bit全探索
    # https://qiita.com/gogotealove/items/11f9e83218926211083a#%E4%BE%8B%E9%A1%8C-1
    ans=0
    for i in range(2 ** N):
        cnt = 0
        for j in range(N):  # このループが一番のポイント
            if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                cnt+=A[j]
        if cnt%2==P:
            ans+=1
    print(ans)



resolve()

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,P = map(int,input().split())
A = list(map(int,input().split()))
even = [a for a in A if a%2==0]
odd = [a for a in A if a%2==1]
li0 = []
li1 = []
ans = 0
if P==0:
    for _ in range(0,len(odd)+1,2):
        li0.append(len(list(itertools.combinations(odd,_))))
    for i in range(len(even)+1):
        tmp = len(list(itertools.combinations(even,i)))
        for j in li0:
            ans += tmp*j
else:
    for _ in range(len(even)+1):
        li1.append(len(list(itertools.combinations(even,_))))
    for i in range(1,len(odd)+1,2):
        tmp = len(list(itertools.combinations(odd,i)))
        for j in li1:
            ans += tmp*j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,P = map(int,input().split())
A = list(map(int,input().split()))
even = [a for a in A if a%2==0]
odd = [a for a in A if a%2==1]
ans = 0
if P==0:
    for i in range(len(even)+1):
        tmp1 = len(list(itertools.combinations(even,i)))
        for j in range(0,len(odd)+1,2):
            tmp2 = len(list(itertools.combinations(odd,j)))
            ans += tmp1*tmp2
else:
    for i in range(1,len(odd)+1,2):
        tmp1 = len(list(itertools.combinations(odd,i)))
        for j in range(len(even)+1):
            tmp2 = len(list(itertools.combinations(even,j)))
            ans += tmp1*tmp2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

ans = 0
for i in range(N+1):
    combi = list(combinations(lst_A, i))
    # print(combi)
    for tpl in combi:
        mod = sum(tpl)%2
        if mod == P:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,p=map(int,input().split())
a=list(map(int,input().split()))
cnt=0
for i in range(1<<n):
    total=0
    for j in range(n):
        if i&(1<<j):
            total+=a[j]
    if p==0:
        if total%2==0:
            cnt+=1
    elif p==1:
        if total%2==1:
            cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

for i in biscuits:
    if i % 2 == 0:
        even.append(i)
    elif i % 2 == 1:
        odd.append(i)

if P == 0:
    # even
    answer = 1
    for i in range(1, len(even)+1):
        c = list(itertools.combinations(even,i))
        answer += len(c)
    for i in range(2, len(odd)+1, 2):
        c = list(itertools.combinations(odd,i))
        answer += len(c)
    print(answer)
elif P == 1:
    # odd
    answer = 0
    even_c = 1
    odd_c = 0
    for i in range(1, len(even)+1):
        c = list(itertools.combinations(even,i))
        even_c += len(c)
    for i in range(1, len(odd)+1, 2):
        c = list(itertools.combinations(odd,i))
        odd_c += len(c)
    print(even_c * odd_c)

Submission status: Time Limit Exceeded

Solution code:
import math
def comb(n,r):
  if r>n: return 0
  else: return int(math.factorial(n)/(math.factorial(r)*math.factorial(n-r)))

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

ans=0
if flag==0:#evenの場合
  for i in range(odd//2+1):
    ans+=comb(odd,2*i)
else:#oddの場合
  for i in range(2*(n+1)//2+1):
    ans+=comb(odd,1+2*i)
print(ans*n)

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain
from itertools import combinations

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


def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))

for i in(powerset(a)):
    if sum(i) % 2 == p:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
import itertools
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]
if P == 0:
    ans += 1
    b = sum([ len(list(itertools.combinations(odd,tmp))) for tmp in range(2, len(odd)+1, 2) ])
else:
    b = sum([ len(list(itertools.combinations(odd,tmp))) for tmp in range(1, len(odd)+1, 2) ])
c = [ len(list(itertools.combinations(even, tmp))) for tmp in range(1, len(even)+1) ]
factor = 0
for tmp in c:
    ans += tmp*b
    factor += tmp
else:
    if P == 0:
        ans += b+factor
    else:
        ans += b
print(ans)

Submission status: Time Limit Exceeded

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):
    if n < 0 or r < 0 or n < r:
        return 0
    elif n == 0 or r == 0:
        return 1
    else:
        return comb(n-1,r-1)+comb(n-1,r)

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: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
import itertools
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]
if P == 0:
    ans += 1
    b = [ len(list(itertools.combinations(odd,tmp))) for tmp in range(2, len(odd)+1, 2) ]
else:
    b = [ len(list(itertools.combinations(odd,tmp))) for tmp in range(1, len(odd)+1, 2) ]
c = [ len(list(itertools.combinations(even, tmp))) for tmp in range(1, len(even)+1) ]
factor = sum(b)
for tmp in c:
    ans += tmp*factor
if P == 0:
    ans += factor+sum(c)
else:
    ans += factor

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
import itertools
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]
b = []
c = []
if P == 0:
    ans += 1
    for tmp in range(2, len(odd)+1, 2):
        b.append(len(list(itertools.combinations(odd,tmp))))
else:
    for tmp in range(1, len(odd)+1, 2):
        b.append(len(list(itertools.combinations(odd, tmp))))

for tmp in range(1, len(even)+1):
    c.append(len(list(itertools.combinations(even, tmp))))
for tmp in c:
    for tmp2 in b:
        ans += tmp*tmp2

if P == 0:
    ans += sum(b)+sum(c)
else:
    ans += sum(b)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

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:
        i = 1
        one_pattern = 1
        while i*2 <= one_count:
            one_pattern  += len(list(itertools.combinations(np.arange(one_count),i*2)))
            i += 1
    else:
        one_pattern = 1
else:
    if one_count >= 1:
        i = 1
        one_pattern = 0
        while i*2 - 1 <= one_count:
            one_pattern  += len(list(itertools.combinations(np.arange(one_count),i*2-1)))
            i += 1
    if one_count < 1:
        one_pattern = 0
        
print(zero_pattern * one_pattern)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, P = input().split()
A = list(map(int, input().split()))
if int(P) == 0:
    ans = 1
else:
    ans = 0
for i in range(int(N)):
    for j in itertools.combinations(A, i+1):
        if sum(j)%2 == int(P):
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#Biscuits

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

import numpy as np

a = np.array(A)
f = 2**N-1
cnt = 0
for i in range(2**N):
    ff = np.array(list(map(int,list(format(f,'b').zfill(N)))))
    s = np.sum(ff * a)
    if ( s%2 == P ):
        cnt+=1
    f-=1
print (cnt)

Submission status: Accepted

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k 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 *= int(numerator[k])

    return result


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
        
ans = 0
for i in range(P, odd+1, 2):
    ans += cmb(odd, i)
    
ans *= 2 ** even

print(ans)

Submission status: Accepted

Solution code:
N,P=map(int,input().split())
A=list(map(int,input().split()))
f=0
for i in range(N):
  if A[i]%2==1:
    f=1
if f==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 comb(x, y):
  m = c = 1
  for i in range(y):
    m *= x-i
    c *= y-i
  return m//c
even = odd = 0
for a in A:
  if a%2 == 0:
    even += 1
  else:
    odd += 1
ans = 0
for i in range(P, odd+1, 2):
  ans += comb(odd, i)
print(pow(2, even) * ans)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
A = list(map(int, input().split()))
def comb(x, y):
  m = c = 1
  for i in range(y):
    m *= x-i
    c *= y-i
  return m//c
even = odd = 0
for a in A:
  if a%2 == 0:
    even += 1
  else:
    odd += 1
if P == 0:
  ans = 0
  for i in range(0, odd+1, 2):
    ans += comb(odd, i)
  print(pow(2, even) * ans)
else:
  ans = 0
  for i in range(1, odd+1, 2):
    ans += comb(odd, i)
  print(pow(2, even) * ans)

Submission status: Accepted

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

# dp[i][j] := i-1番目のbuiscuitsまでみて、食べた枚数のあまりがjであるような方法の数
dp = [[0,0] for _ in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
    next = (a_ls[i-1])%2
    if next == 0:
        dp[i][0] += 2 * dp[i-1][0]
        dp[i][1] += 2 * dp[i-1][1]
    else:
        dp[i][0] += dp[i-1][0] + dp[i-1][1]
        dp[i][1] += dp[i-1][0] + dp[i-1][1]
print(dp[-1][P])

Submission status: Accepted

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 6)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

n,p = I()
A = [2 if i%2==0 else 1 for i in I()]
a = set(A)



if p == 0:
    if len(a)==1 and 2 in a:
        print(2**n)
    else:
        print(2**(n-1))
else:
    if len(a)==1 and 2 in a:
        print(0)
    else:
        print(2**(n-1))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    n,p=MI()
    lis=LI()
    ev=0
    od=0
    for i in range(n):
        if lis[i]%2==0:
            ev+=1
        else:
            od+=1
    ans=0
    for i in range(od+1):
        if i%2==p:
            ans+=factorial(od)//factorial(i)//factorial(od-i)
    ans*=2**ev
    print(ans)

            
        
        







if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:

def resolve():
    # P は [0, 1]
    N, P = map(int, input().split())
    A = list(map(int, input().split()))

    odds = sum([1 for a in A if a % 2 == 1])

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

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7


# nCr

def ruijo(n, l, mod):
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


def cmb(n, r, mod):
    if r == 1:
        return n
    elif (n == r or r == 0):
        return 1
    else:
        if (r < 0 or r > n):
            return 0
        r = min(r, n - r)
        return ruijo(n, n - r + 1, mod) * g2[r] % mod


mod = 10 ** 18 + 7  # 出力の制限
N = 10 ** 3
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

n,p = lr()
a = [x%2 for x in lr()]
odd_n = sum(a)
even_n = n-odd_n
ans = 0
if p%2 == 0:
    for i in range(0,odd_n+1,2):
        ans += cmb(odd_n, i, mod)
else:
    for i in range(1,odd_n+1,2):
        ans += cmb(odd_n, i, mod)
ans = (2**even_n)*ans
print(ans)

Submission status: Accepted

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

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)]

oishii = a.count(1)

c = sum([cmb(oishii,i) for i in range(p,oishii+1,2)])

print(c*2**(n-oishii))

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
A = list(map(int, input().split()))
def comb(n, k):
  ret = 1
  for i in range(1, k+1):
    ret = ret * (n+1-i) // i
  return ret
Even = 0
Odd = 0
for a in A:
  if a % 2 == 0:
    Even += 1
  else:
    Odd += 1
ans = 0
while P <= Odd:
  ans += comb(Odd, P)
  P += 2
print(ans * 2 ** Even)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
A = [int(i)&1 for i in input().split()]
o = A.count(1)
e = N-o
on = en = 0
def ncr(n, r):
    r = min(r,n-r)
    res=1
    d=1
    for i in range(r):
        res*=n-i
        d *= i + 1
    return res//d

for r in range(e+1):
    en+=ncr(e,r)
for r in range(P, o+1, 2):
    on+=ncr(o,r)

print(on*en)

Submission status: Accepted

Solution code:
import sys
def input():
  return sys.stdin.readline().rstrip()

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

temp=0
for i in range(N):
  if A[i]%2==1:
    temp+=1
if temp==0:
  print(1<<N if P == 0 else 0)
else:
  print(1<<(N-1))

Submission status: Accepted

Solution code:
n, p = map(int, input().split()); a = list(map(int, input().split()))
s = t = u = 0; b = [1]
for i in range(n):
    if a[i]%2 == 0: s += 1
    else: t += 1
for i in range(1, n+1):
    b.append(b[-1]*i)
if p == 0:
    for i in range(0, t//2*2+1, 2):
        u += b[t]//b[i]//b[t-i]
else:
    for i in range(1, (t+1)//2*2, 2):
        u += b[t]//b[i]//b[t-i]
print(2**s*u)

Submission status: Accepted

Solution code:
import math
from scipy.special import comb
n, p = map(int, input().split())
aa = list(map(int, input().split()))
odd = []
even = []
for i in range(n):
  if aa[i] % 2 == 0:
    even.append(aa[i])
  else:
    odd.append(aa[i])
    
x = len(odd)
y = len(even)


sum1 = 0
for i in range(0, x+1, 2):
  sum1 += comb(x,i)
sum2 = 0
for i in range(1, x+1, 2):
  sum2 += comb(x,i)
  
if p == 0:
  ans = int((2 ** y) * sum1)
else:
  ans = int((2 ** y) * sum2)
print(ans)

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

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

Submission status: Accepted

Solution code:
import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n, p = read_ints()
    a = read_int_list()
    for x in a:
        if x % 2 == 1:
            print(pow(2, n - 1))
            break
    else:
        print(0 if p == 1 else pow(2, n))

if __name__ == '__main__':
    Main()

Submission status: Accepted

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

m = len([x for x in a if x & 1])

if m == 0:
  if p == 0:
    ans = 2 ** n
  else:
    ans = 0
else:
  ans = 2 ** (n - 1)

print(ans)

Submission status: Accepted

Solution code:

import math
def comb(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()))
AA = [0]*n
for i in range(n):
    if A[i]%2:
        AA[i]=1
sumA = sum(AA)
res1 = 0
for i in range(p,sumA+1,2):
    res1 += comb(sumA,i)
res0 = 2**(n-sumA)

print(res1*res0)

Submission status: Accepted

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n, p = map(int, input().split())
A = list(map(lambda x: int(x) % 2, input().split()))
x = A.count(0)
y = n - x
if p == 1:
    cnt = 0
    for i in range(y + 1):
        if i % 2 == 1:
            cnt += combinations_count(y, i)
    print(2 ** x * cnt)
else:
    cnt = 0
    for i in range(y + 1):
        if i % 2 == 0:
            cnt += combinations_count(y, i)
    print(2 ** x * cnt)