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:
import sys
from functools import reduce
from operator import mul
# sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def cmb(n: int, r: int):
    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 = input_int_list()
    A = input_int_list()
    even = 0
    odd = 0
    for a in A:
        if a % 2 == 1:
            odd += 1
        else:
            even += 1

    if p == 1:
        ans = 2**even
        tmp = 0
        for i in range(1, odd + 1, 2):
            tmp += cmb(odd, i)
        print(ans * tmp)
    elif p == 0:
        ans = 2**even
        tmp = 0
        for i in range(0, odd + 1, 2):
            tmp += cmb(odd, i)
        print(ans * tmp)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()))
oddC = 0
evenC = 0
for a in A:
    if a % 2 == 1:
        oddC += 1
    else:
        evenC += 1
c = 0
if P == 0:
    oddcombi = 0
    for i in range(oddC+1):
        if i % 2 == 1:
            continue
        oddcombi += combinations_count(oddC,i)
    evencombi = 0
    for i in range(evenC+1):
        evencombi += combinations_count(evenC,i)
    print(oddcombi*evencombi)
else:
    oddcombi = 0
    for i in range(oddC+1):
        if i % 2 == 0:
            continue
        oddcombi += combinations_count(oddC,i)
    evencombi = 0
    for i in range(evenC+1):
        evencombi += combinations_count(evenC,i)
    print(oddcombi*evencombi)

Submission status: Accepted

Solution code:
import sys, math
from functools import lru_cache
from collections import defaultdict
from decimal import Decimal
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N, P = mi()
    A = list(mi())

    if all(a%2==0 for a in A):
        print(0 if P else pow(2, N))
    else:
        print(pow(2, N-1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
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==0:
    even+=1
  else:
    odd+=1
ans=0
t=1
while t<=odd:
  res=math.factorial(odd)//(math.factorial(t)*math.factorial(odd-t))
  t+=2
  if even!=0:
    w=0
    while w<=even:
      res1=math.factorial(even)//(math.factorial(w)*math.factorial(even-w))
      w+=1
      ans+=res*res1
  else:
    ans+=res
if p==1:
  print(ans)
else:
  print(2**n-ans)

Submission status: Accepted

Solution code:
import math


def combination(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 = 0
even = 0
for a in A:
    if a % 2 == 0:
        even += 1
    else:
        odd += 1

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

Submission status: Accepted

Solution code:
import math

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

zero_count = 0
one_count = 0

for num in a:
    if num % 2 == 0:
        zero_count += 1
    else:
        one_count += 1

coef = 2 ** zero_count

ans = 0

for i in range(one_count + 1):
    if i % 2 != p:
        continue
        
    ans += math.factorial(one_count) // math.factorial(one_count - i) // math.factorial(i)
print(ans * coef)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from math import *

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))

N,P = mint()
A = lint()
odd = len([a for a in A if a%2!=0])
if odd==0:
    print(0 if P else 2**N)
else:
    print(2**(N-1))

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from math import *

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))

N,P = mint()
A = lint()
even = len([a for a in A if a%2==0])
odd = N-even
if odd==0:
    print(0 if P else 2**N)
else:
    print(2**(N-1))

Submission status: Accepted

Solution code:
# 47 A - Biscuits
N,P = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A,reverse = False)

# dp[i][p] i 番目までの袋を使ったときに余り p になる選び方
dp = [[0]*2 for _ in range(N+1)]

# 初期条件 (何も選ばないとき余りは 0)
dp[0] = [1,0]

for v in range(1,N+1):
    # 偶数の袋 (偶数を足しても足さなくても偶奇は変わらない)
    if A[v-1]%2 == 0:
        dp[v][0] = dp[v-1][0]*2
        dp[v][1] = dp[v-1][1]*2
    # 奇数の袋 (足すと偶奇が反転する)
    else:
        # 奇数の袋を選んだとき + 選ばなかったとき
        dp[v][0] = dp[v-1][1] + dp[v-1][0]
        dp[v][1] = dp[v-1][0] + dp[v-1][1]
print(dp[N][P])

Submission status: Accepted

Solution code:
import itertools
import math
from math import factorial

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

#奇数の袋、偶数の袋の個数を求める。
odd = 0
even = 0

