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()))
B = [A[k]%2 for k in range(N)]
dp = [[0,0] for k in range(N+1)]
dp[0][0] = 1

for k in range(N):
    if B[k] == 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][0] + dp[k][1]

print(dp[N][P])

Submission status: Accepted

Solution code:
import sys

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

def solve():
    input = sys.stdin.readline
    N, P = map(int, input().split())
    A = [int(a) for a in input().split()]
    even, odd = 0, 0
    for a in A:
        if a % 2 == 0: even += 1
        else: odd += 1
    
    even_Chose = 0
    odd_Chose = 0
    for i in range(even + 1): even_Chose += comb(even, i)
    for i in range(odd + 1):
        if i % 2 == P: odd_Chose += comb(odd, i)
    print(even_Chose * odd_Chose) 

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import math

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

odd = list(filter(lambda x:(x % 2 == 1), A))
even = list(filter(lambda x:(x % 2 == 0), A))
#print(odd)
#print(even)
odd_num = len(odd)
even_num = len(even)

ans = 0

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


ans = 0
for o in range(0, odd_num + 1):
    for e in range(0, even_num + 1):
        #print(o, e)
        if P == 0:
            if o % 2 == 0:
                #print(o,e, comb(odd_num, o) * comb(even_num, e))
                ans += comb(odd_num, o) * comb(even_num, e)
        else:
            if o % 2 == 1:
                ans += comb(odd_num, o) * comb(even_num, e)

print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

#コンビネーション
def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

N = 200  # N は必要分だけ用意する
mod = pow(10, 50) + 7
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) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)


n, p = MAP()
a = LIST()
arr = [i % 2 for i in a]
num1 = sum(arr)
num0 = n - num1
ans = 0
for i in range(n + 1): #全体でi個選ぶ
    for j in range(i + 1): #1をj個選ぶ
        if j % 2 == p:
            ans += cmb(num1, j) * cmb(num0, i - j)
print(ans)

Submission status: Accepted

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

cnt_odd = sum([int((Ai % 2) == 1) for Ai in A])
cnt_evn = N - cnt_odd

ptn_evn = 1 << cnt_evn

tab_ncr = [1]
ncr_tmp = 1
for i in range(cnt_odd):
    ncr_tmp *= (cnt_odd - i)
    ncr_tmp //= (i + 1)
    tab_ncr.append(ncr_tmp)

ans = 0
# print("#", tab_ncr)

for i in range(cnt_odd + 1):
    if i % 2 != P: continue
    #
    ans += (ptn_evn * tab_ncr[i])

print(ans)

Submission status: Accepted

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

A = [a%2 for a in A]

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, P = map(int, input().split())
a = list(map(int, input().split()))
odd = 0
even = 0
for i in range(N):
  if a[i] % 2: odd += 1
  else: even += 1
if P:
  print(int((pow(2, odd - 1) * pow(2, even) * (odd > 0))))
else:
  print(max(1, pow(2, odd - 1)) * pow(2, even))

Submission status: Accepted

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

n = 0
for v in A:
  if v % 2 == 0:
    n += 1
if N == n:
  if P == 0: ans = 2 ** N
  else: 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()))
