Problem:


Score : 200 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 50

P = 0 or 1

1 \leq A_i \leq 100

Input

Input is given from Standard Input in the following format:

N P
A_1 A_2 ... A_N

Output

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

Sample Input 1

2 0
1 3

Sample Output 1

2

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

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

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

Sample Input 2

1 1
50

Sample Output 2

0

Sample Input 3

3 0
1 1 1

Sample Output 3

4

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

Sample Input 4

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

Sample Output 4

17592186044416



Sample input:
2 0
1 3


Sample output:
2

Submission status: Accepted

Solution code:
from 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()
    m = 0
    A = readInts()
    for i in range(n):
        a = A[i]
        if a % 2 == 1:
            m += 1
    if m == 0:
        print(2**n if p == 0 else 0)
    else:
        print(2**(n-1))
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#https://atcoder.jp/contests/agc017/tasks/agc017_a
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n,p=mii()
arr=limii()
even=0
odd=0
for i in arr:
    if i%2==0:
        even+=1
    else:
        odd+=1

ans=0

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

Submission status: Accepted

Solution code:
#biscuits
n,p=map(int,input().split())
odd=0
even=0
lists=list(map(int,input().split()))
for some in lists:
    if some%2==0:
        even+=1
    else:
        odd+=1
ans=2**even
dp=[1 for i in range(51)]
for i in range(1,51):
    dp[i]=dp[i-1]*i
def combi(n,k):
    return dp[n]//(dp[k]*dp[n-k])
if p%2==0:
    #oddはeven枚数
    sub=0
    for i in range(odd+1):
        if i%2==0:
            sub+=combi(odd,i)
    print(ans*sub)
      
else:
    sub=0
    for i in range(odd+1):
        if i%2!=0:
            sub+=combi(odd,i)
    print(ans*sub)

Submission status: Accepted

Solution code:
N,P = map(int,input().split())
A = list(map(int,input().split()))
odd = 0 
for i in range(N):
  if A[i]%2 != 0:
    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())
a=list(map(int, input().split()))

a_new=[]
for i in range(n):
    a_new.append(a[i]%2)
even=a_new.count(0)
odd=a_new.count(1)

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

Submission status: Accepted

Solution code:
import collections, 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(int, input().split()))
for i in range(N):
    A[i] = A[i] % 2
c = collections.Counter(A)
zero = c[0]
one = c[1]

ans = 0
if P == 0:
    for i in range(0, one + 1, 2):
        ans += (2 ** zero) * (combinations_count(one, i) )
else:
    for i in range(1, one + 1, 2):
        ans += (2 ** zero) * (combinations_count(one, i) )
print(ans)

Submission status: Accepted

Solution code:
def main():
  import math
  n,p=map(int,input().split())
  a=list(map(int,input().split()))
  x=[i for i in a if i%2==0]
  y=[i for i in a if i%2==1]
  
  def comb(n,r):
    return math.factorial(n)//(math.factorial(r)*math.factorial(n-r))
  
  xl,yl=len(x),len(y)
  ans=0
  
  for i in range(xl+1):
    for j in range(yl+1):
      if j%2==p:
        ans+=comb(yl,j)*comb(xl,i)
        
  print(ans)
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


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


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


N, P = readnums()
A = map(lambda x: x % 2, readnums())

