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

N = 10**3
C = [[0]*(N+1) for i in range(N+1)] #C[n][k] > nCk

for i in range(N+1):
    for j in range(i+1):
        if j == 0 or j == i:
            C[i][j] = 1
        else:
            C[i][j] = C[i-1][j-1]+C[i-1][j]

def cmb3(n, k):
    return C[n][k]

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

if p == 0:
    ans = 0
    for i in range(o+1):
        if i%2 == 1:
            continue
        else:
            ans += cmb3(o, i)
    ans *= 2**e
    print(ans)
else:
    ans = 0
    for i in range(o+1):
        if i%2 == 0:
            continue
        else:
            ans += cmb3(o, i)
    ans *= 2**e
    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]%=2
o=a.count(1)
z=n-o
if o==0:
  if p==0:print(2**z)
  else:print(0)
else:
  print(2**(n-1))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def linear_nCk(n,k):
    a = [1]*(k+1)
    for i in range(1,k+1):
        a[i] = a[i-1]*(n-k+i)//i
    return a[-1]

N,P = LI()
A = LI()

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

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

Submission status: Accepted

Solution code:
N, P=map(int, input().split())
A=list(map(int, input().split()))
odd=[]
even=[]
for a in A:
  if a%2==0:
    even.append(a)
  else:
    odd.append(a)
amod=len(odd)
amev=len(even)
evonly=2**amev

from math import factorial
if P==0:
  evod=0
  i=0
  while amod>=i:
    evod+=factorial(amod)//(factorial(i)*factorial(amod-i))
    i+=2
  print(evonly*evod)
else:
  evod=0
  i=1
  while amod>=i:
    evod+=factorial(amod)//(factorial(i)*factorial(amod-i))
    i+=2
  print(evonly*evod)

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())
l = list(map(int, input().split()))

o = 0
e = 0
for i in range(n):
    if l[i] % 2 == 0:
        e += 1
    else:
        o += 1

if p == 0:
    a = 0
    for i in range(e+1):
        a += comb(e, i)
    b = 0
    for i in range(0, o+1, 2):
        b += comb(o, i)
    print(a*b)

else:
    a = 0
    for i in range(e+1):
        a += comb(e, i)
    b = 0
    for i in range(1, o+1, 2):
        b += comb(o, i)
    print(a*b)

Submission status: Accepted

Solution code:
import itertools
n,p = map(int,input().split())
a = list(map(lambda x:int(x)&1,input().split()))
cnt0 = a.count(0)
cnt1 = n - cnt0
if p==0 and cnt0==n:
    print(2**n)
elif p==1 and cnt0==n:
    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()))
cnt0 = a.count(0)
cnt1 = n-cnt0
if cnt0==n and p==0:
    print(2**n)
elif cnt0==n and p==1:
    print(0)
else:
    print(2**(n-1))

Submission status: Accepted

Solution code:
def m():
    N, P = map(int, input().split())
    A = list(map(int, input().split()))
    Even = [a for a in A if a % 2 == 0]
    Odd = [a for a in A if a % 2 == 1]
    if P == 1 and len(Odd) == 0:
        return 0

    if len(Odd) == 0:
        return pow(2, len(Even))
    else:
        return pow(2, N-1)


print(m())

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
A=[i%2 for i in map(int,input().split())]
A0=A.count(0)
A1=A.count(1)
if p==1 and A1==0:
    print(0)
elif p==0 and A1==0:
    print(2**A0)