dp = [[0, 0] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(2):
        dp[i+1][j] += dp[i][j]
        dp[i+1][(j+a[i])%2] += dp[i][j]
print(dp[n][p])

Submission status: Accepted

Solution code:
# 0405の分もやる

#ABC041-C
if False:
    N=int(input())
    A=[int(i) for i in input().split()]
    ans=[(i,a) for i,a in enumerate(A)]
    ans.sort(key=lambda x: x[1],reverse=True)
    for i in range(N): print(ans[i][0]+1)

#AGC017-A
if True:
    N,P=map(int,input().split())
    A=[int(i) for i in input().split()]
    flag=True # 偶数のみか
    for a in A:
        if a%2==1:
            flag=False
            break
    if flag:
        if P==0:
            print(2**N)
        else:
            print(0)
    else:
        print(2**(N-1))

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
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 = m()

a = l()

on= 0

su = 0

for i in range(n):
    a[i] %= 2
    if a[i] == 1:
        on += 1
no = n - on

if p % 2 == 0:
    if on % 2 == 0:
        for i in range(0,on+1,2):
            su += cmb(on,i)
        suu = 0
        for i in range(no+1):
            suu += cmb(no,i)
        su *= suu
    else:
        for i in range(1,on+1,2):
            su += cmb(on,i)
        suu = 0
        for i in range(no+1):
            suu += cmb(no,i)
        su *= suu

else:
    if on % 2 == 0:
        for i in range(1,on+1,2):
            su += cmb(on,i)
        suu = 0
        for i in range(no+1):
            suu += cmb(no,i)
        su *= suu

    else:
        for i in range(0,on+1,2):
            su += cmb(on,i)
        suu = 0
        for i in range(no+1):
            suu += cmb(no,i)
        su *= suu

print(su)

Submission status: Accepted

Solution code:
from scipy import misc
N,P = (int(x) for x in input().split())
A = list(map(int, input().split()))
o = sum(x % 2 == 1 for x in A)
e = sum(x % 2 == 0 for x in A)
if P == 0:
    sum0 = sum(misc.comb(o, i, exact=True) for i in range(0, o+1, 2))
    print(sum0*(2**e))
else:
    sum1 = sum(misc.comb(o, i, exact=True) for i in range(1, o+1, 2))
    print(sum1*(2**e))

Submission status: Accepted

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

n, p = map(int, input().split())
a = list(map(int, input().split()))
m = 0
for i in a:
    if i % 2 == 0:
        m += 1
x = 0
for i in range(1, n - m + 1, 2):
    x += comb(n - m, min(i, n - m - i))
x *= 2 ** m
print(int(x) if p == 1 else int(2 ** n - x))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from scipy.misc import comb

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

for i in A:
    if i%2==0:
        e +=1
    else:
        o +=1
#print(e,o)
       
if P==0:
    e_x = 2**e
    o_x = 0
    for j in range(0,o+1,2):
        #print(j,comb(o,j,exact=True))
        o_x += comb(o,j,exact=True)
else:
    e_x = 2**e
    if o==0:
        o_x = 0
    else:
        o_x = 0
        for j in range(1,o+1,2):
            #print(j,comb(o,j,exact=True))
            o_x += comb(o,j,exact=True)

ans = e_x * o_x
print(ans)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

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

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

a_0 = []
a_1 = []
for j in a_list:
    if j % 2 == 0:
        a_0.append(j)
    else:
        a_1.append(j)

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


if p == 0:
    ans = 1

    tmp_2 = 0
    if len(a_0) >= 1:
        for i in range(1,len(a_0)+1):
            tmp_2 += combinations_count(len(a_0), i)
    #print(tmp_2)
    ans += tmp_2
    
    tmp_1 = 0
    if len(a_1) > 2:
        for i in range(2,len(a_1)+1, 2):
            #print(i)
            tmp_1 += combinations_count(len(a_1), i)
    elif len(a_1) == 2:
        tmp_1 += 1
    ans += tmp_1
    #print(tmp_1)

    ans += tmp_1*tmp_2


elif p == 1:
    ans = 0

    tmp_2 = 1
    if len(a_0) >= 1:
        for i in range(1,len(a_0)+1):
            tmp_2 += combinations_count(len(a_0), i)
    #print(tmp_2)

    if len(a_1) >= 1:
        for i in range(1,len(a_1)+1, 2):
            #print(i)
            tmp = combinations_count(len(a_1), i)
            ans += tmp*tmp_2

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, p = map(int, readline().split())
a = list(map(int, readline().split()))
cnt_1 = 0
cnt_2 = 0
for i in a:
    if i % 2 == 1:
        cnt_1 += 1
    else:
        cnt_2 += 1
ans = 2 ** max(0, cnt_1 - 1) * 2 ** cnt_2
if p == 1 and cnt_1 == 0:
    ans = 0
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import factorial

def combi(n, k):
  return factorial(n) // factorial(n-k) // factorial(k)

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

e = len([a for a in A if a % 2 == 0])
o = N - e

ans = 0
for i in range(P, o+1, 2):
  ans += combi(o, i)
print(ans * pow(2, e))

Submission status: Accepted

Solution code:
from scipy.misc import comb
from math import factorial

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

e = len([a for a in A if a % 2 == 0])
o = N - e

ans = 0
if P == 0:
  for i in range(0, o+1, 2):
    ans += comb(o, i, exact=True)
  print(ans * pow(2, e))
else:
  for i in range(1, o+1, 2):
    ans += comb(o, i, exact=True)
  print(ans * pow(2, e))

Submission status: Accepted

Solution code:
from math import factorial

def combi(n, k):
  return factorial(n) // factorial(n-k) // factorial(k)

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

e = len([a for a in A if a % 2 == 0])
o = N - e

ans = 0
if P == 0:
  for i in range(0, o+1, 2):
    ans += combi(o, i)
  print(ans * pow(2, e))
else:
  for i in range(1, o+1, 2):
    ans += combi(o, i)
  print(ans * pow(2, e))

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(j) for j in input().split()]
#template
#issueから始める
N,P = inputlist()
A = inputlist()
for i in range(N):
    A[i] = A[i] % 2
