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 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()))
o, e = 0, 0
for i in A:
    if i % 2 == 0:
        e += 1
    else:
        o += 1
ans = 0
for i in range(P, o+1, 2):
    ans += comb(o, i)
print(ans * 2 ** e)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,P= map(int, input().split())
A= list(map(int, input().split()))
A = [A[i] % 2 for i in range(N)] 
even = A.count(0)
odd = A.count(1)

anseven = 1
ansodd = 1

dic = {0:1}
for i in range(1, 51):
    dic[i] = dic[i - 1] * i

#  偶数i個選ぶ
for i in range(1, even + 1):
    anseven += dic[even] // dic[even - i] // dic[i]

if P == 0:
    #  奇数i個選ぶ
    for i in range(2, odd + 1, 2):
        ansodd += dic[odd] // dic[odd - i] // dic[i]

else:
    if odd == 0:
        print(0)
        exit()
    ansodd = 0
    #  奇数i個選ぶ
    for i in range(1, odd + 1, 2):
        ansodd += dic[odd] // dic[odd - i] // dic[i]

print(anseven * ansodd)

Submission status: Accepted

Solution code:

def comb(n, max_k, mod):
    """
    (n,k) := n個からk個選ぶ組み合わせ
    k = 0~max_Kまでを計算して返す
    """
    res = [1]*(max_k+1)
    t = 1
    for i in range(max_k+1):
        res[i] *= t
        t *= n-i
        t %= mod

    n = reduce(lambda x,y: (x*y)%mod, range(1,max_k+1), 1)
    n = modinv(n, mod)

    for i in reversed(range(max_k+1)):
        res[i] *= n
        res[i] %= mod
        n *= i
        n %= mod
    return res

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

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

evens = 0
odds = 0

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


cnt = 0
if P == 0:
    comb = 1
    cnt = 1
    for n in range(2,odds+1,2):
        comb *= (odds+2-n)*(odds+1-n)
        comb //= n*(n-1)
        cnt += comb
else:
    comb = odds
    cnt = odds
    for n in range(3,odds+1,2):
        comb *= (odds+2-n)*(odds+1-n)
        comb //= n*(n-1)
        cnt += comb

print(2**evens * cnt)

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, n_max, MOD=10 ** 9 + 7):
        """
        前処理 = O(n_max + log(MOD))
        :param self.fac[n]: n!
        :param self.facinv[n]: 1/n!
        """
        self.mod = MOD
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % MOD
            fac.append(f)
        f = pow(f, MOD - 2, MOD)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % MOD
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):  # self.C と同じ
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod


N, P = map(int, input().split())
A = []
for a in map(int, input().split()):
    A.append(a%2)
cnt1 = A.count(1)
cnt0 = N - cnt1
C = Combination(cnt1)
if P==1:
    res = sum(C(cnt1,i) for i in range(1,cnt1+1,2))*pow(2,cnt0)
else:
    res = sum(C(cnt1,i) for i in range(0,cnt1+1,2))*pow(2,cnt0)
print(res)

Submission status: Accepted

Solution code:
import sys
import math


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())


# bit全探索で愚直に
def solver1(n, p, A):
    ans = 0
    for i in range(2**n):
        x = 0
        for j in range(n):
            if (i>>j) & 1:
                x += A[j]
        if x % 2 == p:
            ans += 1
    return ans


def solver2(n, p, A):
    odd = 0
    even = 0
    for a in A:
        if a % 2 == 1:
            odd += 1
        else:
            even += 1
    if odd == 0:
        if p == 0:
            return 2 ** even
        else:
            return 0
    else:
        return 2 ** (n-1)


def main():
    n, p = inintm()
    A = inintl()
    # print(solver1(n, p, A))
    print(solver2(n, p, A))


main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

# たぶん普通にDP
# dp[i]:i番目(1-index)までの袋から偶奇が正しくなるように選ぶ場合の数

dp=[0]*(N+2)
dp[0]=(P+1)%2

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

Submission status: Accepted

Solution code:
n, p = map(int,input().split())
a=list(map(int, input().split()))
odd=0
even=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)]

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

o_pattern=0
for i in range(p,odd+1,2):
    o_pattern += cmb(odd,i)

e_pattern=0
for i in range(even+1):
    e_pattern += cmb(even,i)

print(o_pattern*e_pattern)

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

