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

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

ans = 0
import math
if p == 0:
    for i in range(odd+1):
        if i%2 == 1:
            continue
        ans += (2**even)* math.factorial(odd) // math.factorial(odd - i) //math.factorial(i)

else:
    for i in range(odd+1):
        if i%2 == 0:
            continue
        ans += (2**even)* math.factorial(odd) // math.factorial(odd - i) //math.factorial(i)

print(ans)

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
a=list(map(int,input().split()))
z=o=0
for i in a:
  if i&1:o+=1
  else:z+=1
if o==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(lambda a: int(a) % 2, input().split()))

if P == 1 and A.count(1) == 0:
    print(0)
    exit()

if P == 0 and A.count(1) == 0:
    print(2**N)
    exit()

print(2**(N - 1))

Submission status: Accepted

Solution code:

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

num = 0
count = 0

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

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

Submission status: Accepted

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

from math import factorial
ec = 0
for i in range(e+1):
    ec += factorial(e)//(factorial(e-i)*factorial(i))
oc = 0
if p==0:
    for i in range(o+1):
        if i%2==0:
            oc += factorial(o)//(factorial(o-i)*factorial(i))
else:
    for i in range(o+1):
        if i%2==1:
            oc += factorial(o)//(factorial(o-i)*factorial(i))
print(oc*ec)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# AGC 017: A – Biscuits
N, P = [int(s) for s in input().split()]
A = [int(s) for s in input().split()]

isAllEven = True

for k in A:
    if k % 2 == 1:
        isAllEven = False
        break

if isAllEven:
    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()))
odd=[0]*n
even=[0]*n

if a[0]%2==0:
    even[0]=2
else:
    odd[0]=1
    even[0] = 1

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

if p==0:
    print(even[n-1])
else:
    print(odd[n-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
table = [[None] * 101 for _ in range(101)]

def comb(n, r):
  if not table[n][r] is None:
    return table[n][r]
  
  if n == r or r == 0:
    table[n][r] = 1
  elif r == 1:
    table[n][r] = n
  else:
    table[n][r] = comb(n - 1, r - 1) + comb(n - 1, r)
    
  return table[n][r]

N, P = map(int, input().split())
biscuits = [int(x) for x in input().split()]

num_even = len([x for x in biscuits if x % 2 == 0])
num_odd = N - num_even

A = 0

for r in range(num_even + 1):
  A += comb(num_even, r)

B = 0

for r in range(num_odd + 1):
  if r % 2 == P:
    B += comb(num_odd, r)
    
print(A * B)

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 = [int(i) % 2 for i in input().split()]
A0 = A.count(0)
A1 = A.count(1)
s0 = sum([comb(A0, i) for i in range(0, A0 + 1)])
s10 = sum([comb(A1, i) for i in range(0, A1 + 1, 2)])
s11 = sum([comb(A1, i) for i in range(1, A1 + 1, 2)])

if P == 0:
    print(s0 * s10)
else:
    print(s0 * s11)

Submission status: Accepted

Solution code:
import math
def AGC017C(a,f):
    p=0
    for i in range(f,a+1,2):
        p+=math.factorial(a)//math.factorial(a-i)//math.factorial(i)
    return p

n,p=map(int,input().split())
d={1:0,0:0}
a=list(map(int,input().split()))
for i in a:
    d[i%2]+=1
if p==0:
    print((2**d[0])*AGC017C(d[1],0))
else:
    if d[1]==0:
        print(0)
    else:
        print((2**d[0])*(AGC017C(d[1],1)))

Submission status: Accepted

Solution code:
def com(x,y):
    buns = 1
    bunb = 1
    for i in range(y):
        buns = buns * (x-i)
        bunb = bunb * (i+1)
    d = buns // bunb
    return d

n , p = map(int,input().split())
a = list(map(int,input().split()))
kisu = 0
gusu = 0
for i in a:
    if i % 2 == 0:
        gusu += 1
    if i % 2 == 1:
        kisu += 1

kar = 0
if p == 0:
    for i in range(0,kisu+1,2):
        kar += com(kisu,i)
    print(2**gusu * kar)
elif p == 1:
    for i in range(1,kisu+1,2):
        kar += com(kisu,i)
    print(2**gusu * kar)

Submission status: Accepted

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

odd = A.count(1)
even = N - odd
if odd:
    print(2 ** (N-1))
else:
    print(0 if P else 2 ** N)

Submission status: Accepted

Solution code:
import math
def naive_cmb(n, r):
    if r < 0 or r > n:
        return 0
    return (math.factorial(n) // math.factorial(r)) // math.factorial(n-r)

N, P = map(int, input().split())
A = list(map(lambda x: x%2, list(map(int, input().split()))))

ans = 0
a = A.count(1)
b = A.count(0)

if P == 1:
    for i in range(1, a+1, 2):
        ans += naive_cmb(a, i)
    ans *= 2**b
else:
    for i in range(0, a+1, 2):
        ans += naive_cmb(a, i)
    ans *= 2**b

print(ans)

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 0
    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,*A = map(int, open(0).read().split())
B = list(map(lambda x:x%2, A))
n0 = B.count(0)
n1 = B.count(1)
ans = 0
if P==0:
  for i in range(0,n0+1):
    for j in range(0,n1+1,2):
      ans += cmb(n0,i)*cmb(n1,j)
else:
  for i in range(0,n0+1):
    for j in range(1,n1+1,2):
      ans += cmb(n0,i)*cmb(n1,j)
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())))
flg = np.all(A%2==0)
print( 2**n if flg and p==0 else 0 if flg else 2**(n-1))