if P:
    if not sum(A):
        print(0)
    else:
        print(2 ** N // 2)
else:
    if not sum(A):
        print(2 ** N)
    else:
        print(2 ** N // 2)

Submission status: Accepted

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

import itertools
ad = [a[i]%2 for i in range(n)]

b = Counter(ad)
ama = 1
pet = p

zero = [1] * (b[0]+1)
one = [1] * (b[1]+1)
ze = [0]*2
on = [0]*2

ze[0] = 1
on[0] = 1
for i in range(1,b[0]+1):
    zero[i] = zero[i-1] * (b[0]+1-i) // i
    ze[i%2] += zero[i]
for i in range(1,b[1]+1):
    one[i] = one[i-1] * (b[1]+1-i) // i
    on[i%2] += one[i]
    
if p == 0:
    ans = (ze[0]*on[0] + ze[1]*on[1])
else:
    ans = (ze[0]*on[1] + ze[1]*on[0])
if p == 1 and b[1] == 0:
    ans = 0
if p == 0 and b[1] == 0:
    ans *= 2
    
print(ans)

Submission status: Accepted

Solution code:
import math
N, P = map(int, input().split())
A = list(map(int, input().split()))
even = 0
odd = 0
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

oddcmb = 0
if P == 0:
    for i in range(odd+1)[::2]:
        # print(i)
        oddcmb += comb(odd, i)
    ans = 2**even*oddcmb
    # oddcmb = comb()
else:
    for i in range(1, odd+1)[::2]:
        # print(i)
        oddcmb += comb(odd, i)
    ans = 2**even*oddcmb

print(ans)

Submission status: Accepted

Solution code:
import math
def ncr(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()))
odd=0
even=0

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

if p==1:
    ans=2**even
    odd_choice=0
    for i in range(1,odd+1,2):
        odd_choice+=ncr(odd,i)
    print(ans*odd_choice if even!=0 else odd_choice)

else:
    ans=2**even
    if even==0:
        ans=0
    odd_choice=0
    for i in range(0,odd+1,2):
        odd_choice+=ncr(odd,i)
    print(ans*odd_choice if even!=0 else odd_choice)

Submission status: Accepted

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

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

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

print(dp[N][P])

Submission status: Accepted

Solution code:
from collections import Counter
def main():
    N, P = (int(_) for _ in input().split())
    A = [int(_) for _ in input().split()]
    
    dp = [[0] * 2 for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        dp[i+1][0] += dp[i][0]
        dp[i+1][1] += dp[i][1]
        if A[i]%2 == 0:
            dp[i+1][0] += dp[i][0]
            dp[i+1][1] += dp[i][1]
        else:
            dp[i+1][0] += dp[i][1]
            dp[i+1][1] += dp[i][0]
    print(dp[N][P])
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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

cnt_even = 0
for i in range(n):
	if A[i] % 2 == 0:
		cnt_even += 1

if cnt_even == n:
	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()))
for i in range(N):
    A[i]%=2

odds=sum(A)
evens=N-odds 
if odds>0:
    ans=2**evens 
    ans*=2**(odds-1)
    print(ans)
else:
    if P==0:
        print(2**evens)
    else:
        print(0)

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
a=list(map(lambda x:int(x)%2,input().split()))
d=[0]*n
if p==1:
    if a[0]==1:
        d[0]=1
    else:
        d[0]=0
else:
    if a[0]==1:
        d[0]=1
    else:
        d[0]=2
for i in range(1,n):
    if a[i]==0:
        d[i]=d[i-1]+d[i-1]
    else:
        d[i]=d[i-1]+(2**i-d[i-1])
print(d[n-1])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, P = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    dp_odd = [0 for _ in range(N + 1)]
    dp_even = [0 for _ in range(N + 1)]
    dp_even[0] = 1

    for i in range(1, N + 1):
        if A[i] % 2 == 0:
            dp_odd[i] = dp_odd[i - 1] * 2
            dp_even[i] = dp_even[i - 1] * 2
        else:
            dp_odd[i] = dp_even[i - 1] + dp_odd[i - 1]
            dp_even[i] = dp_odd[i - 1] + dp_even[i - 1]

    if P == 0:
        print(dp_even[-1])
    else:
        print(dp_odd[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

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]"):
    if all(map(lambda a: a % 2 == 0, A)):
        print(2 ** N if P == 0 else 0)
        return
    print(2 ** (N-1))
    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: Accepted

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

Submission status: Accepted

Solution code:
import math

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

b = [a[i] % 2 for i in range(n)]

z = b.count(0)
o = b.count(1)

c = 0

for i in range(o+1):
  if i % 2 == 0:
    c += math.factorial(o)/(math.factorial(i)*math.factorial(o-i))

ans = int(c *( 2 **z))
    
if p == 0:
  print(ans)
else:
  print(str(2**n-ans))

Submission status: Accepted

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

for a in A:
    Am.append(a%2)
if max(Am)==0:
    if P==0:
        print(2**N)
    else:
        print(0)
else:
    print(2**(N-1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100)

def cmb(n,r):
    if r>n/2:
        r=n-r
    if r==0:
        return 1
    else:
        return n*cmb(n-1,r-1)/r

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

for a in A:
    Am.append(a%2)
even=Am.count(0)
odd=N-even
ans=0

if P==0:
    for o in range(0,odd+1,2):
        ans+=int(cmb(odd,o))
    ans*=2**even
else:
    for o in range(1,odd+1,2):
        ans+=int(cmb(odd,o))
    ans*=2**even

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,p = map(int,readline().split())
lst1 = list(map(int,readline().split()))

def pow(n,p): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2
            p //= 2
        else:
            res = res * n
            p -= 1
    return res
#二項係数(modなし) O(k)
def large_conbination(n,k): #no mod. return nCk.
    res1 = 1
    for i in range(n,n-k,-1):
        res1*=i
    res2 = 1
    for i in range(1,k+1):
        res2*= i
    return res1//res2
od = 0
ev = 0
for i in lst1:
    if even(i):
        ev += 1
    else:
        od += 1

#奇数が偶数個
if even(p):
    ans = 0
    res = pow(2,ev)
    for i in range(0,od+1,2):
        ans += res*large_conbination(od,i)
#奇数が奇数個
else:
    ans = 0
    res = pow(2,ev)
    for i in range(1,od+1,2):
        ans += res*large_conbination(od,i)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,p = map(int, input().split())
As = list(map(int, input().split()))
def comb(n,k):
    y = 1
    x = 1
    if k == 0:
        return 1
    while k >= 1:
        x *= (n-k+1)
        y *= k
        k -= 1
    return x//y   
# 偶奇の問題
ps = [a%2 for a in As]
cnt_o = sum(ps)
cnt_e = n - cnt_o

n_o = 0
for i in range(p,cnt_o+1,2):
    n_o += comb(cnt_o,i)

print(n_o*2**cnt_e)

Submission status: Accepted

Solution code:
# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
N,P = map(int,input().split())
# arrA = list(map(int,input().split()))
arrA = np.array(input().split(),dtype=np.int64)

A = arrA % 2
if not (1 in A):
    if P == 1:
        print(0)
        exit()
    else:
        print(2**N)
        exit()

even = 1
odd = 1
for i in sorted(A)[::-1][1:]:
    if i == 0:
        even *= 2
        odd *= 2
    else:
        even,odd = odd + even , odd + even
if P==0:
    print(even)
else:
    print(odd)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))

