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

def comb(n, r):
    ans = 1
    if n < 2*r:
        r = n - r
    for i in range(r):
        ans *= (n - i)
        ans //= (i + 1)
    return ans

ev, od = 0, 0
for i in a:
    if i%2 == 0:
        ev += 1
    else:
        od += 1
ans = 0
if p == 0:
    for i in range(0, od+1, 2):
        for j in range(ev+1):
            ans += comb(od, i)*comb(ev, j)
else:
    for i in range(1, od+1, 2):
        for j in range(ev+1):
            ans += comb(od, i)*comb(ev, j) 
print(ans)

Submission status: Accepted

Solution code:
N, P = list(map(int, input().split()))
A = list(map(int, input().split()))
NO = 0
NE = 0
for a in A:
    if a % 2 == 0:
        NE += 1
    else:
        NO += 1


def comb(n, k):
    w = min(n - k, k)
    if n <= 1 or w == 0:
        return 1
    a = n
    for i in range(n - 1, n - w, -1):
        a *= i
    b = 1
    for i in range(2, w + 1):
        b *= i
    return a // b


e = 2 ** NE
o = 0
for i in range(P, NO + 1, 2):
    o += comb(NO, i)
if P == 0:
    res = e * o if o > 0 else e
else:
    res = o * e if e > 0 else o
print(res)

Submission status: Accepted

Solution code:
import math
n,p=map(int,input().split())
c=0
for m in map(int,input().split()):
  if m%2==0:c+=1
d=2**(c)

e=0
for i in range(p,n-c+1,2):
  
  k=math.factorial(n-c) // (math.factorial(n-c - i) * math.factorial(i))
  k=max(k,1)
  e+=k

print(d*e)

Submission status: Accepted

Solution code:
import math
N, P = map(int, input().split())
A = list(map(int, input().split()))
div = 0
for a in A:
  if a % 2 == 1:
    div += 1

ans = 0
mlt = 2 ** (N-div)
if P == 0:
  for i in range(0, div+1, 2):
    cmb = math.factorial(div) // (math.factorial(div-i) * math.factorial(i))
    ans += cmb * mlt
else:
  for i in range(1, div+1, 2):
    cmb = math.factorial(div) // (math.factorial(div-i) * math.factorial(i))
    ans += cmb * mlt
    
print(ans)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
As = list(map(int, input().split()))
dic = {0:0, 1:0}
for a in As:
  if a % 2 == 0:
    dic[0] += 1
  else:
    dic[1] += 1

if P == 1 and dic[1] == 0:
  print(0)
  exit()
  
rlt = 2**dic[0]
tmp = 0
for i in range(dic[1]+1):
  if i == 0:
    t = 1
  else:
    t = t*(dic[1]+1-i)//i
  if (P == 0 and i%2==0) or (P == 1 and i%2==1):
    tmp += t
      
rlt *= tmp

print(rlt)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
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 ** 9)
INF = 10**9
mod = 10**9+7

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')


def solve():
    n, p = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    o = 0
    e = 0
    for e in a:
        if e % 2:
            o += 1
        else:
            e += 1
    if o:
        print(2 ** (n-1))
    else:
        if p:
            print(0)
        else:
            print(2 ** n)
        


t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""