Submission status: Accepted

Solution code:
n, p, *a = map(int, open(0).read().split())
print([[2**n, 0][p], 2**~-n][sum(i%2 for i in a)>0])

Submission status: Accepted

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

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

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

gu = 0

ki = 0

for i in t:
    if i%2==0:
        gu += 1
    else:
        ki += 1

gukumi = 0

kikumi = 0

for i in range(1,gu+1):
    gukumi += combination(gu,i)

if p == 0:
    for i in range(2,ki+1,2):
        kikumi += combination(ki,i)
    ans = kikumi+1+gukumi
else:
    for i in range(1,ki+1,2):
        kikumi += combination(ki,i)
    ans = kikumi
    

ans += gukumi*kikumi

print(ans)

Submission status: Accepted

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

zero = ai.count(0)
one = ai.count(1)


# 再帰制限に引っかかった場合に外す
# import sys
# sys.setrecursionlimit(100000)
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)]

tmp = 2**zero
ans = 0
for i in range(one//2+1):
    if p == 0:
        if i*2 > one:
            break
        ans += cmb(one,0+i*2)
    else:
        if i*2+1 > one:
            break
        ans += cmb(one,1+i*2)
print(int(ans*tmp))

Submission status: Accepted

Solution code:
import math
def combinations(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()))
n0=0
n1=0
ans=0
for i in range(len(a)):
  if a[i]%2:
    a[i]=1
    n1+=1
  else:
    a[i]=0
    n0+=1
s=sum(a)
for i in range(0,s+1,2):
  ans+=combinations(n1,i)
  if p==1 and s==0:
    print(0)
    exit()
print(ans*(2**n0))

Submission status: Accepted

Solution code:
import numpy as np
def combinations(n,k,mod=10**9+7):
    x,y = 1,1
    for i in range(k):
        x = (x*(n-i))%mod
        y = (y*(i+1))%mod
    y = pow(y,mod-2,mod)
    return (x*y)%mod

N,P = map(int,input().split())
a = np.array(list(map(int,input().split())))%2
a1 = np.count_nonzero(a==1)
a0 = np.count_nonzero(a==0)

ans = 0
for i in range(P,a1+1,2):
    ans += combinations(a1,i)

print(ans*(2**a0))

Submission status: Accepted

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

sum = [0, 0]
for i in input().split():
    sum[int(i)%2] += 1

def nCr(n, r):
    a, b = 1, 1
    for i in range(1, r+1):
        a *= n - (i-1)
        b *= i
    return a // b

ans = 0
if P == 0:
    for i in range(N+1):
        for j in range(0, i+1, 2):
            if sum[0] < i-j: continue
            if sum[1] < j: continue
            ans += nCr(sum[0], i-j) * nCr(sum[1], j)