for A in As:
    if(A % 2 == 0):
        even += 1
    else:
        odd += 1

#偶数の組み合わせを求める。
#偶数の組み合わせは0~N個のすべての組み合わせである。
even_combi = 0

for i in range(even+1):
    even_combi += math.factorial(even) // math.factorial(i) // math.factorial(even-i)

#print(even_combi)

#奇数の組み合わせを求める。
#奇数の組み合わせは、Pの値によって変わる。

#Pが0の時
odd_combi = 0

if(P == 0):
    for i in range(0,odd + 1,2):
        odd_combi += math.factorial(odd) // math.factorial(i) // math.factorial(odd-i)

else:
    for i in range(1, odd + 1 , 2):
        odd_combi += math.factorial(odd) // math.factorial(i) // math.factorial(odd-(i))

print(odd_combi*even_combi)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
A = list(map(int, input().split()))
B = [a % 2 for a in A]
count_0 = B.count(0)
count_1 = B.count(1)

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

Submission status: Accepted

Solution code:
import math


N, P = map(int, input().split())
A = list(map(int, input().split()))
B = [a % 2 for a in A]
count_0 = B.count(0)
count_1 = B.count(1)


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


x = y = 0
if count_0 == 0:
    x = 1
else:
    if P == 1 and count_1 == 0:
        x = 0
    else:
        for i in range(count_0 + 1):
            x += comb_count(count_0, i)

if count_1 == 0:
    y = 1
else:
    if P == 0:
        for i in range(0, count_1 + 1, 2):
            y += comb_count(count_1, i)
    else:
        for i in range(1, count_1 + 1, 2):
            y += comb_count(count_1, i)

print(x * y)

Submission status: Accepted

Solution code:
n,p = map(int,input().split())
a = list(map(int,input().split()))
odd = 0
even = 0
for ai in a:
    if(ai%2==0):
        even += 1
    else:
        odd += 1

if(p==1)&(odd==0):
    print(0)
elif(p==0)&(odd==0):
    print(2**n)
else:
    print(2**(n-1))

Submission status: Accepted

Solution code:
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=[int(x)%2 for x in input().split()]
z=a.count(0)
o=a.count(1)
onum=0
if p:
  i=1
  while i<=o:
    onum+=combinations_count(o, i)
    i+=2
else:
  i=0
  while i<=o:
    onum+=combinations_count(o, i)
    i+=2