Submission status: Accepted

Solution code:
def myAnswer(N:int,P:int,A:list) -> int:
   for a in A:
      if(a % 2 == 1):
         return 2**(N - 1)
   return 2**N if( P == 0) else 0

def modelAnswer():
   return
def main():
   N,P = map(int,input().split())
   A = list(map(int,input().split()))
   print(myAnswer(N,P,A[:]))
if __name__ == '__main__':
   main()

Submission status: Accepted

Solution code:
# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
N,P = map(int,input().split())
# arrA = list(map(int,input().split()))
arrA = np.array(input().split(),dtype=np.int64)

A = arrA % 2
bins = np.bincount(A,minlength=2)
    
if bins[1] == 0:
    if P==0:
        print(2**bins[P])
        exit()
    else:
        print(0)
        exit()
else:
    print(2**(N-1))

# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))

Submission status: Accepted

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

gu=0
ki=0

for aa in a:
    if aa%2==0:
        gu+=1
    else:
        ki+=1

gusu=2**gu
if ki>0:
    kisu=2**(ki-1)
else:
    kisu=1

if p==1 and ki==0:
    print(0)
    exit()

print(gusu*kisu)


#pが0だったら選ぶ袋の合計が偶数
#kisu の個数が偶数

#nが1だったら選ぶ袋の合計が奇数
#gusu の個数が奇数

#nは50、全探索はできんね

Submission status: Accepted

Solution code:
def com(n, a):
    a = min([a, n-a])
    x = 1
    for i in range(n-a+1, n+1):
        x *= i
    for i in range(1, a+1):
        x //= i
    return x


n, p = map(int, input().split())
a = [i%2 for i in map(int, input().split())]
b = sum(a) #奇数
d = n-b #偶数
if p==1:
    x = 0
    c = 1
    while c <= b:
        x += com(b, c)
        c += 2
    x *= 2**d
else:
    x = 1
    c = 2
    while c <= b:
        x += com(b, c)
        c += 2
    x *= 2**d

print(x)

Submission status: Accepted

Solution code:
import sys
from math import factorial

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, p = map(int, input().split())
    A = list(map(int, input().split()))

    cnt_odd = 0
    for i in range(n):
        if A[i] % 2 != 0:
            cnt_odd += 1
    cnt_even = n - cnt_odd

    odd = 0
    for r in range(1, n + 1, 2):
        if cnt_odd - r >= 0:
            odd += factorial(cnt_odd) // factorial(r) // factorial(cnt_odd - r)
    even = pow(2, cnt_even)

    odd_pattern = even * odd
    total = pow(2, n)
    if p == 0:
        print(total - odd_pattern)
    else:
        print(odd_pattern)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

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

n,m = inpl()
a = inpl()
odd = even = 0
for x in a:
    if x%2: odd += 1
    else: even += 1