else:
    for i in range(N+1):
        for j in range(1, i+1, 2):
            if sum[0] < i-j: continue
            if sum[1] < j: continue
            ans += nCr(sum[0], i-j) * nCr(sum[1], j)

print(ans)

Submission status: Accepted

Solution code:
def impossible(a,b,P):
    if(b == 0 and P == 1):
        return True
    if(a == 0 and b == 1 and P == 0):
        return True
    
    return False

def func():
    N,P = map(int,input().split())

    lists = list(map(int,input().split()))
    dp = [0] * 2

    for l in lists:
        if(l % 2 == 0):
            dp[0] += 1
        else:
            dp[1] += 1
    ans = 2 ** dp[0]
    if(dp[1] > 0):
        ans *= 2 ** (dp[1] - 1)
    else:
        ans *= 1

    if(impossible(dp[0],dp[1],P)):
        ans = 0

    print(ans)
func()

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**(N-1))

resolve()

Submission status: Accepted

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

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

if odd_n == 0:
    if p == 0:
        print(2**n)
    else:
        print(0)

else:
    print(2**(n-1))

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()))
zero = 0
one = 0
for i in range(n):
    if a[i] % 2 == 0:
        zero += 1
    else:
        one += 1

if p == 0:
    count = 1
    r = 2
else:
    count = 0
    r = 1

while r <= one:
    count += comb(one, r)
    r += 2

print(2**zero*count)

Submission status: Accepted

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

from math import ceil
def comb(n,r):
    ans = 1
    for i in range(r):
        ans *= n-i
    for i in range(1,r+1):
        ans //= i
    return ans

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

if P%2==0:
    ans = 0
    for i in range(int(odd/2)+1):
        ans += comb(odd,2*i)
else:
    ans = 0
    for i in range(1,ceil(odd/2)+1):
        ans += comb(odd,2*i-1)
ans *= 2**even
print(ans)

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
a=list(map(lambda x:int(x)%2,input().split()))
a0=a.count(0)
a1=a.count(1)
base=2**a0

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

