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: Wrong Answer

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


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

even=0
odd=0
for i in a:
    if i%2 == 0:
        even+=1
    else:
        odd+=1
ans = 0
if p == 0:
    print(1<<n)

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

        i+=1

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

        i+=2
    print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


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

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

    print(ans)

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

        i+=1

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

        i+=2
    print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

import itertools
ad = [a[i]%2 for i in range(n)]

b = Counter(ad)
ama = 1
pet = p

zero = [1] * (b[0]+1)
one = [1] * (b[1]+1)
ze = [0]*2
on = [0]*2

ze[0] = 1
on[0] = 1
for i in range(1,b[0]+1):
    zero[i] = zero[i-1] * (b[0]+1-i) // i
    ze[i%2] += zero[i]
for i in range(1,b[1]+1):
    one[i] = one[i-1] * (b[1]+1-i) // i
    on[i%2] += one[i]
    
if p == 0:
    ans = (ze[0]*on[0] + ze[1]*on[1])
else:
    ans = (ze[0]*on[1] + ze[1]*on[0])
if p == 1 and b[1] == 0:
    ans = 0
    
print(ans)

Submission status: Wrong Answer

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


def readstr():
    return input().strip()


def readint():
    return int(input())


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


def readstrs():
    return input().split()


N, P = readnums()
A = map(lambda x: x % 2, readnums())

if not sum(A) and P:
    print(0)
else:
    print(2 ** N // 2)

Submission status: Wrong Answer

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


def readstr():
    return input().strip()


def readint():
    return int(input())


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


def readstrs():
    return input().split()


N, P = readnums()
A = map(lambda x: x % 2, readnums())

if not sum(A):
    print(0)
else:
    print(2 ** N // 2)

Submission status: Wrong Answer

Solution code:
import math
N, P = map(int, input().split())
A = list(map(int, input().split()))
even = 0
odd = 0
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import math
def ncr(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 i in a:
    if i%2==0:
        even+=1
    else:
        odd+=1

if p==1:
    ans=2**even
    odd_choice=0
    for i in range(1,odd+1,2):
        odd_choice+=ncr(odd,i)
    print(ans*odd_choice if even!=0 else odd_choice)

else:
    ans=2**even
    if even==0:
        ans=0
    odd_choice=0
    for i in range(0,odd+1,2):
        odd_choice+=ncr(odd,i)
    print(ans*odd_choice)

Submission status: Wrong Answer

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

odds=sum(A)
evens=N-odds 
if odds>0:
    ans=2**evens 
    ans+=2**(odds-1)
    print(ans)
else:
    if P==0:
        print(2**evens)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
N,P = map(int,input().split())
# arrA = list(map(int,input().split()))
arrA = np.array(input().split(),dtype=np.int64)

A = arrA % 2
if not (1 in A):
    if P == 1:
        print(0)
        exit()
even = 1
odd = 1
for i in sorted(A)[::-1][1:]:
    if i == 0:
        even *= 2
        odd *= 2
    else:
        even,odd = odd + even , odd + even
if P==0:
    print(even)
else:
    print(odd)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))

Submission status: Wrong Answer

Solution code:
# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
N,P = map(int,input().split())
# arrA = list(map(int,input().split()))
arrA = np.array(input().split(),dtype=np.int64)

A = arrA % 2
if not 1 in A:
    if P == 1:
        print(0)
even = 1
odd = 1
for i in A:
    if i == 0:
        even *= 2
        odd *= 2
    else:
        even = odd + even
        odd = even + odd
if P==0:
    print(even)
else:
    print(odd)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))

Submission status: Wrong Answer

Solution code:
# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
N,P = map(int,input().split())
# arrA = list(map(int,input().split()))
arrA = np.array(input().split(),dtype=np.int64)

A = arrA % 2
even = 1
odd = 0
for i in A:
    if i == 0:
        even *= 2
        odd *= 2
    else:
        even = odd + even
        odd = even + odd
if P==0:
    print(even)
else:
    print(odd)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))

Submission status: Wrong Answer

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

gu=0
ki=0

for aa in a:
    if aa%2==0:
        gu+=1
    else:
        ki+=1

gusu=2**gu
if ki>0:
    kisu=2**(ki-1)
else:
    kisu=1

print(gusu*kisu)


#pが0だったら選ぶ袋の合計が偶数
#kisu の個数が偶数

#nが1だったら選ぶ袋の合計が奇数
#gusu の個数が奇数