res = pow(2,even)
ores = eres = 0
for i in range(odd+1):
    if i%2 == 0:
        eres += conb(odd,i)
    else:
        ores += conb(odd,i)
if m:
    print(ores*res)
else:
    print(eres*res)

Submission status: Accepted

Solution code:
import sys
from math import factorial as f

input = sys.stdin.readline


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


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

    r = [a % 2 for a in A]
    n_1 = sum(r)
    n_0 = N - n_1

    c_0 = 2**n_0
    if P == 0:
        c_1 = 0
        for i in range(0, n_1+1, 2):
            c_1 += nCr(n_1, i)
    elif P == 1:
        c_1 = 0
        for i in range(1, n_1+1, 2):
            c_1 += nCr(n_1, i)
    ans = c_0 * c_1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,p = map(int,input().split())
a = list(map(int,input().split()))
even = []
odd = []
for i in range(n):
    if a[i]%2 == 0:
        even.append(a[i])
    else:
        odd.append(a[i])

#print(2**len(even)*2**(len(odd)-1)-1)if len(odd) > 0 else print(2**len(even))

if len(odd) > 0:
    print(2**len(even)*2**(len(odd)-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)%2 for x in input().split()]
even=0
for aa in a:
    if aa%2==0:
        even+=1

if even==n:
    if p==0:
        print(2**n)
    else:
        print(0)
else:
    dp=[[0]*3 for i in range(n+1)]
    if a[0]%2==0:
        dp[0][0]=1
        dp[0][1]=0
    else:
        dp[0][0]=0
        dp[0][1]=1    
    for i in range(n):
        for j in range(2):
            j%=2
            if a[i]%2==0:
                dp[i+1][j]=2*dp[i][j]
                dp[i+1][(j+1)%2]=2*dp[i][(j+1)%2]
            elif a[i]%2==1:
                dp[i+1][j]=dp[i][j]+dp[i][(j+1)%2]
                dp[i+1][(j+1)%2]=dp[i][j]+dp[i][(j+1)%2]
    
    print(dp[n][p])

Submission status: Accepted

Solution code:
# Problem A - Biscuits

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

# initialization
even_count = 0
odd_count = 0
for a in a_nums:
    if a%2==0:
        even_count += 1
    else:
        odd_count += 1

# check
if even_count==N:
    if P==0:
        print(2**N)
    else:
        print(0)
else:
    print(2**(N-1))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict
from operator import mul
from functools import reduce


def nCr(n, r):
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


n, p = map(int, readline().split())
a = list(map(lambda x: int(x) % 2, readline().split()))
dict = defaultdict(int)
for aa in a:
    dict[aa] += 1
memo = 2 ** dict[0]
ans = 0
if p == 0:
    ans += memo
    m = 2
else:
    m = 1
