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 = [int(x) for x in input().split()]

odd = False
for i in range(N):
    if A[i] % 2 == 1:
        odd = True
        break

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

Submission status: Accepted

Solution code:
from math import factorial

def com(n, r):
    return fac_n // factorial(r) // factorial(n - r)


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

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

fac_n = factorial(odd)

res = 0
for r in range(P, odd+1, 2):
    res += com(odd, r)
ans = res * (2**even)

print(ans)

Submission status: Accepted

Solution code:
import functools


@functools.lru_cache(maxsize=None)
def num_counts(size, P):
    if size == 1:
        return 1 + (A[size - 1] + 1) % 2 if P == 0 else A[size - 1] % 2
    if A[size - 1] % 2 == 0:
        return num_counts(size - 1, P) * 2
    else:
        return num_counts(size - 1, P) + num_counts(size - 1, (P + 1) % 2)


if __name__ == "__main__":
    N, P = [int(x) for x in input().split(" ")]
    A = [int(x) for x in input().split(" ")]
    print(num_counts(len(A), P))

Submission status: Accepted

Solution code:
import bisect,copy,heapq,itertools,string
from collections import *
from math import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, p = MAP()
a = list(map(lambda x:int(x)%2, input().split()))
e = a.count(0) if 0 in a else 0
o = a.count(1) if 1 in a else 0

ans = 0
if(p == 0):
    for i in range(0,e+1):
        for j in range(0,o+1,2):
            comb_e = factorial(e)//factorial(i)//factorial(e-i)
            comb_o = factorial(o)//factorial(j)//factorial(o-j)
            ans += comb_e * comb_o
else:
    for i in range(0,e+1):
        for j in range(1,o+1,2):
            comb_e = factorial(e)//factorial(i)//factorial(e-i)
            comb_o = factorial(o)//factorial(j)//factorial(o-j)
            ans += comb_e * comb_o
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


M = 10**9+7 # 出力の制限
N = 10**4 # 必要なテーブルサイズ

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M

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

N = 50
f = [None]*N
v = 1
for i in range(N):
    f[i] = v
    v *= (i+1)