if p==1:
  ans=0
  for i in range((a1+1)//2):
    b=combinations_count(a1, 2*i+1)
    ans+=base*b
  print(ans)
else:
  ans=0
  for i in range(a1//2+1):
    b=combinations_count(a1, 2*i)
    ans+=base*b
  print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
from math import factorial
N, P = map(int, input().split())
A = list(map(int, input().split()))
odd, even = 0, 0
for i in range(N):
    if A[i] % 2 == 0:
        even += 1
    else:
        odd += 1
ans = 0
if P == 0:
    for i in range(0, odd+1, 2):
        ans += factorial(odd) // (factorial(i) * factorial(odd-i)) * 2**even
else:
    for i in range(1, odd, 2):
        ans += factorial(odd) // (factorial(i) * factorial(odd - i)) * 2**even
print(ans)

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

cnt_0 = sum([a % 2 == 0 for a in A])
cnt_1 = sum([a % 2 != 0 for a in A])

ans = 0
# 0枚食べる時
if P == 0:
    ans += 1
for k in range(1, N + 1):
    for i in range(0, k + 1):
        j = k - i
        if i > cnt_0 or j > cnt_1:
            continue
        if P == 0 and j % 2 == 0:
            ans += cmb(cnt_0, i) * cmb(cnt_1, j)
        elif P == 1 and j % 2 == 1:
            ans += cmb(cnt_0, i) * cmb(cnt_1, j)

print(ans)

Submission status: Accepted

Solution code:
#こんな筋肉みたいなコード書いたけど、考察深めればO(1)で解けます
#n,p = map(int,input().split())
#a  = list(map(int,input().split()))
#cnt = 0
#for x in a:
#   if x%2:cnt+=1
#if cnt == 0:
#    if p:ans = 0
#    else:ans = 2**n
#else:
#    ans = 2**(n-1)
#print(ans)

n,p = map(int,input().split())
a = list(map(int,input().split()))
cnt = 0
ans = 0
fact = [1]*(n+1)

for i in range(1,n+1):
    fact[i] = fact[i-1]*i
def C(x,y):
    return fact[x]//fact[y]//fact[x-y]
    
    
for x in a:
    if x %2 == 1:
        cnt += 1
if p :
    for i in range(1,n+100,2):
        if i >cnt:break
        ans += C(cnt,i)*(2**(n-cnt))
else:
    for i in range(0,n+100,2):
        if i > cnt:break
        ans += C(cnt,i)*(2**(n-cnt))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,p = map(int,input().split())
a = list(map(int,input().split()))
cnt = 0
ans = 0
fact = [1]*(n+1)

for i in range(1,n+1):
    fact[i] = fact[i-1]*i
def C(x,y):
    return fact[x]//fact[y]//fact[x-y]
    
    
for x in a:
    if x %2 == 1:
        cnt += 1
if p :
    for i in range(1,n+100,2):
        if i >cnt:break
        ans += C(cnt,i)*(2**(n-cnt))
else:
    for i in range(0,n+100,2):
        if i > cnt:break
        ans += C(cnt,i)*(2**(n-cnt))
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, P = MAP()
A = LIST()

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

for i, a in enumerate(A):
	if a%2 == 0:
		dp[i+1][0] = dp[i][0]*2
		dp[i+1][1] = dp[i][1]*2
	else:
		dp[i+1][0] = dp[i][1]+dp[i][0]
		dp[i+1][1] = dp[i][0]+dp[i][1]

print(dp[N][P])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, P = MAP()
A = LIST()

fact = [0]*(51)
fact[0] = 1

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

def Conv(n, r):
	return fact[n]//fact[r]//fact[n-r]

C = Counter([x%2 for x in A])

ans = 0
for i in range(P%2, C[1]+1, 2):
	ans += Conv(C[1], i)

ans *= pow(2, C[0])
print(ans)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
  A[i] = A[i] % 2

def ncr(n, r, p):
  num = den = 1
  for i in range(r):
    num = (num * (n - i)) % p
    den = (den * (i + 1)) % p
  return (num * pow(den, p - 2, p)) % p
p=10**9+7
odd = sum(A)
even = N- odd

ans = 0
if P == 0:
  c = 0
  for i in range(0, odd+1, 2):
    c += ncr(odd, i, p)
  ans += pow(2, even) * c

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

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
A = list(map(int, input().split()))
L = [i%2 for i in A]

odd_cnt = L.count(1)
eve_cnt = L.count(0)

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

Submission status: Accepted

Solution code:
from math import factorial


def cmb(n,r):
    return factorial(n)//(factorial(n-r)*factorial(r))


n,p=map(int,input().split())
A=list(map(int,input().split()))
A=[A[i]%2 for i in range(n)]

cnt=A.count(0)
ans=0
for i in range(p,n-cnt+1,2):
    ans +=cmb(n-cnt,i)
print(ans*(2**cnt))

Submission status: Accepted

Solution code:
from math import factorial


def cmb(n,r):
    return factorial(n)//(factorial(n-r)*factorial(r))


n,p=map(int,input().split())
A=list(map(int,input().split()))
A=[A[i]%2 for i in range(n)]

cnt=A.count(0)
B=2**cnt

ans=0
for i in range(p,n-cnt+1,2):
    ans +=cmb(n-cnt,i)
print(ans*B)

Submission status: Accepted

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

x=dict()
x[0]=0
x[1]=0
for i in range(K):
    if A[i]%2==0:
        x[0]+=1
    else:
        x[1]+=1
if x[1]==0:
    if P==0:
        print(2**K)
    else:
        print(0)
    exit()
print(2**(K-1))

Submission status: Accepted

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

    odd_cnt = 0
    even_cnt = 0

    for a in A:
        if a % 2 == 0:
            even_cnt += 1
        else:
            odd_cnt += 1
    
    odd_perm = 0
    for r in range(0,odd_cnt+1,2):
        odd_perm += n_combination(odd_cnt, r)
    
    if P == 0:
        print(odd_perm * pow(2,even_cnt))
    else:
        print(pow(2,N) - (odd_perm * pow(2,even_cnt)))
        
def n_combination(n, r):
    numer_sum = 1
    denom_sum = 1
    for i in range(r):
        numer_sum *= n - i
        denom_sum *= r - i
    
    return numer_sum // denom_sum
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
A=[int(a)%2 for a in input().split()]
odd=sum(A)
if odd==0:
    if p==1:print(0)
    else:print(2**n)
else: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()]

a_odd = [x for x in a if x % 2 == 1]

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

Submission status: Accepted

Solution code:
import sys
from math import factorial
def main():
    packages, remainder = receiveInputData()

    packages.countOddAndEven()

    even_ways = packages.calculateEvenWays()
    odd_ways_remainder0, odd_ways_remainder1 = packages.calculateOddWays()

    if remainder.isZero():
        print(even_ways * odd_ways_remainder0)
        return

    print(even_ways * odd_ways_remainder1)






class Package():
    def __init__(self, packages_list, packages_num):
        if not isinstance(packages_list, list):
            print('Package Class argument error')
            sys.exit(1)

        # 問題の制約では、1以上50以下である
        if packages_num < 1 or packages_num > 50:
            print('Package Class Restriction error')
            print(packages_num)
            sys.exit(1)

        self.packages = packages_list
        self.packages_num = packages_num

    # 中に入っているビスケットの数が偶数の袋、奇数の袋それぞれ数える
    def countOddAndEven(self):
        self.packages_num_of_odd_biscuits  = 0
        self.packages_num_of_even_biscuits = 0
        for pack_i, biscuits_num in enumerate(self.packages):
            if biscuits_num % 2 == 0:
                self.packages_num_of_even_biscuits += 1
            else:
                self.packages_num_of_odd_biscuits += 1

    # 偶数個含まれる袋の選び方は何通りかを返す
    # 袋ごとに　食べる　食べない　の２通りなので
    # m袋あれば　2^m通り
    def calculateEvenWays(self):
        return 2 ** self.packages_num_of_even_biscuits

    def calculateOddWays(self):
        count_combination_list = self.calculateCombination(self.packages_num_of_odd_biscuits)

        # あまりPが0の場合
        # 奇数個含まれる袋は、偶数個選ばなければならない
        selected_even_odds = sum(count_combination_list[::2])

        # あまりPが1の場合
        # 奇数個含まれる袋は、奇数個選ばなければならない
        selected_odd_odds = sum(count_combination_list[1::2])

        return selected_even_odds, selected_odd_odds

    def calculateCombination(self,n):
        # i番目にはnCi
        select_ways_of_odd = [1]
        for select_num in range(1,n + 1):
            n_C_i = factorial(n) // (factorial(select_num) * factorial(n - select_num))
            select_ways_of_odd.append(n_C_i)
        return select_ways_of_odd











class Remainder():
    def __init__(self, remainder_0or1):
        if not isinstance(remainder_0or1, int):
            print('Remainder Class argument error')
            sys.exit(1)

        # 問題の制約では、0か1
        if remainder_0or1 != 0 and remainder_0or1 != 1:
            print('Remainder Class Restriction error')
            sys.exit(1)

        self.remainder = remainder_0or1


    def isZero(self):
        if self.remainder == 0:
            return True
        return False


def receiveInputData():

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

    return Package(A, N), Remainder(P)

if __name__ == '__main__':
    main()

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:
    print(2**(n-1))

Submission status: Accepted

Solution code:
# Problem A - Biscuits
# 数の並びのパターンを意識する
# input
N, P = map(int, input().split())
a_list = list(map(int, input().split()))

# initialization
even_count = 0
odd_count = 0

# count
for a in a_list:
    if a%2==0:
        even_count += 1
    else:
        odd_count += 1

if even_count==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(lambda x:int(x)%2,input().split()))
DP = [[0]*1000 for i in range(N+1)]
DP[0][0] = 1
for i in range(1,N+1):
    DP[i][0] = 1
    x = A[i-1]
    if x==0:
        DP[i][1] = DP[i-1][1]
    else:
        DP[i][1] = DP[i-1][1]+DP[i-1][0]
    for j in range(2,900):
        if x==0:
            DP[i][j] = DP[i-1][j-2]+DP[i-1][j]
        else:
            DP[i][j] = DP[i-1][j-1]+DP[i-1][j]