print((2**z)*onum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math


# 組み合わせの計算
def C(n, r):
    ret = math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    return ret


# 組み合わせの総和こ計算
# nCr + nCr-1 + ... + nC0
def sum_C(n, R):
    nCr_0 = 1

    s = nCr_0
    for r in range(min(n, R)):
        nCr_1 = nCr_0 * (n - r) // (r + 1)
        nCr_0 = nCr_1
        s += nCr_1

    return s


# nC0, nC1, nC2, ..., nCrの答えをlistで返す
def list_conb(n, R):
    nCr_0 = 1

    ret = [nCr_0]
    for r in range(min(n, R)):
        nCr_1 = nCr_0 * (n - r) // (r + 1)
        ret.append(nCr_1)
        nCr_0 = nCr_1

    return ret


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

    A = [a % 2 for a in A]

    n_1 = sum(A)
    n_0 = N - n_1

    # 0 -> 1の数が偶数
    # 1 -> 1の数が奇数

    c = 0
    # 1の袋をi個選び0の袋を好きな個数選ぶ
    if P == 0:
        r = range(0, n_1 + 1, 2)
    else:
        r = range(1, n_1 + 1, 2)

    for i in r:  # 偶数
        if N - i < 0:
            break
        c += C(n_1, i) * sum_C(n_0, N - i)

    print(c)


main()

Submission status: Accepted

Solution code:
import math
n,p = map(int,input().split())
ls = list(map(int,input().split()))
lo = []
le = []
def combinations_count(n, r): #組み合わせ(nCr)
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
for i in ls:
    if i % 2 == 0:
        le.append(i)
    else:
        lo.append(i)
x = len(lo)
y = len(le)
if p == 0:
    a = 1
    if x != 0:
        if x % 2 == 0:
            r = x
        else:
            r = x - 1
        a = 0
        for j in range(0,r+1,2):
            a += combinations_count(x, j)
    b = 1
    if y != 0:
        b = 0
        for k in range(y+1):
            b += combinations_count(y, k)
    print(a*b)
else:
    if x != 0:
        if x % 2 == 0:
            r = x - 1
        else:
            r = x
        a = 0
        for j in range(1,r+1,2):
            a += combinations_count(x, j)
    else:
        a = 0
    b = 1
    if y != 0:
        b = 0
        for k in range(y+1):
            b += combinations_count(y, k)
    print(a*b)

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

even_answer = 2 ** even

check = p


def kaijo(i):
    if (i == 1) or (i == 0):
        return 1
    return i * kaijo(i - 1)


odd_answer = 0
while check <= odd:
    # print(kaijo(n) / kaijo(check) / kaijo(n - check))
    odd_answer = odd_answer + (kaijo(odd) / kaijo(check) / kaijo(odd - check))
    # print(odd_answer)
    check += 2

print(int(odd_answer * even_answer))

Submission status: Accepted

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

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

if dic["odd"] == 0:
    if P == 1:
        print(0)
    else:
        print(2 ** dic["even"])

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

Submission status: Accepted

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

odd = [i for i in lis if i % 2==1]
even = [i for i in lis if i % 2 == 0]

if len(odd) == 0:
    if p == 0:
        print(2**n)
    else:
        print(0)
else:
    odd_m = len(odd)
    even_m = len(even)
    t1 = 2**even_m
    t2 = 2**(odd_m-1)
    print(t1*t2)

Submission status: Accepted

Solution code:
from math import factorial

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

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

n=num_k//2
ans_k=0
for i in range(0,n*2+1,2):
    ans_k+=factorial(num_k)/factorial(i)/factorial(num_k-i)

ans_g=2**(num_g)

ans=int(ans_k*ans_g)

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

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


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

x = sum(A[i] % 2 == 0 for i in range(N))  # Aiの中で、偶数であるものの個数
y = N-x  # Aiの中で、奇数であるものの個数

if y == 0:
    print(0 if P == 1 else 2**x)
else:
    print(2**(x+y-1))

Submission status: Accepted

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

def comb_dp():
    """
    dpテーブルを作ってnCkを計算.
    modのpは素数でなくてよい.
    1 <= k <= n <= 2000程度
    O(MAX_C ** 2).
    """
    Com = [[0]*MAX_C for _ in range(MAX_C)]
    Com[0][0] = 1
    for i in range(1, MAX_C):
        # iC0 = 1
        Com[i][0] = 1
        for j in range(1, MAX_C):
            # iCj = i-1_C_j-1 + i-1_C_j mod p
            Com[i][j] = (Com[i-1][j-1] + Com[i-1][j])
        
    return Com
Com = comb_dp()
if P == 0:
    is_even = [A[i]%2==0 for i in range(N)]
    num_e = is_even.count(True)
    num_o = N-num_e
    tmp1 = 0
    tmp2 = 0
    for i in range(0, num_e+1):
        tmp1 += Com[num_e][i]
    for i in range(0, num_o+1, 2):
        tmp2 += Com[num_o][i]
    print(tmp1*tmp2)
else:
    is_even = [A[i]%2==0 for i in range(N)]
    num_e = is_even.count(True)
    num_o = N-num_e
    tmp1 = 0
    tmp2 = 0
    for i in range(0, num_e+1):
        tmp1 += Com[num_e][i]
    for i in range(1, num_o+1, 2):
        tmp2 += Com[num_o][i]
    print(tmp1*tmp2)

Submission status: Accepted

Solution code:
from scipy.special import comb
N, P = map(int, input().split())
A = list(map(int, input().split()))
MAX_C = 100

# def comb_dp():
#     """
#     dpテーブルを作ってnCkを計算.
#     modのpは素数でなくてよい.
#     1 <= k <= n <= 2000程度
#     O(MAX_C ** 2).
#     """
#     Com = [[0]*MAX_C for _ in range(MAX_C)]
#     for i in range(1, MAX_C):
#         # iC0 = 1
#         Com[i][0] = 1
#         for j in range(1, MAX_C):
#             # iCj = i-1_C_j-1 + i-1_C_j mod p
#             Com[i][j] = (Com[i-1][j-1] + Com[i-1][j])
        
#     return Com
# Com = comb_dp()
# print(Com[2][1])
# print(Com[2][2])
if P == 0:
    is_even = [A[i]%2==0 for i in range(N)]
    num_e = is_even.count(True)
    num_o = N-num_e
    tmp1 = 0
    tmp2 = 0
    for i in range(0, num_e+1):
        tmp1 += comb(num_e, i, exact=True)
    for i in range(0, num_o+1, 2):
        tmp2 += comb(num_o, i, exact=True)
    print(tmp1*tmp2)
else:
    is_even = [A[i]%2==0 for i in range(N)]
    num_e = is_even.count(True)
    num_o = N-num_e
    tmp1 = 0
    tmp2 = 0
    for i in range(0, num_e+1):
        tmp1 += comb(num_e, i, exact=True)
    for i in range(1, num_o+1, 2):
        tmp2 += comb(num_o, i, exact=True)
    print(tmp1*tmp2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
n, p, *a = map(int, open(0).read().split())


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


memo = [0, 0]
for i in range(n):
    memo[a[i] % 2] += 1
# p == 0


ans = 0
if p == 0:
    for i in range(0, memo[1] + 1, 2):
        ans += c(memo[1], i) * pow(2, memo[0])
else:
    for i in range(1, memo[1] + 1, 2):
        ans += c(memo[1], i) * pow(2, memo[0])
# p == 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))

def main():
    N,P = map(int,input().split())
    A = list(map(int,input().split()))
    num1 = 0
    num0 = 0
    for i in range(N):
        tmp = A[i]%2
        if tmp == 0:
            num0 += 1
        else:
            num1 += 1
    #print(num1,num0)
    ans2 = 0
    for i in range(num0+1):
        ans2 += comb(num0,i)

    if P == 1:
        syo = num1//2
        amari = num1%2
        tmp = syo + amari
        i = 1
        ans = 0
        for j in range(tmp):
            ans += comb(num1,i)
            i += 2


        ans = ans*ans2
        return ans

    else:
        syo = num1//2
        tmp = syo+1
        i = 0
        ans = 0
        #print(tmp)
        for j in range(tmp):
            #print(i,num1)
            if i == 0:
                ans += 1
                i += 2
            else:
                ans += comb(num1,i)
                i += 2

        ans = ans*ans2
        return ans

#print(comb(3,2))
print(main())

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
a=list(map(int, input().split()))
from math import factorial
o=0;e=0
for i in a:
    if i%2==0:e+=1
    else:o+=1
if p==0:
    odds=0
    for i in range(0,o+1,2):
        odds+=factorial(o)//factorial(i)//factorial(o-i)
else:
    odds=0
    for i in range(1,o+1,2):
        odds+=factorial(o)//factorial(i)//factorial(o-i)
print(odds*2**e)

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())
s = list(map(int,input().split()))
x,y,ans = 0,0,0
for i in s:
    if i%2 == 0:
        x += 1
    else:
        y += 1

if p == 1:
    k = 0
    for i in range(1,y+1,2):
        k += comb(y,i)
    g = 0
    for i in range(x+1):
        g += comb(x,i)
    print(k*g)
else:
    g = 0
    for i in range(x+1):
        g += comb(x,i)
    k = 0
    for i in range(0,y+1,2):
        k += comb(y,i)
    print(k*g)

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
    a[i]=a[i]%2
one=sum(a)
zero=n-one
if p==1 and one==0:
    print(0)
    exit()
if p==0 and one==0:
    print(2**n)
    exit()
print(2**(n-1))

Submission status: Accepted

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

a = sum([x % 2 == 1 for x in arr])
b = n - a


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


MOD = 10**18 + 7
N = 10**6
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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)