from collections import Counter
c = Counter(A)
n0 = c[0]
n1 = c[1]
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
ans = 0
ans2 = 0
for i in range(1,n1+1):
    if i % 2 == 0:
        continue
    ans += comb(n1,i)
for i in range(n1+1):
    if i % 2 == 1:
        continue
    ans2 += comb(n1,i)
if P == 1:
    print((2**n0)*ans)
if P == 0:
    print((2**n0)*ans2)

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def print_list(l): print(*l, sep='\n')
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def No(): print('No')

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N,P = imn()
A = iln()

contains_odd_number = False
for a in A:
    if a % 2 == 1:
        contains_odd_number = True
if contains_odd_number:
    print(2**(N-1))
else:
    if P == 0:
        print(2**N)
    else:
        print(0)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
biscuits = list(map(int, input().split()))
gu = 0
ki = 0
for i in range(N):
    if biscuits[i] % 2 == 0:
        gu += 1
    else:
        ki += 1
if P == 1 and ki == 0:
    print(0)
elif gu == N:
    print(pow(2,N))
else:
    print(pow(2,N-1))

Submission status: Accepted

Solution code:
from math import factorial
def combi(n,k):
    return factorial(n) // factorial(k) // factorial(n-k)

n,p = map(int,input().split())
a = list(map(int,input().split()))
even = 0
odd  = 0
for i in a:
    if i&1:
        odd  += 1
    else:
        even += 1
picke = 0
for i in range(even + 1):
    picke += combi(even,i)
picko = 0
for i in range(p,odd + 1,2):
    picko += combi(odd,i)
print(picke*picko)

Submission status: Accepted

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

from math import factorial
comb0 = 2 ** mod0
comb1 = 0
if mod1 > 0:
  for i in range(P, mod1+1, 2):
    comb1 += factorial(mod1) // (factorial(mod1 - i) * factorial(i))
else:
  if P == 0:
    comb1 = 1
ans = comb0 * comb1
#print(comb0, comb1)
print(ans)

Submission status: Accepted

Solution code:
# Problem A - Biscuits

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

# initialization
even_count = 0
odd_count = 0

# count
for a in a_list:
    if a%2==0:
        even_count += 1
    else:
        odd_count = 2 ** (N - 1)
if even_count==len(a_list):
    if P==0:
        print(2 ** N)
    else:
        print(0)
else:
    print(2**(N-1))

Submission status: Accepted

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


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

odds = sum(a % 2 for a in A)
evens = len(A) - odds