cnt = 0
for i in range(1000):
    if i%2==P:
        cnt += DP[N][i]
print(cnt)

Submission status: Accepted

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

odd = []
even = []
for i, aa in enumerate(a):
    if aa % 2 == 0:
        even.append(aa)
    else:
        odd.append(aa)
e = len(even)
o = len(odd)
ans = 2 ** e
od_list = [1]
bunsi = 1
bunbo = 1

for i in range(1,o+1):
    bunsi *= o - i + 1
    bunbo *= i
    od_list.append(bunsi//bunbo)
even_i = od_list[::2]
odd_i = od_list[1::2]
# print(o)
# print(od_list)
if p == 0:
    print(ans * sum(even_i))
    # print(even_i)
else:
    print(ans * sum(odd_i))

Submission status: Accepted

Solution code:
# mod mでの二項係数を求める
class BiCoeff(object):
    def __init__(self, MAX, m):
        super(BiCoeff, self).__init__()
        fac = [0]*MAX
        finv = [0]*MAX
        inv = [0]*MAX

        fac[0] = 1
        fac[1] = 1
        finv[0] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2,MAX):
            fac[i] = (fac[i-1]*i)%m
            inv[i] = m - (inv[m%i] * (m//i))%m
            finv[i] = (finv[i-1] * inv[i])%m

        self.MAX = MAX
        self.m = m
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def calc(self,n,k):
        if n<k:
            return 0
        if n<0 or k<0:
            return 0
        return (self.fac[n] * (self.finv[k]*self.finv[n-k])%self.m)%self.m

n,p = map(int, input().split())
al = list(map(int, input().split()))
bicoeff = BiCoeff(10**5,10**9+7)

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

r1 = 2**even
r2 = 0
for k in range(odd+1):
    if k%2==p:
        r2 += bicoeff.calc(odd, k)
print(r1*r2)

Submission status: Accepted

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

is_odd = False
for ai in a:
    if ai % 2 == 1:
        is_odd = True
        break

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

Submission status: Accepted

Solution code:
N,P=map(int, input().split())
*A,=map(int, input().split())
p = [0,0]
for a in A: p[a&1] += 1
even,odd=p[0],p[1]

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import factorial
N, P = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: x % 2, A))
counter = {'0': 0, '1': 0}
for a in A:
    c_a = str(a)
    counter[c_a] += 1