else:
    print((2**A0)*(2**A1)//2)

Submission status: Accepted

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

f = 0
for a in A:
    if a%2:
        f = 1
        break

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

Submission status: Accepted

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

check = all(a%2 == 0 for a in A)
ans = 0
if check and p == 0:
  ans = 1 << n
if not check:
  ans = 1 << (n-1)
print(ans)

Submission status: Accepted

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

cnt = 0
for num in a:
    if num % 2 == 1:
        cnt += 1

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

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

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

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,P = IL()
A = IL()
A = [a%2 for a in A]
dic = Counter(A)
if P == 0:
  A = dic[0]
  B = dic[1]
  temp = 0
  for i in range(B+1)[::2]:
    temp += nCr(B,i)
  print(temp*pow(2,A))
else:
  A = dic[0]
  B = dic[1]
  temp = 0
  for i in range(B+1)[1::2]:
    temp += nCr(B,i)
  print(temp*pow(2,A))

Submission status: Accepted

Solution code:
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
com = [[0] * 55 for i in range(55)]
com[0][0] = 1
for i in range(1,55):
    com[i][0] = 1
    for j in range(1,55):
        com[i][j] = com[i-1][j-1] + com[i-1][j]
eval = 0
for i in range(even + 1):
    eval += com[even][i]
oval = 0

if P == 0:
    for i in range(odd+1):
        if i % 2 == 0:
            oval += com[odd][i]
else:
    for i in range(odd + 1):
        if i % 2 == 1:
            oval += com[odd][i]
print(eval * oval)

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
sys.setrecursionlimit(int(pow(10,6)))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]
# @lru_cache(None)

n,p=l()
A=l()
o=e=0
for i in range(n):
    if(A[i]%2):
        o+=1
    else:
        e+=1
if(o):
    print(2**(n-1))
else:
    if(p):
        print(0)
    else:
        print(2**n)

Submission status: Accepted

Solution code:
# AGC017 A Biscuits

n, p = map(int, input().split())
a_list = [int(x)%2 for x in input().split()]

dp = [[0] * 2 for x in range(n+1)]
if a_list[0] == 0:
    dp[0][0] = 1
else:
    dp[0][1] = 1

for i in range(n):
    _a = a_list[i]
    if _a == 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][1]+dp[i][0]
        
print(dp[n][p])

Submission status: Accepted

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

n,p = map(int,input().split())
al = list(map(int,input().split()))
even = 0
odd = 0
for a in al:
  if a%2 == 0:
    even += 1
  else:
    odd += 1
if p == 1 and odd == 0:
  print(0)
  exit()
ans1 = 2**even
ans2 = 0
if p == 0:
  t = 0
  while t <= odd:
    ans2 += comb(odd,t)
    t += 2
else:
  k = 1
  while k <= odd:
    ans2 += comb(odd,k)
    k += 2
print(ans1*ans2)

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:
import numpy as np
n,p = map(int, input().split())
alist = map(int, input().split())
x = np.array([[2,0],[0,2]])
y = np.array([[1,1],[1,1]])
ans = np.array([1,0])
for a in alist:
  if a%2 == 0:
    ans = np.dot(x,ans)
  if a%2 == 1:
    ans = np.dot(y,ans)
print(ans[p])

Submission status: Accepted

Solution code:
import sys
N, P = map(int, sys.stdin.readline().rstrip().split())
A = list(map(int, sys.stdin.readline().rstrip().split()))

kisu = 0
gusu = 0
for a in A:
    if a % 2 == 1:
        kisu += 1
    else:
        gusu += 1

total = 2 ** N # 全場合の数
if kisu == 0:
    ans = 2 ** gusu
else:   
    ans = (2 ** gusu) * (2 ** (kisu - 1)) # 偶数になる場合の数

if P == 0:
    print(ans)
else:
    print(total - ans)

Submission status: Accepted

Solution code:
import sys
N, P = map(int, sys.stdin.readline().rstrip().split())
A = list(map(int, sys.stdin.readline().rstrip().split()))

kisu = 0
gusu = 0
for a in A:
    if a % 2 == 1:
        kisu += 1
    else:
        gusu += 1

total = 2 ** N # 全場合の数

# 階乗の事前計算
x = [1]
res = 1
for i in range(1, N + 1):
    res *= i
    x.append(res)

def cmb(n, r):
    return x[n] // (x[r] * x[n - r])

ans = 0 # 偶数になる場合の数

for k in range(kisu + 1):
    if k % 2 == 0:
        # 奇数が偶数個（0個含む） + 偶数が0個以上
        ans += cmb(kisu, k) * (2 ** gusu)

if P == 0:
    print(ans)