print(sum(comb(odds, i) for i in range(P, odds + 1, 2)) * (2 ** evens))

Submission status: Accepted

Solution code:
def main():
    from math import factorial

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

    b = [i % 2 == 0 for i in a]
    n, m = b.count(True), b.count(False)
    c = factorial(m)

    x = 2 ** n
    y = sum([c // factorial(i) // factorial(m - i) for i in range(0, m + 1, 2)])
    z = sum([c // factorial(i) // factorial(m - i) for i in range(1, m + 1, 2)])

    if p == 0:
        print(x * y)
    else:
        print(x * z)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

A = list(map(int, input().split()))
B = []
for i in A:
    B.append(i%2)

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

t = 0

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

for i in range(1, one+1, 2):
    t += combinations_count(one, i)

if p == 1:
    print(t * 2**zero)
else:
    print(2**n - t * 2**zero)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

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

for a in A:
    if a % 2 == 0:
        cE += 1
    else:
        cO += 1


# 全て偶数
if cO == 0:
    ans = 2 ** N if P == 0 else 0
    print(ans)
else:
    # 偶数が含まれている
    # ある奇数$k$について考える
    # 残りの奇数がcO-1個，偶数がcE個残っている，この選び方は2 ** (N - 1)通り
    # 選んだ合計がSとする
    # - Sが奇数である: Akを選ぶと全体は偶数，選ばないと全体は奇数
    # - Sが偶数である: Akを選ぶと全体は奇数，選ばないと全体は偶数
    # よってそれぞれの2 ** (N - 1)通りについて，Akを選ぶ・選ばないが1通り存在する
    # print(2 ** (cO - 1) * 2 ** cE)
    print(2 ** (N - 1))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math
n,p = map(int,input().split())
a = list(map(int,input().split()))
dp = [[0,0] for _ in range(n)]
if a[0] & 1:
    dp[0][0] = 1
    dp[0][1] = 1
else:
    dp[0][0] = 2
    dp[0][1] = 0
for i in range(1,n):
    if a[i] & 1:
        dp[i][0] = dp[i-1][0]+dp[i-1][1]
        dp[i][1] = dp[i-1][0]+dp[i-1][1]
    else:
        dp[i][0] = dp[i-1][0]*2
        dp[i][1] = dp[i-1][1]*2
print(dp[n-1][p])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
def comb(n, k):
    k = min(n-k,k)
    ans = 1
    for i in range(1, k + 1):
        ans = (ans * (n + 1 - i) // i)
    return ans

def solve(N: int, P: int, A: "List[int]"):
    odd = 0
    even = 0

    for i in range(N):
        if A[i]&1:
            odd += 1
        else:
            even += 1
    
    all_pattern = 2**N
    odd_pattern = 0
    for o in range(1,odd+1):
        if o&1:
            odd_pattern += comb(odd,o)
    odd_pattern *= 2**even

    if P:
        print(odd_pattern)
    else:
        print(all_pattern-odd_pattern)
    return


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

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

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

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

Submission status: Accepted

Solution code:
def n_pow(a, n):
    if n <= 0:
        return 0
    return pow(a, n)


def main():
    bags, remainder = map(int, input().split())
    biscuits = list(map(int, input().split()))
    count = [0, 0]
    for b in biscuits:
        count[b % 2] += 1
    if remainder == 1 and count[1] == 0:
        print(0)
    elif count[1] == 0:
        print(pow(2, bags))
    else:
        print(n_pow(2, bags - 1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce
from math import factorial

sys.setrecursionlimit(4100000)
from functools import lru_cache

INF = 1 << 60
MOD = 10 ** 9 + 7

#Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ここから書き始める
n, p = map(int, input().split())
is_all_even = True
a = [0] * n
a = list(map(int, input().split()))
for i in a:
    if i % 2 == 1:
        is_all_even = False
        break
ans = 0
if is_all_even:
    if p == 0:
        ans = 2 ** n
    else:
        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()))
dp = [[0] * (N + 1) for i in range(2)]
dp[0][0] = 1
for i in range(N):
    if A[i] % 2 == 0:
        # これを選ぶとき
        dp[0][i + 1] += dp[0][i]
        dp[1][i + 1] += dp[1][i]
        # これを選ばない時
        dp[0][i + 1] += dp[0][i]
        dp[1][i + 1] += dp[1][i]
    else:
        # これを選ぶとき
        dp[0][i + 1] += dp[1][i]
        dp[1][i + 1] += dp[0][i]
        # これを選ばない時
        dp[0][i + 1] += dp[0][i]
        dp[1][i + 1] += dp[1][i]


print(dp[P][N])

Submission status: Accepted

Solution code:
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, e in enumerate(a, 1):
    for j in range(2):
        r = e % 2
        dp[i][j] = dp[i-1][j] + dp[i-1][(j-r)%2]

print(dp[n][p])

Submission status: Accepted

Solution code:
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, e in enumerate(a, 1):
    if e % 2:
        dp[i][0] = dp[i-1][0] + dp[i-1][1]
        dp[i][1] = dp[i-1][1] + dp[i-1][0]
    else:
        dp[i][0] = dp[i-1][0] * 2
        dp[i][1] = dp[i-1][1] * 2

print(dp[n][p])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, P = (int(i) for i in input().split())
    A = [int(i) % 2 for i in input().split()]
    from collections import Counter
    c = Counter(A)
    if all(a == 0 for a in A):
        print(2**N if P == 0 else 0)
    else:
        print(2**(c[1]-1) * 2**c[0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, P = (int(i) for i in input().split())
    A = [int(i) % 2 for i in input().split()]
    from collections import Counter
    c = Counter(A)
    if all(a == 0 for a in A):
        print(2**N if P == 0 else 0)
    else:
        print(2**(c[1]-1) * 2**c[0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, P = (int(i) for i in input().split())
    A = [int(i) % 2 for i in input().split()]
    from collections import Counter
    c = Counter(A)
    ans = 0
    if P == 0:
        ans = 2**c[0]
        if c[1]:
            ans *= 2**(c[1]-1)
    else:
        if c[1]:
            ans = 2**(c[1]-1)
        ans *= 2**c[0]
    # print(c)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


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

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

if odd == 0 and P == 1:
    print(0)
elif odd == 0 and P == 0:
    print(2 ** even)
else:
    ans = (2 ** even) * (2 ** (odd - 1))
    print(ans)

Submission status: Accepted

Solution code:
N,P = map(int, input().split())
A = [int(a) for a in input().split()]

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

if odd == 0:
    if P == 0:
        ans = pow(2, N)
    else:
        ans = 0
else:
    ans = pow(2, N-1)

print(ans)

Submission status: Accepted

Solution code:
N,P = map(int, input().split())
A = [int(a) for a in input().split()]

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

L = [1]*(N+1)
for i in range(N):
    L[i+1] = L[i]*(i+1)
    
def cmb(n, r):
    return L[n]//L[r]//L[n-r]

ans = pow(2, N)    
for i in range(1, odd+1, 2):
    ans -= cmb(odd, i)*pow(2, even)
if P == 1:
    ans = pow(2, N) - ans

print(ans)

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

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

N,P=map(int,input().split())
A=list(map(int,input().split()))
odd=len([i for i in A if i%2==1])
even=len([i for i in A if i%2==0])

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

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
A_li = list(map(int, input().split()))
for i, a in enumerate(A_li) :
    if a % 2 == 1 :
        break
    if i == N - 1 :
        if P == 0 : 
            print(2 ** N)
        else :
            print(0)
        exit()
print(2 ** (N - 1))

Submission status: Accepted

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

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()))
res = 0

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

for i in range((a.count(1)+1)//2):
  res = res + comb(a.count(1), 2*i+1)
if res == 0 and p == 0:
  res = 1
res = res * 2**a.count(0)
print(res)