Submission status: Accepted

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

odd = 0
for i in a:
    if i%2:
        odd += 1
even = n-odd

ans = 0

for i in range(0,odd+2,2):
    if i+p > odd:
        break
    for j in range(0,even+1):
        if j > even:
            break
        
        a = 1
        for k in range(i+p):
            a *= (odd-k)
            a /= k+1
    
        b = 1
        for k in range(j):
            b *= (even-k)
            b /= k+1
       
        
        ans += a*b
print(int(ans))

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] %= 2
cnt_zero = a.count(0)
cnt_one = n - cnt_zero
ans = 0
def nCk(n, k):
    if k > n - k:
        return nCk(n, n - k)
    ret = 1
    for i in range(k):
        ret *= n - i
    for i in range(k):
        ret //= i + 1
    return ret
ans = 0
c = 0
for i in range(p, cnt_one + 1, 2):
    c += nCk(cnt_one, i)
ans = (2 ** cnt_zero) * c
print(ans)

Submission status: Accepted

Solution code:
from math import factorial
def cmb(a,b):
    return factorial(a)//factorial(b)//factorial(a-b)
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
ans = 0
if P == 0:
    for i in range(Odd+1)[::2]:
        ans += cmb(Odd,i)
else:
    for i in range(Odd+1)[1::2]:
        ans += cmb(Odd,i)
ans *= pow(2,Even)
print(ans)

Submission status: Accepted

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

if even==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()))
mod = {0:0, 1:0}
for i in a:
    mod[i % 2] += 1
ans = 0
for i in range(p, mod[1] + 1, 2):
    temp = 1
    for j in range(i):
        temp *= mod[1] - j
        temp //= j + 1
    ans += temp
for i in range(mod[0]):
    ans *= 2
print(ans)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
a = list(map(int, input().split()))
os = list(filter(lambda x: x % 2 == 1, a))
es = list(filter(lambda x: x % 2 == 0, a))