"""

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

dp = [0] * 5005
dp[0] = 1

for a in A:
    for i in range(5000, 0, -1):
        if i - a >= 0:
            dp[i] += dp[i - a]

print(sum(dp[i] for i in range(len(dp)) if i % 2 == P))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    N, P = [int(item) for item in input().split()]
    As = [int(item)%2 for item in input().split()]

    is_all_even = True
    for item in As:
        if item == 1:
            is_all_even = False
    
    res = 0
    if is_all_even:
        if P == 0:
            res = 2 ** N
        else:
            res = 0
    else:
        res = 2**(N-1)
    
    print(res)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def comb(n,k):
    res = 1
    for i in range(1,k+1):
        res *= (n+1-i)
        res //= i
    return res


n,p = map(int, input().split())
a = list(map(int, input().split()))
a = [ai % 2 for ai in a]
odd, even = a.count(1), a.count(0)

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

Submission status: Accepted

Solution code:
from scipy.special import comb
import numpy as np

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

A = A % 2 != 0
odd = np.sum(A)
even = N - odd
# print(A, odd, even)

ans = 0
odd_num = 0
even_num = 0
if P == 1:
    for i in range(1, odd + 1, 2):
        odd_num += comb(odd, i, exact=True)
    even_num = pow(2, even)
    ans = odd_num * even_num
else:
    for i in range(0, odd + 1, 2):
        odd_num += comb(odd, i, exact=True)
    even_num = pow(2, even)
    ans = odd_num * even_num
    # print(odd_num, even_num)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
import itertools
import math

def readInt():
  return int(input())
def readInts():
  return list(map(int, input().split()))
def readChar():
  return input()
def readChars():
  return input().split()

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

def cula(a):
  ans = 0
  for i in range(a+1):
    ans+=comb(a,i)
  return ans

def culb(b):
  ans = 0
  for i in range(p,b+1,2):
    ans+=comb(b,i)
  return ans

n,p = readInts()
a = [0,0]
for i in readInts():
  if i%2==0:
    a[0]+=1
  else:
    a[1]+=1

print(cula(a[0])*culb(a[1]))

Submission status: Accepted

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

# In[6]:


import math


# In[7]:


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


# In[15]:


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


# In[16]:


even_cnt = sum([1 for x in A if x%2 == 0])
odd_cnt = sum([1 for x in A if x%2 != 0])
if P == 0:
    ans1 = 2**even_cnt
    ans2 = 0
    for i in range(0,odd_cnt+1,2):
        ans2 += comb(odd_cnt,i)
else:
    ans1 = 2**even_cnt
    ans2 = 0
    for i in range(1,odd_cnt+1,2):
        ans2 += comb(odd_cnt,i)
print(ans1*ans2)


# In[ ]:

Submission status: Accepted

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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

N, P = two_int()
A=many_int()

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

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

even_count=0
for i in range(even+1):
    even_count += comb(even, i)

odd_count=0
if P==1:
    for i in range(1, odd+1, 2):
        odd_count += comb(odd, i)
elif P==0:
    for i in range(2, odd+1, 2):
        odd_count += comb(odd, i)
    odd_count+=1

if odd_count != 0 and even_count != 0:
    print(odd_count * even_count)
else:
    print(odd_count)

Submission status: Accepted

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

import sys
import numpy as np
from itertools import combinations
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, P, *A, = map(int, read().split())

n_odd = 0
n_even = 0
for a in A:
    if a % 2 == 0:
        n_even += 1
    else:
        n_odd += 1

if n_even == N:
    if P == 0:
        print(pow(2, N))
    else:
        print(0)
else:
    print(pow(2, (N - 1)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#AGC017-A
from math import factorial
def nCr(n,r):
    return factorial(n) / factorial(r) / factorial(n - r)
n,p = map(int,input().split())
a = list(map(int,input().split()))
even = 0
odd = 0
for i in a:
    if i % 2 == 0:
        even += 1
    else:
        odd += 1

#偶数
if p == 0:
    temp = 0
    for i in range(0,odd+1,2):
        temp += nCr(odd,i)
    print(int(2**even * temp))
#奇数
else:
    temp = 0
    for i in range(1,odd+1,2):
        temp += nCr(odd,i)
    print(int(2**even * temp))

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def comb(n, k):

    k = min(k, n - k)

    m = 1
    for i in range(n, n - k, -1):
        m *= i

    n = 1
    for i in range(1, k + 1):
        n *= i

    return m // n


def main():
    N, P = in_nn()
    A = in_nl()

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

    #print(odd, even)

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# AGC017A

def f(n, p, a):
    odd = sum(i % 2 for i in a)
    if odd == 0:
        if p == 0:
            return 2**n
        elif p == 1:
            return 0
    else:
        return 2**(n-1)
        
n, p = map(int, input().split())
a = list(map(int, input().split()))
print(f(n, p, a))

Submission status: Accepted

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

def nCr(n, r):
    r = min(r, n-r)

    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i

    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i

    return numerator // denominator

x = sum(A) % 2

o = 0
e = 0

for a in A:
    if a % 2 == 0:
        e += 1
    else:
        o += 1

z = 2**e

y = 1
if P == 0:
    y = 0
if x:
    y ^= 1
res = 0
for i in range(y, o+1, 2):
    res += nCr(o, i)
    
print(res*z)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
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 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10
	
N, P = MAP()
A = LIST()

dp = [[0, 0] for _ in range(N+1)]
dp[0][0] = 1
dp[0][1] = 0  #dp[0]は一個も選ばないときのP=0,P=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, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
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 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10
	
#階乗#
lim = 50  #必要そうな階乗の限界を入力
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod

#階乗の逆元#
fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


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

dp = [[0, 0] for _ in range(N+1)]
dp[0][0] = 1
dp[0][1] = 0  #dp[0]は一個も選ばないときのP=0,P=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, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
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 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10
	
#階乗#
lim = 50  #必要そうな階乗の限界を入力
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod

#階乗の逆元#
fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


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

if any([x%2 for x in A]):
	print(pow(2, N-1))
else:
	print(pow(2, N) if P == 0 else 0)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
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 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10
	
#階乗#
lim = 50  #必要そうな階乗の限界を入力
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod

#階乗の逆元#
fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


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

a = [x%2 for x in A]
cnt_0 = a.count(0)
cnt_1 = a.count(1)

ans = 0

for i in range(P%2, cnt_1+1, 2):
	ans += C(cnt_1, i)

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

Submission status: Accepted

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

fac = [1]*(n+1)
for i in range(2,n+1): fac[i] = fac[i-1]*i
def comb(n,k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return fac[n]//(fac[k]*fac[n-k])

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

cnte = cnto = 0
for i in range(even+1): cnte += comb(even,i)
for i in range(odd+1)[p::2]: cnto += comb(odd,i)
print(cnte*cnto)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
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 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10
	
#階乗#
lim = 50  #必要そうな階乗の限界を入力
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod

#階乗の逆元#
fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


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

a = [x%2 for x in A]
cnt_0 = a.count(0)
cnt_1 = a.count(1)

ans = 2**cnt_0

if P == 0:
	c = 0
	for i in range(cnt_1//2 + 1):
		c += C(cnt_1, 2*i)
	print(ans*c)
elif P == 1:
	c = 0
	for i in range((cnt_1-1)//2 + 1):
		c += C(cnt_1, 2*i+1)
	print(ans*c)

Submission status: Accepted

Solution code:
def ncr(n, r):
    if n < r: return 0
    r = min(r, n - r)
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + i + 1 for i in range(r)]
    denominator = [i + 1 for i 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 *= numerator[k]
    return int(result)


n, p = map(int, input().split())
a = list(map(int, input().split()))
# ans = 0
# for maskN in range(1 << n):
#     # print(maskN)
#     tmp = 0
#     for i in range(n):
#         if (maskN >> i & 1 == 1):
#             tmp += a[i]
#     if tmp % 2 == p:
#         ans += 1

# print(ans)

dic = {'odd': 0, 'even': 0}

for i in a:
    if i % 2 == 0:
        dic['even'] += 1
    else:
        dic['odd'] += 1

even = 0
odd = 0
# 偶数個の組み合わせ総数
for i in range(dic['even'] + 1):
    even += ncr(dic['even'], i)

if p == 0:
    for i in range(0, dic['odd'] + 1, 2):
        odd += ncr(dic['odd'], i)

else:
    for i in range(1, dic['odd'] + 1, 2):
        odd += ncr(dic['odd'], i)

print(odd * even)

Submission status: Accepted

Solution code:
from math import factorial

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

ev=len(even)
od=len(odd)
odd_sum=0

for i in range(od+1):
    if i%2==p and i<=od:
        odd_sum+=(factorial(od)//(factorial(od-i)*factorial(i)))

print(odd_sum*(2**ev))

Submission status: Accepted

Solution code:
import random as rng
import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def dump_impl(*objects):
    print(*objects, file=sys.stderr)


def dump_dummy(*objects):
    pass


dump = dump_impl if "DEBUG" in sys.argv else dump_dummy


def odd(n): return n & 1


def even(n): return not odd(n)


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


N, P = map(int, input().split())
A = [int(n) % 2 for n in input().split()]
cnt0 = len([a for a in A if a == 0])
cnt1 = len([a for a in A if a == 1])
ans = 0
if odd(P):
    for i in range(cnt1 + 1):
        if odd(i):
            ans += comb(cnt1, i)
else:
    for i in range(cnt1 + 1):
        if even(i):
            ans += comb(cnt1, i)
ans *= pow(2, cnt0)
print(ans)

Submission status: Accepted

Solution code:
import random as rng
import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def dump_impl(*objects):
    print(*objects, file=sys.stderr)


def dump_dummy(*objects):
    pass


dump = dump_impl if "DEBUG" in sys.argv else dump_dummy


def odd(n): return n & 1


def even(n): return not odd(n)


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


if __name__ == '__main__':
    N, P = map(int, input().split())
    A = [int(n) % 2 for n in input().split()]
    cnt0 = len([a for a in A if a == 0])
    cnt1 = len([a for a in A if a == 1])
    ans = 0
    if odd(P):
        for i in range(cnt1 + 1):
            if odd(i):
                ans += comb(cnt1, i)
    else:
        for i in range(cnt1 + 1):
            if even(i):
                ans += comb(cnt1, i)
    ans *= pow(2, cnt0)
    print(ans)

Submission status: Accepted

Solution code:
import random as rng
import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def dump_impl(*objects):
    print(*objects, file=sys.stderr)


def dump_dummy(*objects):
    pass


dump = dump_impl if "DEBUG" in sys.argv else dump_dummy


def odd(n): return n & 1


def even(n): return not odd(n)


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


def main():
    N, P = map(int, input().split())
    A = [int(n) % 2 for n in input().split()]
    cnt0 = len([a for a in A if a == 0])
    cnt1 = len([a for a in A if a == 1])
    ans = 0
    if odd(P):
        for i in range(cnt1 + 1):
            if odd(i):
                ans += comb(cnt1, i)
    else:
        for i in range(cnt1 + 1):
            if even(i):
                ans += comb(cnt1, i)
    ans *= pow(2, cnt0)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import random as rng
import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
sys.setrecursionlimit(10**9)


def dump_impl(*objects):
    print(*objects, file=sys.stderr)


def dump_dummy(*objects):
    pass


dump = dump_impl if "DEBUG" in sys.argv else dump_dummy


def odd(n): return n & 1


def even(n): return not odd(n)


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


N, P = map(int, input().split())
A = [int(n) % 2 for n in input().split()]
cnt0 = len([a for a in A if a == 0])
cnt1 = len([a for a in A if a == 1])
ans = 0
if odd(P):
    for i in range(cnt1 + 1):
        if odd(i):
            ans += comb(cnt1, i)
else:
    for i in range(cnt1 + 1):
        if even(i):
            ans += comb(cnt1, i)
ans *= pow(2, cnt0)
print(ans)

Submission status: Accepted

Solution code:
import random as rng
import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
sys.setrecursionlimit(10**9)


def dump_impl(*objects):
    print(*objects, file=sys.stderr)


def dump_dummy(*objects):
    pass


dump = dump_impl if "DEBUG" in sys.argv else dump_dummy


def odd(n): return n & 1


def even(n): return not odd(n)


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


N, P = map(int, input().split())
A = [int(n) % 2 for n in input().split()]
cnt0 = len([a for a in A if a == 0])
cnt1 = len([a for a in A if a == 1])
ans = 0
if odd(P):
    for i in range(cnt1 + 1):
        if odd(i):
            ans += comb(cnt1, i)
else:
    for i in range(cnt1 + 1):
        if even(i):
            ans += comb(cnt1, i)
ans *= pow(2, cnt0)
print(ans)

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
a=list(map(lambda x:int(x)%2,input().split()))
on=a.count(1)
ze=a.count(0)
ans=0
if on==0:
    if p==0:
        print(2**n)
        exit()
    if p==1:
        print(0)
        exit()
    
print(2**(n-1))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
from collections import defaultdict
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, P = map(int, readline().split())
    A = list(map(int, readline().split()))
    odd = 0
    even = 0
    for a in A:
        if a&1:
            odd += 1
        else:
            even += 1

    fact = [1, 1]
    for i in range(2, odd + 1):
        fact.append(fact[-1] * i)

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from scipy.special import comb
import functools
import operator

"""def sum(l):
    result = functools.reduce(operator.mul, l)
    return result"""

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

N, P = nm()
A = nl()
even = 0
odd = 0
for a in A:
    if a % 2 == 0:
        even += 1
    else:
        odd += 1
if P == 0:
    ans = sum([comb(even, i, exact=True) for i in range(0, even+1)]) * sum([comb(odd, i, exact=True) for i in range(0, odd+1, 2)])
else:
    ans = sum([comb(even, i, exact=True) for i in range(0, even+1)]) * sum([comb(odd, i, exact=True) for i in range(1, odd+1, 2)])
print(ans)

Submission status: Accepted

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

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
for a in A:
    if a%2:
        odd += 1

all_c = 0
for i in range(n+1):
    all_c += cmb(n, i)

odd_c = 0
for i in range(-(-odd//2)):
    #print(odd,"C",2*i+1)
    odd_c += cmb(odd, 2*i+1)
#print("奇数個の組", odd_c)

even_c = 0
for i in range(n-odd+1):
    even_c += cmb(n-odd, i)

if p == 1:
    print(odd_c*even_c)
else:
    print(all_c - odd_c*even_c)

Submission status: Accepted

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

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

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

print(res)