#nは50、全探索はできんね

Submission status: Wrong Answer

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

gu=0
ki=0

for aa in a:
    if aa%2==0:
        gu+=1
    else:
        ki+=1
count=0
if p==1:
    i=1
    while i <=ki:
        j=0
        temp=1
        while j<i:
            temp=temp*(ki-j)
            j+=1
        i+=2
        count+=temp//i
else:
    i=0
    while i <=ki:
        j=0
        temp=1
        while j<i:
            temp=temp*(ki-j)
            
            j+=1
        #print(i,temp)
        if i!=0:
            count+=temp//i
        else:
            count+=1
        i+=2
#偶数の選び方
gusu=2**gu

print(gusu*count)


#pが0だったら選ぶ袋の合計が偶数
#kisu の個数が偶数

#nが1だったら選ぶ袋の合計が奇数
#gusu の個数が奇数

#nは50、全探索はできんね

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

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

n,m = inpl()
a = inpl()
odd = even = 0
for x in a:
    if x%2: odd += 1
    else: even += 1
res = pow(2,even)
ores = eres = 0
for i in range(odd):
    if i%2 == 0:
        eres += conb(odd,i)
    else:
        ores += conb(odd,i)
if m:
    print(ores*res)
else:
    print(eres*res)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

even = 0
not_even = 0
for a in A:
    if a % 2 == 0: even += 1
    else: not_even += 1
print(even, not_even)
ans = 0
if p == 0:
    #偶数だけ
    if even != 0: a = factorial(even)
    else: a = 0
    #奇数だけ
    b = 0 
    n = 2
    while n <= not_even:
        b += combinations_count(not_even, n)
        n += 2
    print(a + b + a * b + 1)
else:
    #奇数だけ
    if not_even != 0: a = factorial(not_even)
    else: a = 0
    #偶数だけ
    b = 0
    n = 3
    while n <= even:
        b += combinations_count(even, n)
        n += 2
    print(a + b + a * b)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

if a[0]%2==0:
    even[0]=1
else:
    odd[0]=1
    even[0] = 1

for i in range(n-1):
    if a[i+1]%2==0:
        odd[i+1]+=odd[i]+1
        even[i+1]+=even[i]+1
    else:
        odd[i+1]+=even[i]+odd[i]
        even[i+1]+=odd[i]+even[i]

if p==0:
    print(even[n-1])
else:
    print(odd[n-1])

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
A = list(map(lambda x: int(x)%2, input().split()))
print(2**(N-1))

Submission status: Wrong Answer

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

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


tmp = 2**zero
ans = 0
for i in range(one//2+1):
    if p == 0:
        if i*2 > one:
            break
        ans += scipy.misc.comb(one,0+i*2)
    else:
        if i*2+1 > one:
            break
        ans += scipy.misc.comb(one,1+i*2)
print(int(ans*tmp))

Submission status: Wrong Answer

Solution code:
import math
def combinations(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()))
n0=0
n1=0
ans=0
for i in range(len(a)):
  if a[i]%2:
    a[i]=1
    n1+=1
  else:
    a[i]=0
    n0+=1
s=sum(a)
for i in range(0,s+1,2):
  ans+=combinations(n1,i)
print(ans*(2**n0))

Submission status: Wrong Answer

Solution code:
def impossible(a,b,P):
    if(b == 0 and P == 1):
        return True
    if(a == 0 and b == 1 and P == 0):
        return True
    
    return False

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

lists = list(map(int,input().split()))
dp = [0] * 2

for l in lists:
    if(l % 2 == 0):
        dp[0] += 1
    else:
        dp[1] += 1

if(impossible(dp[0],dp[1],P)):
    ans = 0
else:
    ans = 2 ** (dp[0] + dp[1] - 1)

print(ans)

Submission status: Wrong Answer

Solution code:
def impossible(p,q,P):
    if(p == 0 and q == 1 and P == 0):
        return True
    elif(q == 0 and P == 1):
        return True
    else:
        return False


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

Submission status: Wrong Answer

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

print(2 ** (ZeroOne[0]+ZeroOne[1] - 1))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from math import factorial
N, P = map(int, input().split())
A = list(map(int, input().split()))
odd, even = 0, 0
for i in range(N):
    if A[i] % 2 == 0:
        even += 1
    else:
        odd += 1
ans = 0
if P == 0:
    ans += 2 ** even
    v = ans
    ans += (odd * (odd-1)) // 2 * max(1, v)