start = p

# aから奇数個 or 偶数個選ぶ
ans = 0
for i in range(p, a + 1, 2):
    for j in range(b + 1):
        ans += cmb(a, i, MOD) * cmb(b, j, MOD)

print(ans)

Submission status: Accepted

Solution code:
import math
 
def combination(n, k):
    return math.factorial(n) // math.factorial(k) // math.factorial(n - k)    

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

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

kisu = 0
gusu = 0

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

sum_gu = 2**gusu

if P%2==0:
    sum_ki = 0
    for i in range(2,kisu+1, 2):
        sum_ki += combination(kisu, i)
    sum_ki *= sum_gu
    print(sum_gu+sum_ki)
else:
    sum_ki = 0
    for i in range(1,kisu+1, 2):
        sum_ki += combination(kisu, i)
    print(sum_gu*sum_ki)

Submission status: Accepted

Solution code:
from collections import deque

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

even = 0
odd = 0

for a in input().split():
    check = int(a)

    if check % 2 == 0:
        even += 1
    else:
        odd += 1


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


# 奇数にする場合
result = 0
if P == 1:
    # 奇数を奇数個選ぶ
    for i in range(1, odd+1, 2):
        result += comb(odd, i)

# 偶数にする場合
else:
    # 奇数を選ばない、もしくは偶数個選ぶ
    for i in range(0, odd+1, 2):
        result += comb(odd, i)