for i in range(m, dict[1] + 1, 2):
    ans += nCr(dict[1], i) * memo
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, P = list(map(int,_in[0].split(' ')))  # type:list(int)
    A_arr = list(map(int,_in[1].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_A_odd = len([0 for a in A_arr if a%2==1])
    len_A_even = len(A_arr) - len_A_odd
    cnt = 0
    if P==0:
        cnt = 2**len_A_even*max(2**(len_A_odd-1),1)
    else:
        cnt = 2**len_A_even*(2**(len_A_odd-1) if len_A_odd>0 else 0)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


n,p=map(int,input().split())
a=list(map(int,input().split()))
guu=0
ki=0
for i in range(n):
  if a[i]%2==0:
    guu+=1
  else:
    ki+=1
ans=0
if p==0:
  i=0
  while i<=ki:
    ans+=cmb(ki,i)
    i+=2
  print((2**guu)*ans)
  
else:
  i=1
  while i<=ki:
    ans+=cmb(ki,i)
    i+=2
  print((2**guu)*ans)

Submission status: Accepted

Solution code:
import math
N, P = map(int,input().split())
A = list(map(int,input().split()))
B = [e%2 for e in A]
ans = pow(2,B.count(0))
def nCr(n,r):
    return (math.factorial(n)//(math.factorial(r)*math.factorial(n-r)))
t = 0
for k in range(B.count(1)+1):
    if k%2 == 0:
        t += nCr(B.count(1),k)
print(ans*t if P == 0 else pow(2,N)-ans*t)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over= reduce(mul,range(n,n-r,-1))
    under = reduce(mul,range(1,r + 1))
    return over // under


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

ae = [0,0]
ans = 0

for i in range(N):
    ae[A[i] % 2] += 1
for i in range(1,ae[1] + 1,2):
    ans += cmb(ae[1] ,i)
ans *= 2 ** ae[0]

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

Submission status: Accepted

Solution code:
N,P=map(int, input().split())
*A,=map(int, input().split())
odd=sum(1 for a in A if a&1)
if odd==0:
    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()))
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


odds=0
evens=0
for a in A:
    if a%2==0:
        evens+=1
    else:
        odds+=1
ans=0
a=0
b=0
if P==0:
    #偶数と奇数を偶数個
    for i in range(evens+1):
        a+=cmb(evens, i)
    for j in range(0,odds+1, 2):
        b+=cmb(odds, j)
    #print(a,b)
    ans+=a*b
if P==1:
    #偶数と奇数を奇数個
    for i in range(evens+1):
        a+=cmb(evens, i)
    for j in range(1,odds+1, 2):
        b+=cmb(odds, j)
    ans+=a*b
print(ans)

Submission status: Accepted

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

if t==0:
    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 = list(map(int, input().split()))

n = 0
for a in A:
    if a % 2 == 0: n += 1
if N == n:
    if P == 0:
        ans = 2 ** N #選ぶか選ばないか => 2通り
    else: ans = 0
else: ans = 2 ** (N-1)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

a = a%2

one = np.count_nonzero(a)
zero = n - one

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

ans = 0

for i in range(one+1):
    if i % 2 == p:
        ans += cmb(one, i)
        # print(ans)

ans *= 2**zero

print(ans)

Submission status: Accepted

Solution code:
def comb(n, r):
    return fact(n) // (fact(r) * fact(n - r))

def fact(n):
    if n < 0:
        return
    if n == 0:
        return 1
    ret = n
    for i in range(n-1, 0, -1):
        ret *= i
    return ret

def main():
    n, p = map(int, input().split())
    A = list(map(int, input().split()))
    AA = [i % 2 for i in A]
    even = AA.count(0)
    odd_cnt = n - even
    ans = 0
    if p:  # oddのとき
        for i in range(odd_cnt + 1):
            if i % 2 != 0:
                ans += comb(odd_cnt, i)
    else:  # evenのとき
        for i in range(odd_cnt + 1):
            if i % 2 == 0:
                ans += comb(odd_cnt, i)
    print(2 ** even * ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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()))
    even=0
    odd=0
    for i in range(n):
        if A[i]%2==0:
            even+=1

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



resolve()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

import collections
import math

c = collections.Counter()

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

ans = 0
if P == 0:
    ans1 = 0
    for i in range(0, c[1] + 1, 2):
        ans1 += math.factorial(c[1]) / math.factorial(i) / math.factorial(c[1] - i)

    for i in range(c[0] + 1):
        ans0 = math.factorial(c[0]) / math.factorial(i) / math.factorial(c[0] - i)
        ans += ans0 * ans1
else:
    ans1 = 0
    for i in range(1, c[1] + 1, 2):
        ans1 += math.factorial(c[1]) / math.factorial(i) / math.factorial(c[1] - i)

    for i in range(c[0] + 1):
        ans0 = math.factorial(c[0]) / math.factorial(i) / math.factorial(c[0] - i)
        ans += ans0 * ans1


print(int(ans))

Submission status: Accepted

Solution code:
from collections import Counter

def combination(n, r): #nCrを求める
    if n - r > r:
        r = n - r
    tmp = 1
    for i in range(n - r + 1, n + 1):
        tmp *= i
    for i in range(1, r + 1):
        tmp //= i
    return tmp

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

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

C = Counter(B)

odd = C[1]
even = C[0]

ans = 0
for i in range(P, odd + 1, 2):
    tmp = combination(odd, i)
    ans += tmp

ans *= pow(2, even)
print (ans)

Submission status: Accepted

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

even=sum(1 for a in A if a&1==0)
odd =sum(1 for a in A if a&1==1)

def comb(n, r):
    p, q = 1, 1
    for i in range(min(r,n-r)):
        p *= n-i
        q *= i+1
    return p // q

ans=0
for i in range(P,odd+1,2):
    ans+=comb(odd, i)
ans *= 1<<even

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N, P = (int(i) for i in input().split())
    A = [int(i) % 2 for i in input().split()]
    from collections import Counter
    c = Counter(A)
    ans = 0
    if P == 0:
        ans = 2**c[0]
        if 0 < c[1]:
            ans *= 2**(c[1]-1)
    else:
        if 0 < c[1]:
            ans = 2**(c[1]-1)
        ans *= 2**c[0]
    print(ans)


if __name__ == '__main__':
    main()