def cmb(n, r, M=None):
    return (f[n] // f[r] // f[n-r])

n0 = sum(num%2==0 for num in a)
n1 = sum(num%2==1 for num in a)
ans = 0
if p==1:
    for i1 in range(1, n1+1, 2):
        ans += cmb(n1, i1)
else:
    for i1 in range(0, n1+1, 2):
        ans += cmb(n1, i1)
ans *= pow(2, n0)
print(ans)

Submission status: Accepted

Solution code:
N,P = list(map(int, input().split()))
a = list(map(int, input().split()))
num_odd = sum([i%2 == 1 for i in a])
num_even = N - num_odd
 
ce = 2 ** num_even
co = 2 ** (num_odd - 1)
if num_odd == 0:
    co = P^1
print(co * ce)

Submission status: Accepted

Solution code:
Fact=[1]
for i in range(1,50+1):
    Fact.append(Fact[-1]*i)

def nCr(n,r):
    return Fact[n]//(Fact[r]*Fact[n-r])
N,P=map(int,input().split())
A=list(map(int,input().split()))

Odd,Even=0,0
for a in A:
    if a%2:
        Odd+=1
    else:
        Even+=1

T=0
for r in range(P,Odd+1,2):
    T+=nCr(Odd,r)
print(T*(2**Even))

Submission status: Accepted

Solution code:
N,P = list(map(int, input().split()))
a = list(map(int, input().split()))
num_odd = sum([i%2 == 1 for i in a])
num_even = N - num_odd

ce = 2 ** num_even
co = 2 ** (num_odd - 1)
if num_odd == 0:
    co = P^1
print(co * ce)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
inp1, inp2 = map(int, input().split())
c = [int(i)&1 for i in input().split()]
add = sum(c)
if add:
    ans = 2**(inp1-1)
else:
    ans = 2**inp1*(1-inp2)
print(ans)

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
c = [int(i)&1 for i in input().split()]
odd = sum(c)
val = 0
if odd:
    val = 2**(a-1)
else:
    val = 2**a*(1-b)
 
print(val)

Submission status: Accepted

Solution code:
from math import factorial
def ncr(n,r):
    a=factorial(n)
    b=factorial(n-r)*factorial(r)
    return a//b
N,P=list(map(int,input().split()))
A=list(map(int,input().split()))
A=[i%2 for i in A]
zero=[i for i in A if i==0]
one=[i for i in A if i==1]
lzero=len(zero)
lone=len(one)
if lzero==0:
    if P%2==0:
        a = 0
        for i in range(2, lone+1, 2):
            a += ncr(lone, i)
        print(a+1)
    else:
        a = 0
        for i in range(1, lone+1, 2):
            a += ncr(lone, i)
        print(a)
    exit()
if lone==0:
    if P%2==0:
        print(2**lzero)
    else:print(0)
    exit()
if P%2==1:
    guu=2**lzero
    a=0
    for i in range(1,lone+1,2):
        a+=ncr(lone,i)
    print(guu*a)
else:
    guu=2**lzero
    a=0
    for i in range(0,lone+1,2):
        a+=ncr(lone,i)
    print(guu*a)

Submission status: Accepted

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

odd = 0
for v in A:
    if  v % 2:
        odd += 1 
even = N-odd
if odd != 0:
    print((2**even)*int(2**(odd-1)))
else:
    if P == 0:
        print(2**N)
    else:
        print(0)

Submission status: Accepted

Solution code:
from itertools import combinations

def readinput():
    n,p=list(map(int,input().split()))
    a=list(map(int,input().split()))
    return n,p,a


from operator import mul
from functools import reduce

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

def main(n,p,a):
    ne=0
    no=0
    for i in range(n):
        if a[i]%2==0:
            ne+=1
        else:
            no+=1
    #print('ne: {}, no: {}'.format(ne,no))

    alle=2**ne
    #print('alle: {}'.format(alle))

    allo=0
    if p==0:
        mo=0
    else:
        mo=1
    while mo<=no:
        allo+=cmb(no,mo)
        mo+=2
    #print('allo: {}'.format(allo))
    
    return alle*allo

if __name__=='__main__':
    n,p,a=readinput()
    ans=main(n,p,a)
    print(ans)

Submission status: Accepted

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

a,b=0,0
for i in A:
    if i%2==0:a +=1
    else:b +=1

cnt=0 if p==1 else 1
for i in range(p,b+1,2):
    if i==0:continue
    cnt +=factorial(b)//(factorial(i)*factorial(b-i))

print(cnt*(2**a))

Submission status: Accepted

Solution code:
import math

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

memo = [[0 for _ in range(51)] for _ in range(51)]

def c(n,k):
  if memo[n][k] != 0:
      return memo[n][k]
  if(k<=0 or n<=k):
      memo[n][k] = 1
      return 1
  else:
      ans = c(n-1, k-1) + c(n-1, k)
      memo[n][k] = ans
      return ans

for i in range(51):
  pascal_triangle.append([c(i,j) for j in range(i+1)])

Numbers_1 = 0
for i in range(N):
    Numbers_1 += A[i] % 2

Select_0_count = sum(pascal_triangle[N - Numbers_1])

ans = 0

for i in range(Numbers_1+1):
    if i % 2 == P:
        ans += pascal_triangle[Numbers_1][i] * Select_0_count

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):
    if P == 0:
        print(2**N)
    else:
        print(0)
else:
    print(2**(N-1))

Submission status: Accepted

Solution code:
from scipy.special import comb
n, p = map(int, input().split())
A = list(map(int, input().split()))
cnt_o = len([a for a in A if a%2 == 1])
cnt_e = n - cnt_o
sum_comb_o = 0  # 奇数からとる組み合わせの和
for i in range(n+1):
    if p == 0 and i%2 == 0:
        sum_comb_o += comb(cnt_o, i, exact=True)
    elif p == 1 and i%2 == 1:
        sum_comb_o += comb(cnt_o, i, exact=True)
print(2**cnt_e * sum_comb_o)

Submission status: Accepted

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

MOD = 2  # type: int


def solve(N: int, P: int, A: "List[int]"):
    if not sum([e%2 for e in A]):
        if P:
            print(0)
        else:
            print(2**N)
    else:
      print(2**(N-1))
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

n_odd=0
n_even=0

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


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

ans=0

if p==0:    
    #p=0
    for j in range(n_odd+1):
        if j%2==1:
            continue
        else:
            tmp=0
            for l in range(n_even+1):
                tmp+=cmb(n_even,l)
            
            ans+=cmb(n_odd,j)*tmp
elif p==1:
    #p=1
    for k in range(n_odd+1):
        if k%2==0:
            continue
        else:
            tmp=0
            for l in range(n_even+1):
                tmp+=cmb(n_even,l)

            ans+=cmb(n_odd,k)*tmp