if even == 0:
    mul = 1
else:
    mul = 2 ** even

result *= mul
print(result)

Submission status: Accepted

Solution code:
def LI():
    return list(map(int, input().split()))


N, P = LI()
A = LI()
gu = 0
ki = 0
for i in range(N):
    if A[i] % 2 == 0:
        gu += 1
    else:
        ki += 1


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

Submission status: Accepted

Solution code:
Limit = 100
CMB = [[0]*(Limit+1) for _ in range(Limit+1)]
def cmb_table(Limit):
  for i in range(Limit+1):
    for j in range(Limit+1):
      if j == 0 or j == i: #端っこの場合
        CMB[i][j] = 1
      else:
        CMB[i][j] = CMB[i-1][j-1] + CMB[i-1][j]

cmb_table(Limit)
#print(CMB[0][3])
N,P = map(int,input().split())
A = list(map(int,input().split()))
odd = 0; even = 0
for x in A:
  if x%2 == 0:
    even +=1
  else:
    odd +=1
ans = 0
if P%2 == 0: #偶数の場合
  for x in range(even+1):
    E = x
    if E == 0:
      face = 1
    else:
      face = CMB[even][E]
    O = 0
    while E+O <= N:
      if O == 0:
        faco = 1
      else:
        faco += CMB[odd][O]
      O += 2
    #print(E,face,faco)
    ans += face*faco #どっちも選ばなくてOK
else:
  for x in range(even+1):
    E = x
    if E == 0:
      face = 1
    else:
      face = CMB[even][E]
    O = 1
    while E+O <= N:
      if O == 1:
        faco = CMB[odd][O]
      else:
        faco += CMB[odd][O]
      O += 2
    #print(face,faco)
    ans += face*faco #どっちも選ばなくてOK
    
print(ans)

Submission status: Accepted

Solution code:
N,P = map(int,input().split())
def combi(N,K):
    a = 1
    for i in range(K):
        a *= N-i
    for j in range(K):
        a /= j+1
    return a

ans = 0
lis = list(map(int,input().split()))
ls = []
for a in lis:
    ls.append(a%2)
one = ls.count(1)
zero = ls.count(0)
pattern_a = 0
pattern_b = 0
for j in range(zero+1):
    pattern_b += combi(zero,j)
time = 0
while time<=one:
    if time%2 ==P:
        pattern_a += combi(one,time)
    time += 1
print(int(pattern_a*pattern_b))

Submission status: Accepted

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

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

a0 = 0
a1 = 0
for a in al:
    if a%2 == 0:
        a0 += 1
    else:
        a1 += 1

ans = pow(2,a0)
ans2 = 0
if p == 0:
    for i in range(0,51,2):
        if a1 < i:break
        ans2 += com(a1,i)

else:
    for i in range(1,51,2):
        if a1 < i:break
        ans2 += com(a1,i)
