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

su = 2 ** N
guusu = True
for a in A:
    if a % 2 == 1:
        guusu = False
        break
if P == 0:
    print(su if guusu else su//2)
else:
    print(0 if guusu else su//2)

Submission status: Accepted

Solution code:
def count(l):
    res = {0:0, 1:0}
    for d in l:
        if d in res:
            res[d] += 1
        else:
            res[d] = 1
    return res
from operator import mul
from functools import reduce

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

n, p = map(int, input().split())
data = list(map(int, input().split()))
data = [i%2 for i in data]
oz = count(data)

ans = 0
m = 2**oz[0]
if p == 0:
    choice = 2
    ans += m
elif p == 1:
    choice = 1
ones = oz[1]
while choice <= ones:
    ans += m*cmb(ones, choice)
    choice += 2
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
import math
def resolve():
    n,p=map(int, input().split())
    l=list(map(int,input().split()))
    gu=0
    ki=0
    cnt=0
    for i in l:
        if i%2==1:
            ki+=1
        else:
            gu+=1
    if p==0:
        for j in range(0,ki+1,2):
            x=math.factorial(ki)//(math.factorial(ki-j)*math.factorial(j))
            for k in range(gu+1):
                y=math.factorial(gu)//(math.factorial(gu-k)*math.factorial(k))
                cnt+=x*y
    else:
        for j in range(1,ki+1,2):
            x=math.factorial(ki)//(math.factorial(ki-j)*math.factorial(j))
            for k in range(gu+1):
                y=math.factorial(gu)//(math.factorial(gu-k)*math.factorial(k))
                cnt+=x*y
    print(cnt)


resolve()

Submission status: Accepted

Solution code:
n,p = map(int,input().split())
l = list(map(int,input().split()))
l1 = []
for i in l:
  if i%2==0:
    l1.append(0)
  else:
    l1.append(1)
    


a = l1.count(1)
b = l1.count(0)
if a!=0:
  cou = (2**(b))*(2**(a-1))
  print(cou)
else:
  if p%2==0:
    print(2**b)
  else:
    print(0)

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache(maxsize=None)

def kaijou(n):
    if n <= 1:
        return 1
    return kaijou(n-1)*n

n,p = map(int,input().split())
even = 0
odd = 0
ans = 0
for i in map(int,input().split()):
    if i % 2 == 0:
        even += 1
    else:
        odd += 1
if p == 0:
    eveng = 0
    for j in range(0,odd+1,2):
        if j > odd:
            break
        eveng += kaijou(odd)/kaijou(odd-j)/kaijou(j)
    ans = int((2**even)*eveng)
else:
    oddg = 0
    #print(odd)
    for j in range(1,odd+1,2):
        if j > odd:
            break
        oddg += kaijou(odd)/kaijou(odd-j)/kaijou(j)
    ans = int((2**even)*oddg)
print(ans)

Submission status: Accepted

Solution code:
def fur(n, r):
    return  math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
import math
n, p = map(int, input().split())
A = list(map(lambda x:int(x)%2, input().split()))
from collections import Counter
c = dict(Counter(A))
a, b = 0, 0
if c.get(0) != None:
    a = c[0]
if c.get(1) != None:
    b = c[1]
result = 0
piyo = 1
for i in range(1, a+1):
    piyo += fur(a, i)
for i in range(0, b+1, 2):
    result += fur(b, i) * piyo
if p == 0:
    print(result)
else:
    hoge = 0
    for i in range(n+1):
        hoge += fur(n, i)
    print(hoge - result)

Submission status: Accepted

Solution code:
memo = [0] * 100
def f(x):
  global memo
  if x in [0, 1]:
    memo[x] = 1
    return 1
  else:
    if memo[x] > 0:
      return memo[x]
    else:
      memo[x] = x*f(x-1)
      return memo[x]

def comb(n, r):
  a = f(n)
  b = f(r)
  c = f(n-r)
  return a // b // c

N, P = map(int, input().split())
A = list(map(int, input().split()))
A = [a%2 for a in A]
n0 = A.count(0)
n1 = N - n0
base = 2 ** n0
m0 = m1 = 0
for i in range(n1+1):
  if i % 2:
    m1 += comb(n1, i)
  else:
    m0 += comb(n1, i)

if P == 0:
  print(base * m0)
else:
  print(base * m1)

Submission status: Accepted

Solution code:
n , p = map(int, input().split())
a = list(map(int,input().split()))
b = [0]*n

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

ans=2**(n-1)
if p==1 and sum(b)==0:
    ans = 0
if p==0 and sum(b)==0:
    ans *= 2
print(ans)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, p = map(int, input().split())
    A = list(map(int, input().split()))

    dp = [1, 0]
    for a in A:
        if a & 1:
            s = sum(dp)
            dp = [s, s]
        else:
            dp = [dp[0] * 2, dp[1] * 2]

    print(dp[p])
resolve()

Submission status: Accepted

Solution code:
from collections import Counter


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)


def combination(n, r, mod=10**9+7):
    """
    nCr mod m
    """
    if n < r:
        return 0
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


n, p = map(int, input().split())
a = list(map(int, input().split()))
b = [ai % 2 for ai in a]
c = Counter(b)

ans = 0
if p == 0:
    even = (2 ** c[0])
    odd = 1
    for i in range(2, c[1] + 1, 2):
        odd += combination(c[1], i)
    ans = even * odd
else:
    even = (2 ** c[0])
    odd = 0
    for i in range(1, c[1] + 1, 2):
        odd += combination(c[1], i)
    ans = even * odd

print(ans)

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

modA = [i % 2 for i in A]
odd = modA.count(1)
even = modA.count(0)

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

if P == 0:
    """
    evenからは好きなだけ選べる
    それに対してoddから偶数個を選ぶ
    """
    odd_count = 0
    for i in range(0,odd+1,2):
        odd_count += combinations_count(odd, i)
    print(even_count * odd_count)
else:
    """
    evenから好きなだけ選べる
    oddから奇数個を選ぶ
    """
    odd_count = 0
    for i in range(1,odd+1,2):
        odd_count += combinations_count(odd, i)
    print(even_count * odd_count)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

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

    odd = 0
    even = 0
    for a in A:
        if a&1:
            odd += 1
        else:
            even += 1
    if P:
        if odd == 0:
            print(0)
        else:
            print(2**(N - 1))
    else:
        if odd == 0:
            print(2**N)
        else:
            print(2**(N - 1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

def combi(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()))
odd = 0
even = 0
for a in L:
    if a % 2:
        odd += 1
    else:
        even += 1
c = 0
if p == 0:
    for i in range(0, odd + 1, 2):
        c += combi(odd, i)
else:
    for i in range(1, odd + 1, 2):
        c += combi(odd, i)
ans = 2 ** even * c
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N, P = map(int, input().split())
A = list(map(int, input().split()))
n0 = 0
n1 = 0
for i, a in enumerate(A):
    b = a % 2
    A[i] = b
    if b == 0:
        n0 += 1
    else:
        n1 += 1
C1 = [1]
for i in range(n1):
    C1.append(C1[-1] * (n1-i)//(i+1))


ans = 0
for i in range(0, 51, 2):
    if i + P > n1:
        break
    ans += C1[i+P] * (2**(n0))


print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

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

li = list(np.mod(A, 2))
zero = li.count(0)
one = li.count(1)

if P == 0:
    combi = [0] + [2 * x for x in range(1, (one + 2) // 2)]
if P == 1:
    combi = [1] + [2 * x + 1 for x in range(1, (one + 1) // 2)]

q = deque(combi)

right = 0
while q:
    c = q.popleft()
    tmp = cmb(one, c)
    right += tmp

print(2**zero * right)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np
from functools import lru_cache

nCr = {}


@lru_cache(maxsize=None)
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())
A = np.array(list(map(int, input().split())))

li = list(np.mod(A, 2))
zero = li.count(0)
one = li.count(1)

if P == 0:
    combi = [0] + [2 * x for x in range(1, (one + 2) // 2)]
if P == 1:
    combi = [1] + [2 * x + 1 for x in range(1, (one + 1) // 2)]

q = deque(combi)

right = 0
while q:
    c = q.popleft()
    tmp = cmb(one, c)
    right += tmp

print(2**zero * right)

Submission status: Accepted

Solution code:
def fact(n):
  a = 1
  for i in range(2, n+1):
    a *= i
  return a

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

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

zero = 0
one = 0
for i in a:
  if i % 2 == 0:
    zero += 1
  else:
    one += 1

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

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

e, o = 0, 0
for i in range(n):
    e += a[i] % 2 == 0
    o += a[i] % 2 == 1

if o == 0:
    if p == 1:
        print(0)
    else:
        print(1 << n)
else:
    print(1 << (n - 1))

Submission status: Accepted

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

odd = [i for i in a if i % 2 == 1]
even = [i for i in a if i % 2 == 0]
ecnt = pow(2, len(even))
ocnt = pow(2, max(len(odd)-1,0))
print(0 if (len(odd) == 0 and p == 1) else ecnt * ocnt)

Submission status: Accepted

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

odd = [i for i in a if i % 2 == 1]
even = [i for i in a if i % 2 == 0]
ecnt = pow(2, len(even))
ocnt = pow(2, max(len(odd)-1,0))
print(0 if (len(odd )== 0 and p == 1) else ecnt * ocnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

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

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

ans=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

if p==0:
    for i in range(0,one+1,2):
        ans += cmb(one,i)*2**zero

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

print(ans)

Submission status: Accepted

Solution code:
def combination(n,r=-1):
    #res[r] = nPr
    if r==-1:
        r = n
    #nCrの一覧を返す。rの上限も 
    if (r<0) or (n<r):
        return 0
    cur = 1
    res = []
    res.append(cur)
    for i in range(1,r+1):
        cur *= n + 1 -i
        cur //= i
        res.append(cur)
    return res
N,P = [int(hoge) for hoge in input().split()]
A = sum([int(hoge)%2 for hoge in input().split()])
B = N - A#偶数
C = combination(A)
comb = 0
for i in range(P,A+1,2):
    comb += C[i]
print(2**B * comb)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc017/tasks/agc017_a
# dpっぽくね？

'''
dp[i][p] ... 袋の選び方の通りの総数 [0,i)まで見たとき、余りがpになる場合


if A[i]が偶数
選ぶときの通りの数
    dp[i+1][0] += dp[i][0]*2
    dp[i+1][1] += dp[i][1]*2
    ∵偶+偶→偶、奇+偶→奇 でもともとの通りの数に影響を与えない
if A[i]が奇数
    dp[i+1][0] += dp[i][1]+dp[i][0]
    dp[i+1][1] += dp[i][0]+dp[i][1]
    ∵偶+奇→奇、奇+奇→偶 で遷移するので選ぶときと選ばないときで遷移先が異なる
'''
N, P = map(int, input().split())
A = list(map(int, input().split()))
dp0 = 1
dp1 = 0

for a in A:
    if a & 1:
        new0 = dp0 + dp1
        new1 = new0
    else:
        new0 = dp0 * 2
        new1 = dp1 * 2
    dp0 = new0
    dp1 = new1

print(dp1 if P & 1 else dp0)

Submission status: Accepted

Solution code:
import numpy as np
 
N, P = map(int, input().split())
A = list(map(int, input().split()))
odd = len([i for i in A if i%2!=0])
if odd==0 and P==0:
    ans = 2**N
elif odd==0 and P==1:
    ans = 0
else:
    ans = 2**(N-1)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#3問目
import itertools
import math

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

N, P = map(int, input().split())
A = list(map(int, input().split()))
#偶数グループと奇数グループにわける
odd = []
even = []
c = 0
for i in A:
    if i % 2 == 0:
        even.append(i)
    else:
        odd.append(i)
#奇数グループは組み合わせの総数を出す
#もしP=1なら奇数グループから奇数個を出す組み合わせの数、P=0なら奇数グループから偶数個を出す組み合わせの数
if P == 1:
    #奇数グループから奇数個を出す組み合わせの数
    for i in range(1, len(odd)+1, 2):
        c += combinations_count(len(odd), i)
if P == 0:
    #奇数グループから偶数個を出す組み合わせの数
    for i in range(0, len(odd)+1, 2):
        c += combinations_count(len(odd), i)
        
print(2 ** len(even) * c)

Submission status: Accepted

Solution code:
from math import factorial

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

#p==0:奇数が偶数個になるまで食べる
#p==1:奇数が奇数個になるまで食べる
def calc_comb(n,r):
    return factorial(n) / factorial(r) / factorial(n - r)

odd_len = 0
even_len = 0
for i in range(n):
    if a_input[i]%2==0:
        even_len+=1
    else:
        odd_len+=1

ans=0
even_comb = 2**even_len
if p==0:
    if odd_len%2==0:
        for i in range(0,odd_len+1,2):
            ans+=calc_comb(odd_len,i)*even_comb
    if odd_len%2==1:
        for i in range(1,odd_len+1,2):
            ans+=calc_comb(odd_len,i)*even_comb
else:
    if odd_len%2==0:
        for i in range(1,odd_len+1,2):
            ans+=calc_comb(odd_len,i)*even_comb
    if odd_len%2==1:
        for i in range(0,odd_len+1,2):
            ans+=calc_comb(odd_len,i)*even_comb
print(int(ans))

Submission status: Accepted

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

even = sum([a%2==0 for a in A])
odd = n - even

def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= n-i
    ret //= i+1  
  return ret
  
ans = 0
add = 2 ** even
for k in range(p,odd+1,2):  
  ans += nCr(odd,k) * add  
  
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# A - Biscuits
import numpy as np

N, P = map(int, input().split())
A = list(map(int, input().split()))
odd = len([i for i in A if i%2!=0])
if odd==0 and P==0:
    ans = 2**N
elif odd==0 and P==1:
    ans = 0
else:
    ans = 2**(N-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

n,p = MI()
a = LI()
cnt = 0
for i in range(n):
    if a[i]%2 == 1:
        cnt += 1
if cnt%2 == 1:
    print(2**(n-1))
elif cnt == 0:
    if p == 1:
        print(0)
    else:
        print(2**n)
else:
    print(2**(n-1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
from bisect import bisect_left,bisect_right

def main():  
    N,P = map(int,input().split())
    A = list(map(int,input().split()))
    cnt1 = sum(a%2 == 1 for a in A)
    cnt0 = N - cnt1
    factorial = [1,1]
    for i in range(2,N + 1):
        factorial.append(factorial[-1]*i)
    
    nck = lambda n,k:factorial[n]//factorial[n - k]//factorial[k]

    ans = 0
    if P == 0:
        for i in range(0,cnt1 + 1,2):
            ans += nck(cnt1,i)
        ans *= pow(2,cnt0)
    else:
        for i in range(1,cnt1 + 1,2):
            ans += nck(cnt1,i)
        ans *= pow(2,cnt0)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc017/tasks/agc017_a

from math import factorial
n, p = map(int, input().split())

nums = [int(i) for i in input().split()]

odd = 0
even = 0
for num in nums:
    if num % 2 == 0:
        even += 1
    else:
        odd += 1
# ans = 0
# if p == 0:
#     e = 2 ** even
#     o = 0
#     for i in range(0, odd + 1, 2):
#         o += factorial(odd) // (factorial(odd - i) * factorial(i))
#     ans += e * o
# elif p == 1:
#     e = 2 ** even
#     o = 0
#     for i in range(1, odd + 1, 2):
#         o += factorial(odd) // (factorial(odd - i) * factorial(i))
#     ans += e * o
# print(ans)

# 別解
ans = 0
if p == 0 and odd == 0:
    ans += 2 ** even
else:
    ans += (2 ** even) * (2 ** odd // 2)
print(ans)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
A = list(map(int, input().split()))
ev = 0
od = 0
for a in A:
    if a % 2 == 0:
        ev += 1
    else:
        od += 1
if P == 0 and od == 0:
    print(2**ev)
else:
    print(2**ev * (2**od//2))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc017/tasks/agc017_a

from math import factorial
n, p = map(int, input().split())

nums = [int(i) for i in input().split()]

odd = 0
even = 0
for num in nums:
    if num % 2 == 0:
        even += 1
    else:
        odd += 1
ans = 0
if p == 0:
    e = 2 ** even
    o = 0
    for i in range(0, odd + 1, 2):
        o += factorial(odd) // (factorial(odd - i) * factorial(i))
    ans += e * o
elif p == 1:
    e = 2 ** even
    o = 0
    for i in range(1, odd + 1, 2):
        o += factorial(odd) // (factorial(odd - i) * factorial(i))
    ans += e * o
print(ans)

Submission status: Accepted

Solution code:
from math import factorial

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

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

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

    a,b = 0,0
    b = 2**even

    for i in range(odd+1):
        if i % 2 == P:
            a += comb(odd,i)

    print(a*b)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import numpy as np

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

d = defaultdict(int)
d.update(Counter(A).items())

if d[1] == 0:
    if P == 0:
        print(2**N)
    else:
        print(0)
else:
    print(2**(N-1))

Submission status: Accepted

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

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

n = [0] * 2

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


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

print(ans)

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

even=0
odd=0
for i in a:
    if i%2 == 0:
        even+=1
    else:
        odd+=1
ans = 0
if p == 0:
    evens = 0
    i = 1
    while(i <= even):
        evens += cmb(even, i)

        i+=1

    ans += 1<<even
    i = 2
    while(i <= odd):
        ans += cmb(odd, i) + cmb(odd, i)*evens
        i+=2

    print(ans)

else:
    evens = 0
    i = 1
    while(i <= even):
        evens += cmb(even, i)

        i+=1

    i = 1
    while(i <= odd):
        ans += cmb(odd, i) + cmb(odd, i)*evens

        i+=2
    print(ans)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
odd = sum([int(i) % 2 for i in input().split()])
even = N-odd

if odd == 0:
    if P == 0:
        print(2**even)
    else:  # P==1
        print(0)
else:
    print(2**even * (2**odd//2))

Submission status: Accepted

Solution code:
import collections
n, p = list(map(int, input().split()))
a = list(map(int, input().split()))
a2 = [ai%2 for ai in a]
a2 = collections.Counter(a2)

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

Submission status: Accepted

Solution code:
import collections
n, p = list(map(int, input().split()))
a = list(map(int, input().split()))
a2 = [ai%2 for ai in a]
a2 = collections.Counter(a2)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

e = 0
o = 0
for i in lis:
  if i % 2 == 0:
    e += 1
  else:
    o += 1

if p == 0:
  ans = 1
  for i in range( o//2):
    ans += nCk( o, (i+1)*2)
  print( int( ans * 2**e))
else:
  ans = 0
  for i in range( o//2):
    ans += nCk( o, i*2+1)
  print( int( ans * 2**e))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import factorial
from collections import Counter
def nCr(n,r):
    return factorial(n)//(factorial(r)*factorial(n-r))
N,P=map(int,input().split())
A=list(map(lambda x:int(x)%2,input().split()))
c=Counter(A)
z=pow(2,c.get(0,0))
res=0
for i in range(1 if P else 0,c.get(1,0)+1,2):
    res+=nCr(c.get(1,0),i)
print(z*res)

Submission status: Accepted

Solution code:
from math import factorial
n,p=map(int,input().split())
a=list(map(int,input().split()))
a1=[]
a0=[]

for i in a:
    if i%2==1:
        a1.append(i)
    else:
        a0.append(i)

a1c=len(a1)
a0c=len(a0)
#print(a1)
#print(a0)
ans1=0
for i in range(a0c+1):
    ans1+=factorial(a0c) / factorial(i) / factorial(a0c - i)
#print(ans1)
ans2=0
if p==1:
    for i in range(1,a1c+1,2):
        ans2+=factorial(a1c) / factorial(i) / factorial(a1c - i)

else:
    for i in range(0,a1c+1,2):
        ans2+=factorial(a1c) / factorial(i) / factorial(a1c - i)

print(int(ans2*ans1))

Submission status: Accepted

Solution code:
def comb(n, k, mod=10**9+7):
    num = den = 1
    for i in range(k):
        num *= n - i
        den *= i + 1
    return num // den

N, P = map(int, input().split())
A = list(map(int, input().split()))
cnt = [0] * 2
for a in A:
    cnt[a % 2] += 1
even = 0
odd = [0] * 2
for i in range(N+1):
    even += comb(cnt[0], i)
    odd[i % 2] += comb(cnt[1], i)
print(even * odd[P])

Submission status: Accepted

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

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)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rln(s):
    return range(len(s))

#a = list(map(int, input().split()))

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



n,P = list(map(int, input().split()))
a = list(map(int, input().split()))
num01 = [0,0]

for i in a:
    num01[i%2]+=1

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10**9+7
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


#print(num01)

ans = 0
for i in range(num01[1]-P, -1, -2):
    ans += cmb(num01[1],i,p)

ans *= 2**num01[0]

print(ans)

Submission status: Accepted

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

# dp[i][p]:i番目まで見たとき、余りがpとなる選び方
dp = [[0 for _ in range(2)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
  if a[i]%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][0]+dp[i][1]
    dp[i+1][1] = dp[i][0]+dp[i][1]
print(dp[n][p])
#print(dp)

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
if even == n:
    if p == 0:
        print(2**n)
    else:
        print(0)
else:
    print(2**(n-1))

Submission status: Accepted

Solution code:
from collections import Counter
def main():
    N, P = map( int, input().split())
    A = Counter(list( map( lambda x: int(x)%2, input().split())))
    zero = A[0]
    one = A[1]
    ans = 1
    now = 1
    for i in range(1,one+1):
        now *= (one-i+1)
        now //= i
        if i%2 == 0:
            ans += now
    if P == 0:
        print( ans*pow(2,zero))
    else:
        print(pow(2,N) - ans*pow(2,zero))
        
if __name__ == '__main__':
    main()