print(ans)

Submission status: Accepted

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

# 全探索(奇数か偶数に全てを分ける)
evenL = []
oddL = []
for i in range(N):
    if (A[i] % 2 == 0):
        evenL.append(A[i])
    else:
        oddL.append(A[i])

even = len(evenL)
odd = len(oddL)

# 2で割った袋の枚数のあまりが1になるような組み合わせを数える
sum_odd = 0
numL = []
for i in range(odd):
    if ((i + 1) % 2 == 1):
        numL.append(i + 1)

for i in numL:
    sum_odd += (math.factorial(odd) //
                math.factorial(odd - i) // math.factorial(i))
# 全体から奇数になるような選び方を引いたら偶数になる選び方になる

# 2で割ったあまりが偶数こになる
numevenL = []
sum_even = 0
for i in range(odd):
    if ((i + 1) % 2 == 0):
        numevenL.append(i + 1)

for i in numevenL:
    sum_even += ((math.factorial(odd) //
                  math.factorial(odd - i) // math.factorial(i)))

if (P % 2 == 1):
    print(2 ** N - ((sum_even + 1) * (2 ** even)))
else:
    print((sum_even + 1) * (2 ** even))

Submission status: Accepted

Solution code:
from math import factorial
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


def main():
    n, p = LI()
    a = LI()
    even = [i for i in a if i % 2 == 0]
    odd = [i for i in a if i % 2 != 0]
    if len(odd) == 0:
        if p == 0:
            ans = 2 ** n
        else:
            ans = 0

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


main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    from operator import mul
    from functools import reduce
    def combinations_count(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 = list(map(int, input().split()))
    odd = sum([a % 2 == 1 for a in A])
    even = n - odd
    if p == 0:
        odd_sum = 0
        for i in range(0, odd + 1, 2):
            odd_sum += combinations_count(odd, i)
    else:
        if odd == 0:
            print(0)
            exit()
        else:
            odd_sum = 0
            for i in range(1, odd + 1, 2):
                odd_sum += combinations_count(odd, i)
    if even == 0:
        even_sum = 0
        print(odd_sum)
    else:
        even_sum = pow(2, even)
        print(even_sum * odd_sum)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

lst=[0,0]

for i in range(n):
    lst[a[i]%2]+=1
# print(lst)

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

tmp1=pow(2,lst[0])
tmp2=0
for i in range(lst[1]+1):
    if p==0 and i%2==0:
        tmp2+=comb(lst[1],i)
    elif p==1 and i%2==1:
        tmp2+=comb(lst[1],i)
print(tmp1*tmp2)
# print(tmp1,tmp2)

Submission status: Accepted

Solution code:
n, p = map(int ,input().split())
a = list(map(int ,input().split()))
flg_lst = []
for i in range(n):
    if a[i] % 2 == 0:
        flg_lst.append(True)
    else:
        flg_lst.append(False)
if False in flg_lst:
    print(2 ** (n - 1))
else:
    if p == 0:
        print(2 ** n)
    else:
        print(0)

Submission status: Accepted

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

Submission status: Accepted

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

length = len(a)
even = len([i for i in a if i % 2 == 0])
odd = len([i for i in a if i % 2 == 1])

if length == even and p == 1:
    print(0)
elif length == even:
    print(2 ** n)
else:
    print(2 ** n // 2)

Submission status: Accepted

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

B=[a%2 for a in A]
if sum(B)==0:
    print((P==0)*2**N)
else:
    print(2**(N-1))

Submission status: Accepted

Solution code:
import math
def comb(n, r): #comb(int, int)
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n,p = map(int,input().split())
a = list(map(int,input().split()))
a_even = 0
a_odd = 0
for i in range(n):
    if a[i]%2 == 0:
        a_even += 1
    else:
        a_odd += 1
ans = 0
if p%2 == 0:
    k = 0
    for i in range(10**10):
        if 2*i > a_odd:
            break
        k += comb(a_odd, 2*i)
    print(k*2**a_even)
else:
    k = 0
    for i in range(10**10):
        if 2*i+1 > a_odd:
            break
        k += comb(a_odd, 2*i+1)
    print(k*2**a_even)

Submission status: Accepted

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

semua_angka_genap = True
ada_angka_ganjil = False
for i in num:
  if i % 2 == 1:
    semua_angka_genap = False
    ada_angka_ganjil = True

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

if ada_angka_ganjil:
  print(2**(n-1))

Submission status: Accepted

Solution code:
import sys

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

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

A = [x & 1 for x in A]

if A.count(1):
    x = pow(2, N - 1)
else:
    x = pow(2, N)
    if P:
        x = 0
print(x)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
a = [int(i)&1 for i in input().split()]
odd = sum(a)
ans = 0
if odd:
    ans = 2**(n-1)
else:
    ans = 2**n*(1-p)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

for a in A:
  if a%2 == 1:
    print(2**(N-1))
    exit()

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

Submission status: Accepted

Solution code:
def resolve():
    N, P = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]
    odd = 0
    for a in A:
        if a % 2 == 1:
            odd += 1
    even = N - odd
    if P == 1:
        if odd > 0:
            ans = (2**even) * (2**(odd - 1))
        else:
            ans = 0
    else:
        if odd == 0:
            ans = (2**even)
        else:
            ans = (2**even) * (2**(odd - 1))
    print(ans)


resolve()

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):
    if p:
        print(0)
    else:
        print(pow(2, n))
else:
    print(pow(2, n-1))

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
A = list(map(int, input().split()))
U = n*100
dp = [0]*(U+1)
dp[0] = 1
for a in A:
    for j in reversed(range(U+1)):
        if 0 <= j-a:
            dp[j] += dp[j-a]
print(sum(dp[p::2]))

Submission status: Accepted

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

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

def calc(n):
    ans = 0
    for r in range(n-n%2, -1, -2):
        ans += combinations_count(n, r)
    return ans
    
gusu = 0
for a in A:
    if a%2 == 0:
        gusu +=1
kisu = N - gusu

p0 = 2**gusu*calc(kisu)
if P == 0:
    print(p0)
else:
    print(2**N-p0)

Submission status: Accepted

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

# 奇数の数を数える
odd_cnt = 0
for a in A:
    if a % 2 != 0:
        odd_cnt += 1

# 全てのが偶数の時
if odd_cnt == 0:
    if P == 0:
        print(2**N)
    else:
        print(0)
    exit(0)

print(2**(N-1))

Submission status: Accepted

Solution code:
import collections

def nCk(n, k):
    k = min(k, n-k)
    numer = 1
    for i in range(n, n-k, -1):
        numer *= i
    denom = 1
    for i in range(k, 1, -1):
        denom *= i
    return numer // denom

def main():
    N, P = map(int, input().split())
    A = list(map(int, input().split()))
    B = [x%2 for x in A]
    Bcount = collections.Counter(B)
    if Bcount[1] == 0 and P == 1:
        print(0)
        return
    ans = 0
    if P == 0:
        tmp = pow(2, Bcount[0])
        for i in range(0, Bcount[1]+1, 2):
            ans += tmp * nCk(Bcount[1], i)
        print(ans)
        return
    else:
        tmp = pow(2, Bcount[0])
        for i in range(1, Bcount[1]+1, 2):
            ans += tmp * nCk(Bcount[1], i)
        print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    N, P = MI()
    A = LI()

    odd = 0
    even = 0
    for a in A:
        if a % 2 == 0:
            even += 1
        else:
            odd += 1
    if odd == 0:
        # 全て偶数
        if P == 0:
            print(pow(2, even))
        else:
            print(0)
    else:
        # 奇数が存在する
        # 一つの奇数に着目すると、それ以外の数の合計が奇数か偶数になるかによって
        # 選ぶ選ばないを選択することでPにすることができる
        print(pow(2, N-1))

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def comb(n, r):
    # if n - r < 0: return 0
    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

def solve():
    N, P = MI()
    A = LI()

    cnt = {}
    for a in A:
        cnt[a % 2] = cnt.get(a%2, 0) + 1
    # print(cnt)

    ans = 0

    one = cnt.get(1, 0)
    zero = cnt.get(0, 0)
    if P == 0:
        for i in range(0, one+1, 2):
            # print(i)
            # print(comb(one, i))
            ans += comb(one, i)

        print(ans * (pow(2, zero)))
    else:
        for i in range(1, one+1, 2):
            ans += comb(one, i)
        print(ans * pow(2, zero))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
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)]


N, P = map(int, input().split())  # 袋がN個, 2をPにしたい
A = list(map(lambda x: int(x)%2, input().split()))
# print(A)

kisuu = sum(A)  # 奇数個の袋の数
guusuu = N-kisuu  # 偶数個の袋の数

# Pが1のとき，偶数側の袋を任意の数と，奇数側の数を奇数個選ぶ
if P == 1:
    tmp_guusuu = 0
    tmp_kisuu = 0
    # 偶数側を任意の個数選ぶ
    for i in range(guusuu+1):
        tmp_guusuu += cmb(guusuu, i)
    for i in range(kisuu+1):
        if i % 2 == 0:
            continue
        tmp_kisuu += cmb(kisuu, i)
    print(tmp_guusuu*tmp_kisuu)

# Pが0のとき，偶数側の袋を任意の数と，奇数側の数を偶数個選ぶ
elif P == 0:
    tmp_guusuu = 0
    tmp_kisuu = 0
    # 偶数側を任意の個数選ぶ
    for i in range(guusuu+1):
        tmp_guusuu += cmb(guusuu, i)
    # 奇数側を0個数以上の偶数個選ぶ
    for i in range(kisuu+1):
        if i % 2 == 1:
            continue
        tmp_kisuu += cmb(kisuu, i)
    print(tmp_guusuu*tmp_kisuu)

Submission status: Accepted

Solution code:
n, p, *a = map(int, open(0).read().split())
odd = [i for i in a if i%2 == 1]
if len(odd) == 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 comb(n, r):
    return factorial(n) // (factorial(n-r) * factorial(r))

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache

N,P = map(int, input().split())
A_list = [int(e) for e in input().split()]

A_odd_list = list()
A_even_list = list()

for A in A_list:
    if A%2 == 0:
        A_even_list.append(A)
    else:
        A_odd_list.append(A)

#######################################################################
#https://note.nkmk.me/python-math-factorial-permutations-combinations/
from operator import mul
from functools import reduce

@lru_cache(maxsize=100000000)
def combinations_count(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
#######################################################################

choice_odd = 0
choice_even = 0
odds = len(A_odd_list)
evens = len(A_even_list)

if P == 1:
    #奇数の中から奇数個選ぶ
    for i in range(1,odds+1,2):
        choice_odd += combinations_count(odds,i)
    #偶数の中から好きな個数を選ぶ
    for i in range(0,evens+1,1):
        choice_even += combinations_count(evens,i)
else:
    #奇数の中から偶数個選ぶ
    for i in range(0,odds+1,2):
        choice_odd += combinations_count(odds,i)
    #偶数の中から好きな個数を選ぶ
    for i in range(0,evens+1,1):
        choice_even += combinations_count(evens,i)
        
print(choice_odd*choice_even)

Submission status: Accepted

Solution code:
import sys

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


def resolve():
    n, p = map(int, input().split())
    A = list(map(int, input().split()))
    odd = len([a for a in A if a % 2 != 0])
    even = len([a for a in A if a % 2 == 0])

    # 奇数のビスケットが入った袋を偶数個(０を除く）選ぶパターン
    tot_odd = 0
    for i in range(2, odd + 1, 2):
        bunbo = 1
        bunsi = 1
        for j in range(1, i + 1):
            bunbo *= (odd - j + 1)
            bunsi *= j
        cmb = bunbo // bunsi
        tot_odd += cmb

    # 偶数のビスケットが入った袋を選ぶパターン
    tot_even = 0
    for i in range(even + 1):
        if i == 0:
            tot_even += 1
            continue
        bunbo = 1
        bunsi = 1
        for j in range(1, i + 1):
            bunbo *= (even - j + 1)
            bunsi *= j
        cmb = bunbo // bunsi
        tot_even += cmb

    even_pattern = tot_odd * tot_even + tot_even
    odd_pattern = 2 ** n - even_pattern
    print(even_pattern if p == 0 else odd_pattern)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

N, P = map(int, input().split())
A = list(map(int, sys.stdin.readline().rsplit()))

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

if odd == 0 and P == 0:
    print(2 ** even)
elif odd == 0 and 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()))
even = 0
odd = 0
for i in range(N):
    if A[i]%2==0:
        even += 1
    else:
        odd += 1
if odd>=1:
    ans = pow(2,even+odd-1)
elif P==0:
    ans = pow(2,even)
else:
    ans = 0
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce


def ncr(n, r):
    r = min(r, n - r)
    numer = reduce(lambda x, y: x * y, range(n, n - r, -1), 1)
    denom = reduce(lambda x, y: x * y, range(1, r + 1), 1)
    return numer // denom


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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N, P = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0]*2 for _ in range(N+1)]
dp[0][0] = 1

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

print(dp[N][P])