else:
    print(total - ans)

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
a=list(map(int,input().split()))
k=0
g=0
for i in range(n):
    if a[i]%2==0:
        g+=1
    else:
        k+=1
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
numg=0
numk=0
if p==0:
    for i in range(k//2+1):
        numk+=cmb(k,i*2)
    for i in range(g+1):
        numg+=cmb(g,i)
    print(numk*numg)
else:
    for i in range((k+1)//2):
        numk+=cmb(k,i*2+1)
    for i in range(g+1):
        numg+=cmb(g,i)
    print(numk*numg)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
n = 50
fact = [0 for _ in range(n)]
invfact = [0 for _ in range(n)]
fact[0] = 1
for i in range(1, n):
    fact[i] = fact[i - 1] * i % MOD

invfact[n - 1] = pow(fact[n - 1], MOD - 2, MOD)

for i in range(n - 2, -1, -1):
    invfact[i] = invfact[i + 1] * (i + 1) % MOD
def nCk(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return fact[n] * invfact[k] * invfact[n - k] % MOD

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# from scipy.special import comb
from scipy.misc import comb

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

num_evens = len([a for a in as_ if a % 2 == 0])
num_odds = len([a for a in as_ if a % 2 == 1])

counts = 0
if p == 0:
    # 全部で偶数枚食べる = 偶数枚の袋 a 個 + 奇数枚の袋 b = 2k 個
    # 0袋食べる場合も OK.
    counts += 1
    # 1袋以上食べる場合
    for i in range(1, n + 1):
        # 全部で i 袋食べるとする i = 1 〜 n
        for a in range(i + 1):
            # そのうち偶数枚の袋を a 個食べる方法
            even_ways = comb(num_evens, a, exact=True)
            # 奇数枚の袋は (i - a) 個食べるが、それは偶数でなければならない
            b = (i - a)
            if b % 2 == 1 or b < 0:
                continue
            else:
                odd_ways = comb(num_odds, b, exact=True)

            counts += even_ways * odd_ways

else:
    # 全部で奇数枚食べる = 偶数枚の袋 a 個 + 奇数枚の袋 b = 2k + 1個 (k >= 0)
    # 奇数の袋は0ではいけない (k >= 0)
    # 0袋食べるのはダメ
    # 1袋以上食べる場合
    for i in range(1, n + 1):
        # 全部で i 袋食べるとする
        for b in range(0, i + 1):
            # 奇数枚の袋を b = 2k + 1 個食べる
            if b % 2 == 0:
                continue
            # すると偶数枚の袋は a = i - b 個食べる
            a = i - b
            if a < 0:
                continue

            odd_ways = comb(num_odds, b, exact=True)
            even_ways = comb(num_evens, a, exact=True)
            counts += even_ways * odd_ways

print(counts)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, P = [int(x) for x in input().strip().split()]
    A = [int(x) for x in input().strip().split()]
    odd = len([1 for a in A if a % 2])
    even = len([1 for a in A if a % 2 == 0])
    nCr_ = {}
    def nCr(n, r):
        r = min(n-r, r)
        if r == 0:
            return 1
        if (n, r) in nCr_:
            return nCr_[(n, r)]

        ret1 = 1
        ret2 = 1
        for r in range(1, r+1):
            ret1 *= n - r + 1
            ret2 *= r
        nCr_[(n, r)] = ret1 // ret2
        return nCr_[(n, r)]

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    odd = 0
    even = 0
    ans = 0
    def comb(n, r):
        return math.factorial(n) // math.factorial(r) // math.factorial(n - r)
    for a in A:
        if a % 2 == 0:
            even += 1
        else:
            odd += 1

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,P = map(int, input().split())
A = list(map(int, input().split()))
in_odd = False
for i in range(N):
    if A[i]%2:
        in_odd = True
        break
if not in_odd:
    if P:
        print(0)
    else:
        print(2**N)
else:
    print(2**(N-1))

Submission status: Accepted

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

odds, evens = 0, 0

for i in A:
    if i & 1:
        odds += 1
        
    else:
        evens += 1

from math import factorial

if P == 0:
    ans = 0
    fo = factorial(odds)
    for r in range(0, odds + 1, 2):
        ans += fo // (factorial(odds - r) * factorial(r))
    ans *= 2**evens

else:
    ans = 0
    fo = factorial(odds)
    for r in range(1, odds + 1, 2):
        ans += fo // (factorial(odds - r) * factorial(r))

    ans *= 2**evens
print(ans)

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
import math

n,p = iim()
A = iil()

if n > 1:
    even = 0
    odd = 0
    for i in A:
        if i%2 == 0:
            even += 1
        else:
            odd += 1
    if odd > 0:
        p0 = 2**(odd-1)
        print(2**even*p0)
    else:
        print(2**even if p == 0 else 0)
else:
    if p == 0:
        print(2 if A[0]%2 == p else 0)
    else:
        print(1 if A[0]%2 == p else 0)

Submission status: Accepted

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

A = [a % 2 for a in A]

acc = [1] * 60
for i in range(60):
  if i == 0:
    continue
  acc[i] = acc[i-1] * i

odd = sum(A)
even = N - odd

ans = 0
if P == 0:
  # 奇数から偶数個
  j = 0
  for i in range(0,odd+1,2):
    j += acc[odd] // (acc[odd-i] * acc[i])

else:
  # 奇数から奇数個
  j = 0
  for i in range(1,odd+1,2):
    j += acc[odd] // (acc[odd-i] * acc[i])
  
ans = 0
for i in range(even+1):
  k = acc[even] // (acc[even-i] * acc[i])
  ans += k * j
  
print(ans)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
a = list(map(int, input().split()))
cnt = [0] * 2
for num in a:
    cnt[num % 2] += 1

if cnt[1] == 0:
    if p == 0:
        print(2 ** n)
    else:
        print(0)

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

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce
from operator import mul


def ncr(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


N, P = list(map(int, input().split()))
A = Counter(list(map(lambda x: int(x) % 2, input().split())))
ans = 2 ** A[0]
if P:
    print(ans * sum(ncr(A[1], i) for i in range(1, A[1] + 1, 2)))
else:
    print(ans * sum(ncr(A[1], i) for i in range(0, A[1] + 1, 2)))

Submission status: Accepted

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
num_pack, mod = map(int,input().split())
pack_ls = list(map(int, input().split()))
num_pack_0 = 0
num_pack_1 = 0
for i in range(num_pack):
    if pack_ls[i] % 2 == 0:
        num_pack_0 += 1
    else:
        num_pack_1 += 1

if mod == 1:
    pattern_0 = 2 ** num_pack_0
    pattern_1 = 0
    i = 1
    while i <= num_pack_1:
        pattern_1 += combinations_count(num_pack_1, i)
        i += 2
    ans = pattern_0 * pattern_1
else:
    pattern_0 = 2 ** num_pack_0
    pattern_1 = 0
    i = 0
    while i <= num_pack_1:
        pattern_1 += combinations_count(num_pack_1, i)
        i += 2
    ans = pattern_0 * pattern_1

print(ans)

Submission status: Accepted

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

resZero = resOne = 0
for a in A:
    if a % 2 == 0:
        resZero += 1
    else:
        resOne += 1

if resOne == 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()))
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

g = 0
k=0
for i in a:
    if i%2:
        k+=1
    else:
        g+=1
if p == 0:
    x = 2**g - 1
    y = 0
    for i in range(2,k+1,2):
        y += cmb(k,i)
    ans = y*x + x + y +1
    print(ans)
else:
    x = 2**g-1
    y = 0
    for i in range(1,k+1,2):
        y += cmb(k,i)
    print(y*x+y)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
from itertools import combinations_with_replacement

n, p = map(int, input().split())
A = list(map(int, input().split()))
odd = []
even = []


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


for a in A:
    if a % 2 == 0:
        even.append(a)
    else:
        odd.append(a)
even_count = []
for i in range(len(even)+1):
    even_count.append(combinations_count(len(even), i))
odd_odd_count = []
odd_even_count = []
for i in range(len(odd)+1):
    cnt = combinations_count(len(odd), i)
    if i % 2 == 1:
        odd_odd_count.append(cnt)
    else:
        odd_even_count.append(cnt)
ans = 0
if p == 0:
    for i in even_count:
        for j in odd_even_count:
            ans += i*j
else:
    for i in even_count:
        for j in odd_odd_count:
            ans += i*j

print(ans)

Submission status: Accepted

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

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

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

print(dp[N][P])

Submission status: Accepted

Solution code:
import sys
import math

N, P = map(int, sys.stdin.readline().strip().split())
A = map(int, sys.stdin.readline().strip().split())


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

evens = 0
odds = 0
for a_i in A:
    if a_i % 2 == 0:
        evens += 1
    else:
        odds += 1

# 偶数の服からa個、奇数の袋から2b個取れば良い
if P == 0:
    ans = 2**(evens)
    tmp = 0
    for i in range(0, odds+1, 2):
        tmp += nCr(odds, i)
    ans *= tmp
# 偶数の服からa個、奇数の袋から2b+1個取れば良い
else:
    ans = 2**(evens)
    tmp = 0
    for i in range(1, odds+1, 2):
        tmp += nCr(odds, i)
    ans *= tmp

print(ans)

Submission status: Accepted

Solution code:
N,P=map(int,input().split())
A=list(map(int,input().split()))
g=k=0
for i in A:
    if i%2:
        k+=1
    else:
        g+=1
a=0
from math import factorial
if P:
    for i in range(1,k+1,2):
        a+=factorial(k)//factorial(i)//factorial(k-i)
else:
    for i in range(0,k+1,2):
        a+=factorial(k)//factorial(i)//factorial(k-i)
print(a*pow(2,g))

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

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

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    def fast_pow(num, kata, mod):
        if kata == 0:
            return 0

        res = 1
        while kata > 0:
            if kata & 1 == 1:
                res = res * num % mod
            num = num * num % mod

            kata >>= 1
        return res

    def choose(l, r):
        res = 1
        fac = 1
        for j in range(r):
            res *= l - j
            fac *= j + 1
        return res // fac

    n, p = ns()
    a = na()

    cnt = [0, 0]

    for ai in a:
        if ai % 2:
            cnt[1] += 1
        else:
            cnt[0] += 1

    zero_choice = 2 ** cnt[0]
    one_choice = 0
    for i in range(p, cnt[1] + 1, 2):
        one_choice += choose(cnt[1], i)

    print(zero_choice * one_choice)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May 30 17:31:55 2020

@author: NEC-PCuser
"""

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

gusu = 0
kisu = 0

for i in A:
    if i % 2 == 0:
        gusu += 1
    else:
        kisu += 1

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

Submission status: Accepted

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

for i in A:
    if i % 2 == 0:
        even += 1
    else:
        odd += 1
#print(even,odd)

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

#print("0,0 = ", comb(0,0))

if P == 0:
    ans = 0
    for x in range(odd+1):
        #print(odd, x)
        if x % 2 == 0:
            ans += comb(odd,x)
    ans *= 2**even
    print(ans)
else:
    ans = 0
    for x in range(odd+1):
        if x % 2 == 1:
            if odd != 0:
                ans += comb(odd,x)
    ans *= 2**even
    print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
n -= 1
dat = list(map(int, input().split()))
iseven = True
for i in range(len(dat)):
    if dat[i] %2 == 1:
        iseven = False
if iseven:
    if m == 0:
        print(2**(n+1))
    else:
        print(0)
else:
    if n == 0:
        print(0)
    else:
        print(pow(2, n))

Submission status: Accepted

Solution code:
N,P=map(int,input().split())
A=list(map(int,input().split()))
if all(a%2==0 for a in A):
    print(0 if P else 2**N)
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()))

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

m = len(even)
count1 = 0
for i in range(m+1):
    count1 += comb(m, i)

k = len(odd)
count2 = 0
if p == 0:
    for i in range(0, k+1, 2):
        count2 += comb(k, i)
else:
    for i in range(1, k+1, 2):
        count2 += comb(k, i)

print(count1*count2)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
ns = list(map(int, input().split()))
ns = [i % 2 for i in ns]
ans = [0, 0]
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
c = ns.count(1)
ans[1] = sum(cmb(c, i) for i in range(1, c + 1, 2)) * 2 ** (n - c)
ans[0] = 2**n - ans[1]
print(ans[p])

Submission status: Accepted

Solution code:
from math import factorial

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

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

eve = 0
odd = 0

for i in range(n):
	if a[i]%2==0:
		eve += 1
	else:
		odd += 1
		
eve_cb = 2**eve
odd_cb1 = 0
odd_cb2 = 0

if p==1:
  for i in range(1,odd+1)[::2]:
	  odd_cb1 += combinations_count(odd,i)
else:
  for i in range(0,odd+1)[::2]:
	  odd_cb2 += combinations_count(odd,i)

print(eve_cb*(odd_cb1*p + odd_cb2*(1-p)))