#print(counter)
ans = 2 ** counter['0']
tmp = factorial(counter['1'])
tmp_ans = 0
for i in range(0 + P,counter['1'] + 1,2):
    tmp_ans += tmp / factorial(i) / factorial(counter['1'] - i)
print(int(tmp_ans * ans))

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)
    if P == 0:
        odd = 2**(c[1]-1) if c[1] > 0 else 0
        even = 2**c[0]
        if 0 < odd:
            even *= odd
    else:
        odd = 2**(c[1]-1) if c[1] > 0 else 0
        even = 2**c[0]
        odd *= even
    print(odd if P == 1 else even)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import factorial
def cmb(n,r):
    if n-r<0:
        return 0
    else:
        return factorial(n) // factorial(r) // factorial(n - r)
        

n,p,*a=map(int,open(0).read().split())

odd=sum(i%2 for i in a)
even=n-odd


x=sum(cmb(even,i)for i in range(even+1))
y=sum(cmb(odd,i)for i in range(p,odd+1,2))
print(x*y)

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)
    odd = 2**(c[1]-1) if c[1] > 0 else 0
    even = 2**c[0]
    if 0 < odd:
        even *= odd
    print(odd*2**c[0] if P == 1 else even)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np


def nCr(n, r, mod = 10**9+7):
    r = min(n-r, r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


n, p = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int)
A %= 2

odd = (A == 1).sum()
even = (A == 0).sum()

base = 2 ** even
if p == 0:
    odd_to_even = 0
    for select in range(0, odd+1, 2):
        pattern = nCr(odd, select)
        odd_to_even += pattern

    print(base * odd_to_even)

else:
    odd_to_odd = 0
    for select in range(1, odd+1, 2):
        pattern = nCr(odd, select)
        odd_to_odd += pattern

    print(base * odd_to_odd)