else:
    for i in range(1, odd, 2):
        ans += factorial(odd) // (factorial(i) * factorial(odd - i)) * 2**even
print(ans)

Submission status: Wrong Answer

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

cnt_0 = sum([a % 2 == 0 for a in A])
cnt_1 = sum([a % 2 != 0 for a in A])

ans = 0
# 0枚食べる時
if P == 0:
    ans += 1
for k in range(1, N + 1):
    for i in range(0, k):
        j = k - i
        if i > cnt_0 or j > cnt_1:
            continue
        if P == 0 and j % 2 == 0:
            ans += cmb(cnt_0, i) * cmb(cnt_1, j)
        elif P == 1 and j % 2 == 1:
            ans += cmb(cnt_0, i) * cmb(cnt_1, j)

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from math import factorial


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


n,p=map(int,input().split())
A=list(map(int,input().split()))
A=[A[i]%2 for i in range(n)]

cnt=A.count(0)
ans=0
for i in range(p,n-cnt+1,2):
    ans +=cmb(n-cnt,i)
print(ans*(cnt**2))

Submission status: Wrong Answer

Solution code:
n,p = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

a_odd = [x for x in a if x % 2 == 1]
a_eve = [x for x in a if x % 2 == 0]

if len(a_odd) == 0:
    if p == 0:
        print(2 ** p)
    else:
        print(0)
else:
    print(2 ** (n-1))

Submission status: Wrong Answer

Solution code:
import sys
from math import factorial
def main():
    packages, remainder = receiveInputData()

    packages.countOddAndEven()

    even_ways = packages.calculateEvenWays()
    odd_ways_remainder0, odd_ways_remainder1 = packages.calculateOddWays()

    if remainder.isZero():
        print(even_ways * odd_ways_remainder0)
        return

    print(even_ways * odd_ways_remainder1)






class Package():
    def __init__(self, packages_list, packages_num):
        if not isinstance(packages_list, list):
            print('Package Class argument error')
            sys.exit(1)

        # 問題の制約では、1以上50以下である
        if packages_num < 1 or packages_num > 50:
            print('Package Class Restriction error')
            print(packages_num)
            sys.exit(1)

        self.packages = packages_list
        self.packages_num = packages_num

    # 中に入っているビスケットの数が偶数の袋、奇数の袋それぞれ数える
    def countOddAndEven(self):
        self.packages_num_of_odd_biscuits  = 0
        self.packages_num_of_even_biscuits = 0
        for pack_i, biscuits_num in enumerate(self.packages):
            if biscuits_num % 2 == 0:
                self.packages_num_of_even_biscuits += 1
            else:
                self.packages_num_of_odd_biscuits += 1
        print(self.packages_num_of_odd_biscuits)

    # 偶数個含まれる袋の選び方は何通りかを返す
    # 袋ごとに　食べる　食べない　の２通りなので
    # m袋あれば　2^m通り
    def calculateEvenWays(self):
        return 2 ** self.packages_num_of_even_biscuits

    def calculateOddWays(self):
        count_combination_list = self.calculateCombination(self.packages_num_of_odd_biscuits)

        # あまりPが0の場合
        # 奇数個含まれる袋は、偶数個選ばなければならない
        selected_even_odds = sum(count_combination_list[::2])

        # あまりPが1の場合
        # 奇数個含まれる袋は、奇数個選ばなければならない
        selected_odd_odds = sum(count_combination_list[1::2])

        return selected_even_odds, selected_odd_odds

    def calculateCombination(self,n):
        # i番目にはnCi
        select_ways_of_odd = [1]
        for select_num in range(1,n + 1):
            n_C_i = factorial(n) // (factorial(select_num) * factorial(n - select_num))
            select_ways_of_odd.append(n_C_i)
        return select_ways_of_odd











class Remainder():
    def __init__(self, remainder_0or1):
        if not isinstance(remainder_0or1, int):
            print('Remainder Class argument error')
            sys.exit(1)

        # 問題の制約では、0か1
        if remainder_0or1 != 0 and remainder_0or1 != 1:
            print('Remainder Class Restriction error')
            sys.exit(1)

        self.remainder = remainder_0or1


    def isZero(self):
        if self.remainder == 0:
            return True
        return False


def receiveInputData():

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

    return Package(A, N), Remainder(P)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
a=[int(x)%2 for x in input().split()]
even=0
for aa in a:
    if aa%2==0:
        even+=1

if even==n:
    if p==0:
        print(2**n)
    else:
        print(0)