print(ans*ans2)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

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

    count_even, count_odd = 0, 0
    for a in A:
        if a % 2 == 0:
            count_even += 1
        else:
            count_odd += 1
    
    ans = -1
    # print(N, P, A)
    # print(count_even, count_odd)
    if count_odd == 0:
        # 偶数しかない
        if P == 0:
            # 偶数にしたい => どれでもOK
            ans = 2 ** N
        else:
            # 奇数枚は食べられない
            ans = 0
    else:
        # 奇数が1以上存在するので，ある1つ以外の和Sを考える
        # S is odd: 食べたらeven，食べないとodd => 2 ^ (N-1) パターン
        # S is even: 食べたらodd，食べないとeven
        ans = 2 ** (N - 1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 2 ** 61 - 1
table_len = 100

fac = [1, 1]
for i in range(2, table_len):
    fac.append(fac[-1] * i % MOD)

finv = [0] * table_len
finv[-1] = pow(fac[-1], MOD - 2, MOD)
for i in range(table_len-1, 0, -1):
    finv[i-1] = finv[i] * i % MOD

C = 0
D = 0
for A in As:
    if A % 2:
        D += 1
    else:
        C += 1

ans = pow(2, C)
ans *= sum( ((fac[D] * finv[i] * finv[D-i])%MOD for i in range(P, D+1, 2)) )
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
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 LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


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

x,y = 0,0
for a in A:
    if a % 2 == 0:
        x += 1
    else:
        y += 1

if y == 0:
    if P == 1:
        print(0)
    else:
        print(2**x)
else:
    print(2**(x+y-1))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    def select(n,k):
        return math.factorial(n)//(math.factorial(k)*math.factorial(n-k))
    n,p = LI()
    a = LI()
    a = list(map(lambda x: x%2, a))
    dic = collections.Counter(a)
    c0 = dic[0]
    c1 = dic[1]
    ans = 0

    if p == 0:
        for i in range(n+1):
            for s in range(i//2+1):
                n1 = 2*s
                n0 = i-n1
                if n0<=c0 and n1<=c1:
                    ans += select(c0,n0)*select(c1,n1)
    else:
        for i in range(1,n+1):
            for s in range((i-1)//2+1):
                n1 = 2*s+1
                n0 = i-n1
                if n0<=c0 and n1<=c1:
                    ans += select(c0,n0)*select(c1,n1)
                    
    print(ans)

main()

Submission status: Accepted

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

dp=[[0]*2 for i 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[-1][p])

Submission status: Accepted

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


from collections import Counter
n, p = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(list(map(lambda x: x % 2, a)))
a = Counter(a)
ans = 0
if p == 1:
    for i in range(1, a[1] + 1, 2):
        for j in range(a[0] + 1):
            ans += combinations_count(a[1], i) * combinations_count(a[0], j)
if p == 0:
    for i in range(0, a[1] + 1, 2):
        for j in range(a[0] + 1):
            ans += combinations_count(a[1], i) * combinations_count(a[0], j)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()))
even=0
odd=0
answer=0
for a in A:
    if a%2==0:
        even+=1
    else:
        odd+=1
if even==0:
    if P==0:
        if odd==1:
            print(0)
        else:
            for n in range(2,odd+1,2):
                answer+=combinations_count(odd,n)
            print(answer+1)
    else:
        for n in range(1,odd+1,2):
            answer+=combinations_count(odd,n)
        print(answer)
elif odd==0:
    if P==1:
        print(0)
    else:
        answer+=2**even
        print(answer)
else:
    if P==0:
        suuji=0
        for n in range(0,odd+1,2):
            suuji+=combinations_count(odd,n)
        answer+=2**even
        print(answer*suuji)
    else:
        suuji=0
        for n in range(1,odd+1,2):
            suuji+=combinations_count(odd,n)
        answer+=2**even
        print(answer*suuji)

Submission status: Accepted

Solution code:
def main():
    n,p = map(int,input().split())
    a = list(map(int,input().split()))
    D = {0:0, 1:0}
    for i in range(n):
        D[a[i]%2]+=1
    ans = 0

    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)]
    if p==0:
        for i in range(D[1]//2+1):
            ans += cmb(D[1],2*i)
    else:
        for i in range(D[1]//2):
            ans += cmb(D[1],2*i+1)
    print(ans * pow(2,D[0]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
a=list(map(int,input().split()))
d={0:0,1:0}
for i in range(n):
  d[a[i]%2]+=1
q=2**d[0]
ans=0
m=d[1]
f=[1]
for i in range(1,m+1):
  f+=[f[-1]*i]
for i in range(m+1):
  if i%2!=p:continue
  ans+=q*f[m]//f[i]//f[m-i]
print(ans)