def calc_even(o_num, e_num):
    if o_num < 0 or e_num < 0:
        return 0
    # 奇数の組み合わせ数
    res = 1
    tmp = 1
    for i in range(1, o_num // 2 + 1):
        tmp *= (o_num - i * 2 + 2) * (o_num - i * 2 + 1)
        tmp /= 2 * i * (2 * i - 1)
        res += tmp
    # 偶数の組み合わせ数
    res *= 2 ** e_num
    return res

def calc_odd(o_num, e_num):
    if o_num < 0 or e_num < 0:
        return 0
    # 奇数の組み合わせ数
    tmp = o_num
    res = tmp
    end = o_num if o_num % 2 == 1 else o_num-1
    for i in range(1, end // 2 + 1):
        tmp *= (o_num - i * 2 + 1) * (o_num - i * 2)
        tmp /= 2 * i * (2 * i + 1)
        res += tmp
    # 偶数の組み合わせ数
    res *= 2 ** e_num
    return res
if p == 0:
    res = calc_even(len(os), len(es))
    print(int(res))
else:
    res = calc_odd(len(os), len(es))
    print(int(res))

Submission status: Accepted

Solution code:
def comb(n, k):
    if k > n // 2:
        return comb(n, n - k)
    numer = 1
    denom = 1
    for i in range(k):
        numer *= n - i
        denom *= k - i
    return numer // denom


def main():
    N, P = list(map(int, input().split()))
    A = list(map(int, input().split()))
    # 合計を2で割ったあまりが0となるパターンを数える
    cnt_even_bag = len([a for a in A if a % 2 == 0])
    cnt_odd_bag = N - cnt_even_bag
    cnt_even_pattern = 2 ** cnt_even_bag
    cnt_odd_pattern = 0
    for c in range(1, cnt_odd_bag + 1, 2):
        cnt_odd_pattern += comb(cnt_odd_bag, c)
    cnt_even = cnt_even_pattern * cnt_odd_pattern
    if P == 1:
        print(cnt_even)
    else:
        print(2 ** N - cnt_even)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
a=list(map(int,input().split()))
even=0
odd=0
for i in a:
    if i%2==0:
        even+=1
    else:
        odd+=1
import math
ans=2**even
if p==0:
    m=odd//2
    t=1
    for i in range(1,m+1):
        i*=2
        t+=math.factorial(odd)/math.factorial(i)/math.factorial(odd-i)
else:
    m=(odd+1)//2
    t=0
    for i in range(1,m+1):
        i=2*i-1
        t+=math.factorial(odd)/math.factorial(i)/math.factorial(odd-i)
ans*=t
print(int(ans))

Submission status: Accepted

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

n0 = 0
n1 = 0

for i in range(n):
    if a[i] % 2 == 0:
        n0 += 1
    else:
        n1 += 1

x = 0
if p == 0:
    for i in range(0, n1+1, 2):
        x += comb(n1, i)
else:
    for i in range(1, n1+1, 2):
        x += comb(n1, i)

print(2**n0 * x)

Submission status: Accepted

Solution code:
import math
def main():
    N, P = map(int, input().split())
    A = [int(a) for a in input().split()]
    modA = list()

    for a in A:
        modA.append(a % 2)

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

    ans = tmp = 0
    f = math.factorial
    if P == 0:
        for i in range(0, one + 1, 2):
            tmp += f(one) // (f(i) * f(one - i))
    else:
        for i in range(1, one + 1, 2):
            tmp += f(one) // (f(i) * f(one - i))

    if zero > 0:
        ans = tmp * 2 ** zero
    else:
        ans = tmp

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import factorial
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
def comb(a,b):
    return factorial(a)//(factorial(a-b)*factorial(b))
n_even=0
n_odd=0
for i in range(even+1):
    n_even+=comb(even,i)

if p==1:
    for i in range(1,odd+1,2):
        n_odd+=comb(odd,i)
else:
    for i in range(0,odd+1,2):
        n_odd+=comb(odd,i)
print(n_even*n_odd)

Submission status: Accepted

Solution code:
import sys
import math
import copy
import heapq
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        # self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        # for i in range(1, self.h+1):
        #     for j in range(1, self.w+1):
        #         cx, cy = j, i
        #         for dx, dy in move_eight:
        #             nx, ny = dx + cx, dy + cy

def judge(mid, cnt, n):
    xx = cnt[0]
    if ((mid+1) * (xx-1)) >= n:
        return False
    elif (mid+1) * xx <= n:
        return True
    yoyu = n % (mid+1)
    if Counter(cnt)[xx] <= yoyu:
        return True
    else:
        return False



def solve():
    n, k = getList()
    nums = getList()
    for num in nums:
        if num % 2 == 1:
            print(pow(2, n-1))
            return
    if k == 0:
        print(pow(2, n))
    else:
        print(0)
def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

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

even = 0
odd = 0

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
from math import factorial

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

cnt = [0,0]
for i in a:
    cnt[i%2] += 1

ans = 0

while True:
    if p > cnt[1]:
        break
    ans += factorial(cnt[1]) // factorial(p) // factorial(cnt[1] - p)
    p += 2

print(ans * 2 ** cnt[0])

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

count = 0
for i in a:
    if i%2 == 0:
        count += 1
if count == n:
    if p == 1:
        print(0)
    else:
        print(2**n)
else:
    print(2**(n-1))

Submission status: Accepted

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

Submission status: Accepted

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


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    n, p = MI()
    a = LI()
    num_0 = 0
    num_1 = 0
    for i in range(n):
        if a[i] % 2 == 0:
            num_0 += 1
        else:
            num_1 += 1

    s_1 = 0
    while p <= num_1:
        cmb = math.factorial(num_1) // (
            math.factorial(num_1 - p) * math.factorial(p)
        )
        s_1 += cmb
        p += 2

    print(s_1 * (2 ** num_0))


main()

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 sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, P = mapint()
As = list(mapint())
bit = [a%2 for a in As]

pos = {}
pos[0] = 1
for i in range(1, N+1):
    pos[i] = pos[i-1]*i
dic = {}
dic[0] = 0
dic[1] = 0
for i in bit:
    dic[i] += 1

ans = 2**dic[0]
if P==1:
    if dic[1]<1:
        print(0)
        exit(0)
    else:
        pass
        # ans*=dic[1]
        # dic[1] -= 1
val = 0
for i in range(dic[1]//2+1):
    val += pos[dic[1]]//pos[i*2]//pos[dic[1]-i*2]
print(val*ans)

Submission status: Accepted

Solution code:
from scipy.special import comb
n, p, *A = map(int, open(0).read().split())
o = sum(a%2 for a in A)
e = n - o

s = 0
for i in range(p, o+1, 2):
  s += comb(o, i, exact=True)
s *= pow(2, e)
print(s)

Submission status: Accepted

Solution code:
from scipy.special import comb
n, p, *A = map(int, open(0).read().split())
odd = sum(a%2 for a in A)
even = n - odd

if p:
  s = 0
  for i in range(1, odd+1, 2):
    s += comb(odd, i, exact=True)
  s *= pow(2, even)
  print(s)
else:
  s = 0
  for i in range(0, odd+1, 2):
    s += comb(odd, i, exact=True)
  s *= pow(2, even)
  print(s)

Submission status: Accepted

Solution code:
# nCk ( O(N) )
N_MAX = 100
MOD = 10**9 + 7
fac, finv, inv = [0]*N_MAX ,[0]*N_MAX, [0]*N_MAX
def com_init():
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, N_MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

def com(n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


n,p = map(int, input().split())
al = list(map(int, input().split()))
zero = 0
one = 0
com_init()
for a in al:
    if a%2 == 0: zero+=1
    else: one+=1


zero_comb = pow(2,zero)
one_comb = 0
if p == 0:
    for i in range(0,one+1,2):
        one_comb += com(one,i)
else:
    for i in range(1,one+1,2):
        one_comb += com(one,i)

print(zero_comb*one_comb)

Submission status: Accepted

Solution code:
from scipy.special import comb

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

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

if P == 0:
    # select even cnt from o
    t = 0
    for i in range(0, o+1, 2):
        t += comb(o, i, True)
    print(2**e * t)
else:
    t = 0
    for i in range(1, o+1, 2):
        t += comb(o, i, True)
    print(2**e * t)

Submission status: Accepted

Solution code:
import collections
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()))
H = [i%2 for i in A]
B = collections.Counter(H)[1]

ans = 0
for i in range(1,B//2+1):
    ans += combinations_count(B, 2*i)
C = (ans+1) * (2**(len(A)-B))
print(C if P == 0 else 2**N - C)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,p = readInts()
A = readInts()
odd = 0
for i in range(n):
    # count odd numbers
    # you can use Binomial coefficient
    # if P = 0, you should calculate this in using an odd number of odd numbers
    # else even numbers
    if A[i]%2:
        odd += 1
if odd == 0:
    if p == 0:
        print(2**n)
    else:
        print(0)
else:
    print(2**(n-1)) # 2**(n-1) = 2**(m-1) choosing odd * 2**(n-m) choosing even

Submission status: Accepted

Solution code:
from scipy.special import comb
n,p = map(int, input().split())
A = list(map(int, input().split()))
cnt = [0,0] #偶数,奇数
for a in A:
    if a%2==0: cnt[0] += 1
    else: cnt[1] += 1
      
ans = 0
if p==0: #偶数＋奇数を偶数個(0個含む)
    for i in range(0,cnt[1]+1,2):
        ans += comb(cnt[1],i,exact=True)
    ans *= 2**cnt[0]
else: #偶数＋奇数を奇数個
    for i in range(1,cnt[1]+1,2):
        ans += comb(cnt[1],i,exact=True)
    ans *= 2**cnt[0]
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from math import factorial

n,p=nii()
a=lnii()

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

def solve(q):
  num=0
  while q<=y:
    num+=factorial(y)//(factorial(q)*factorial(y-q))
    q+=2
  return num

ans=2**x
if p==0:
  num=solve(0)
else:
  num=solve(1)

print(ans*num)

Submission status: Accepted

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

print(dp[N][P])

Submission status: Accepted

Solution code:
def solve():
  N, P = map(int, input().split())
  A = list(map(int, input().split()))
  zero,one = 0,0
  for i in range(N):
    if A[i]%2==0:
      zero += 1
    else:
      one += 1
  ans = pow(2,N-1)
  if P==1 and one == 0:
    return 0
  if P==0 and one == 0:
    return pow(2,N)
  return ans
print(solve())

Submission status: Accepted

Solution code:
import math

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

remainders = [a%2 for a in A]

odd = remainders.count(1)
even = remainders.count(0)

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

ans = 0
for n in range(N+1):
  for p in range(P,n+1,2):
    if odd >= p and even >= n-p:
      ans += combinations_count(odd,p) * combinations_count(even,n-p)

print(ans)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
la = [int(i) % 2 for i in input().split()]

n0 = sum(1 for a in la if a % 2 == 0)
n1 = sum(1 for a in la if a % 2 == 1)


def combi(n, k):
    c = 1
    for i in range(1, n + 1):
        c *= i
    for i in range(1, k + 1):
        c //= i
    for i in range(1, n - k + 1):
        c //= i
    return c


def answer():
    if p == 0:
        c0 = 2 ** n0
        c1 = 0
        for i in range(0, n1 + 1, 2):
            c1 += combi(n1, i)
        return c0 * c1
    else:
        c0 = 2 ** n0
        c1 = 0
        for i in range(1, n1 + 1, 2):
            c1 += combi(n1, i)
        return c0 * c1

print(answer())

Submission status: Accepted

Solution code:
from math import factorial as fa
def comb(n, r):
    return fa(n)//(fa(n-r)*fa(r))
n, p = map(int, input().split())
A = list(map(lambda x:int(x)%2, input().split()))
even = A.count(0)
odd = A.count(1)
ans = 0
for i in range(p,odd+1,2):
    ans += comb(odd, i)
print(ans*pow(2,even))

Submission status: Accepted

Solution code:
from collections import Counter

MOD = 10**9+7
MAX_N = 50
inv = [0] * (MAX_N+1)
finv = [0] * (MAX_N+1)
fac = [0] * (MAX_N+1)
inv[1] = 1
finv[0] = 1; finv[1] = 1
fac[0] = 1; fac[1] = 1

def COM_init():
    for i in range(2, MAX_N+1):
        inv[i] = -(MOD//i)*inv[MOD%i]%MOD
        finv[i] = finv[i-1]*inv[i]%MOD
        fac[i] = fac[i-1]*i%MOD

def COM(a, b):
    if a < 0 or b < 0:return 0
    if a < b:return 0
    
    return fac[a]*finv[a-b]*finv[b]%MOD

def main():
    N, P = map(int, input().split())
    A = list(map(int, input().split()))
    B = [a%2 for a in A]
    c = Counter(B)
    
    n0 = c[0]
    n1 = c[1]
    ans = 0
    COM_init()
    for i in range(P, n1+1, 2):
        ans += pow(2, n0) * COM(n1, i)

    print(ans) 
         

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, P = getNM()
A = getList()
for i in range(N):
    if A[i] % 2 == 0:
        A[i] = 0
    else:
        A[i] = 1

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

for i in range(1, N):
    if A[i] == 0:
        # 選ぶ場合、選ばない場合
        dp[i][0] += 2 * dp[i - 1][0]
        dp[i][1] += 2 * dp[i - 1][1]
    else:
        dp[i][0] += (dp[i - 1][0] + dp[i - 1][1])
        dp[i][1] += (dp[i - 1][0] + dp[i - 1][1])

print(dp[N - 1][P])

Submission status: Accepted

Solution code:
import sys,math
input = sys.stdin.readline

def f(s):
    n = int(s)%2
    return n

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

c0 = A.count(0)
c1 = A.count(1)
fact = [1]* (c1+1)
for i in range(1,c1+1):
    fact[i]= fact[i-1]*i

cnt = 0
for i in range(P,c1+1,2):
    cnt += fact[c1]//fact[i]//fact[c1-i]

print(cnt*pow(2,c0))

Submission status: Accepted

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


def read():
    N, P = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, P, A


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


def solve(N, P, A):
    B = Counter([a % 2 for a in A])
    C0 = binom_64bit(B[0])
    C1 = binom_64bit(B[1])
    ans = 0
    if P == 1:
        for i in range(0, B[0]+1):
            for j in range(1, B[1]+1, 2):
                ans += C0[i] * C1[j]
    else:
        for i in range(0, B[0]+1):
            for j in range(0, B[1]+1, 2):
                ans += C0[i] * C1[j]
    return ans


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from math import comb

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

    zero = 0
    one = 0

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

    ans = 0
    q = 2 ** zero

    if p == 0:
        for x in range(0, one + 1, 2):
            ans += q * comb(one, x)
    else:
        for x in range(1, one + 1, 2):
            ans += q * comb(one, x)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for a in A:
  if a % 2 != 0:
    break 
else:
  if p == 1: 
    print(0)
    exit()
  if p == 0: 
    print(2**n)
    exit()
  
ans = 2**(n-1)
print(ans)