else:
    dp=[[0]*3 for i in range(n+1)]
    if a[0]%2==0:
        dp[0][0]=1
        dp[0][1]=0
    else:
        dp[0][0]=0
        dp[0][1]=1    
    for i in range(n):
        for j in range(2):
            j%=2
            if a[i]%2==0:
                dp[i+1][j]=2*dp[i][j]
                dp[i+1][j+1]=2*dp[i][j+1]
            elif a[i]%2==1:
                dp[i+1][j]=dp[i][j]+dp[i][j+1]
                dp[i+1][j+1]=dp[i][j]+dp[i][j+1]
    
    print(dp[n][p])

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
a=[int(x)%2 for x in input().split()]
# print(a)

dp=[[0]*3 for i in range(n+1)]
if a[0]%2==0:
    dp[0][0]=1
    dp[0][1]=0
else:
    dp[0][0]=0
    dp[0][1]=1    
for i in range(n):
    for j in range(2):
        j%=2
        if a[i]%2==0:
            dp[i+1][j]=2*dp[i][j]
            dp[i+1][j+1]=2*dp[i][j+1]
        elif a[i]%2==1:
            dp[i+1][j]=dp[i][j]+dp[i][j+1]
            dp[i+1][j+1]=dp[i][j]+dp[i][j+1]

print(dp[n][p])

Submission status: Wrong Answer

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

odd = []
even = []
for i, aa in enumerate(a):
    if aa % 2 == 0:
        even.append(aa)
    else:
        odd.append(aa)
e = len(even)
o = len(odd)
ans = 2 ** e
od_list = [0]
bunsi = 1
bunbo = 1

for i in range(1,o):
    bunsi *= o - i + 1
    bunbo *= i
    od_list.append(bunsi//bunbo)
even_i = od_list[::2]
odd_i = od_list[1::2]
if p == 0:
    print(ans * sum(even_i))
else:
    print(ans * sum(odd_i))

Submission status: Wrong Answer

Solution code:
from math import factorial
def cmb(n,r):
    if n-r<0:
        return 0
    else:
        return factorial(n) // factorial(r) // factorial(n - r)
        

n,p,*a=map(int,open(0).read().split())

odd=sum(i%2 for i in a)
even=n-odd

print(odd,even)

x=sum(cmb(even,i)for i in range(even+1))
y=sum(cmb(odd,i)for i in range(p,odd+1,2))
print(x*y)

Submission status: Wrong Answer

Solution code:
import numpy as np


def nCr(n, r, mod = 10**9+7):
    r = min(n-r, r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


n, p = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int)
A %= 2

odd = (A == 1).sum()
even = (A == 0).sum()

base = 2 ** even
if p == 0:
    odd_to_even = 0
    for select in range(0, odd, 2):
        pattern = nCr(odd, select)
        odd_to_even += pattern

    print(base * odd_to_even)

else:
    odd_to_odd = 0
    for select in range(1, odd, 2):
        pattern = nCr(odd, select)
        odd_to_odd += pattern

    print(base * odd_to_odd)

Submission status: Wrong Answer

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 = 110  # N は必要分だけ用意する
mod = pow(10, 9) + 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]
tmp = Counter(arr)
num1 = tmp[1]
num0 = tmp[0]
debug('num', num1, num0)
ans = 0
for i in range(n + 1): #全体でi個選ぶ
    for j in range(i + 1): #1をj個選ぶ
        if j % 2 == p and num1 >= j and num0 >= i - j:
            ans += cmb(num1, j) * cmb(num0, i - j)
print(ans)

Submission status: Wrong Answer

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 = 110  # N は必要分だけ用意する
mod = pow(10, 9) + 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]
tmp = Counter(arr)
num1 = tmp[1]
num0 = tmp[0]
debug('num', num1, num0)
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: Wrong Answer

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(pow(2, odd - 1) * pow(2, even))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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
"""

mod = 10**9+7 #出力の制限
N = 10**5
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
# a = cmb(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: Wrong Answer

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 = int(sum(misc.comb(o, i) for i in range(0, o+1, 2)))
    print(sum0*(2**e))
else:
    sum1 = int(sum(misc.comb(o, i) for i in range(1, o+1, 2)))
    print(sum1*(2**e))

Submission status: Wrong Answer

Solution code:
n,p = map(int,input().split())
a = [int(i) for i in input().split()]
odd = 0
evil = 0
for i in range(n):
    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))