Tokio Marine & Nichido Fire Insurance Programming Contest 2020 - O(rand)

Given are N pairwise distinct non-negative integers A_1,A_2,\ldots,A_N. Find the number of ways to choose a set of between 1 and K numbers (inclusive) from the given numbers so that the following two conditions are satisfied:

* The bitwise AND of the chosen numbers is S.
* The bitwise OR of the chosen numbers is T.

Constraints

* 1 \leq N \leq 50
* 1 \leq K \leq N
* 0 \leq A_i < 2^{18}
* 0 \leq S < 2^{18}
* 0 \leq T < 2^{18}
* A_i \neq A_j (1 \leq i < j \leq N)

Input

Input is given from Standard Input in the following format:


N K S T
A_1 A_2 ... A_N


Output

Print the answer.

Examples

Input

3 3 0 3
1 2 3


Output

2


Input

5 3 1 7
3 4 9 1 5


Output

2


Input

5 4 0 15
3 4 9 1 5


Output

3

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127
cmb = [[0 for i in range(51)] for j in range(51)]
cmb[0][0] = 1
for i in range(51):
	for j in range(51):
		if i != 50:
			cmb[i + 1][j] += cmb[i][j]
		if j != 50 and i != 50:
			cmb[i + 1][j + 1] += cmb[i][j]
for i in range(1, 51):
	for j in range(2, 51):
		cmb[i][j] += cmb[i][j - 1]
import random
(N, K, T, S) = map(int, input().split())
a = list(map(int, input().split()))
must0 = [i for i in range(18) if S >> i & 1 == 0]
must1 = [i for i in range(18) if T >> i & 1 == 1]
A = []
for val in a:
	check = True
	for j in must0:
		check = check & (val >> j & 1 == 0)
	for j in must1:
		check = check & (val >> j & 1 == 1)
	if check:
		A.append(val)
if not A:
	print(0)
	exit()
bit = []
for i in range(18):
	if i not in must0 and i not in must1:
		bit.append(i)
for i in range(len(A)):
	temp = 0
	for j in range(len(bit)):
		temp += (A[i] >> bit[j] & 1 == 1) * 2 ** j
	A[i] = temp
ans = 0
n = len(bit)
data = [0] * 2 ** n
pc = [popcount(i) for i in range(2 ** n)]
for i in range(2 ** n):
	for a in A:
		data[a & i] += 1
	for a in A:
		if data[a & i]:
			ans += cmb[data[a & i]][min(K, data[a & i])] * (-1) ** pc[i]
			data[a & i] = 0
print(ans)


import sys
readline = sys.stdin.readline

def popcount(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24
Jm = 18
MOD = 10 ** 18 + 3

def frac(limit):
	frac = [1] * limit
	for i in range(2, limit):
		frac[i] = i * frac[i - 1] % MOD
	fraci = [None] * limit
	fraci[-1] = pow(frac[-1], MOD - 2, MOD)
	for i in range(-2, -limit - 1, -1):
		fraci[i] = fraci[i + 1] * (limit + i + 1) % MOD
	return (frac, fraci)
(frac, fraci) = frac(100)

def comb(a, b):
	if not a >= b >= 0:
		return 0
	return frac[a] * fraci[b] * fraci[a - b] % MOD
PP = (1 << 32) - 1

def popcount64(x):
	return popcount(PP & x) + popcount(x >> 32)
(N, K, S, T) = map(int, readline().split())
lim = 60
calc = [0] * lim
for n in range(lim):
	for j in range(K):
		calc[n] += comb(n, j)
A = list(map(int, readline().split()))
ans = 1
table = [-1] * Jm
for i in range(Jm):
	si = S & 1 << i
	ti = T & 1 << i
	if si and ti:
		table[i] = 1
		continue
	if si and (not ti):
		ans = 0
		break
	if not si and (not ti):
		table[i] = 0
		continue
if not ans:
	print(ans)
else:
	ans = 0
	B = []
	for idx in range(N):
		for i in range(Jm):
			if table[i] == 1:
				if not A[idx] & 1 << i:
					break
			if table[i] == 0:
				if A[idx] & 1 << i:
					break
		else:
			res = 0
			cnt = -1
			ctr = 0
			for i in range(Jm):
				if table[i] == -1:
					ctr += 1
					cnt += 1
					if A[idx] & 1 << i:
						res |= 1 << cnt
			B.append(res)
	Jm = ctr
	L = len(B)
	JJ = (1 << L) - 1
	G = [[0] * L for _ in range(Jm)]
	for i in range(Jm):
		for idx in range(L):
			res = 0
			for jdx in range(idx + 1, L):
				if 1 << i & B[idx] == 1 << i & B[jdx]:
					res |= 1 << jdx
			G[i][idx] = res
	H = [[0] * L for _ in range(1 << Jm)]
	for i in range(L):
		H[0][i] = JJ
	ans = 0
	for k in range(1, K + 1):
		ans += comb(L, k)
	for U in range(1, 1 << Jm):
		R = []
		res = 0
		K = -U & U
		Uk = U ^ K
		for idx in range(L):
			H[U][idx] = H[Uk][idx] & G[K.bit_length() - 1][idx]
			cnt = H[U][idx]
			res += calc[popcount64(cnt)]
		ans += (-1 if popcount(U) & 1 else 1) * res
	print(ans)


def popcount_parity(x):
	for i in range(8):
		x ^= x >> (1 << i)
	return -1 if x & 1 else 1
(N, K, S, T) = map(int, input().split())
if S & T != S:
	print(0)
	exit()
C = [[1]]
CC = [0] * 51
for i in range(1, 51):
	C.append([1] * (i + 1))
	for j in range(1, i):
		C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
for i in range(51):
	CC[i] = sum(C[i][1:K + 1])
A = [int(a) for a in input().split()]
(aa, oo) = (-1, 0)
for i in range(N)[::-1]:
	a = A[i]
	if a & S != S or a | T != T:
		del A[i]
		continue
	aa &= a
	oo |= a
aa ^= oo
i = aa
ans = 0
while 1:
	D = {}
	for a in A:
		t = i & a
		if t not in D:
			D[t] = 1
		else:
			D[t] += 1
	ans += sum([CC[t] for t in D.values()]) * popcount_parity(i)
	if not i:
		break
	i = i - 1 & aa
print(ans)


import sys
readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def solve():
	(n, k, s, t) = nm()
	a = [x ^ s for x in nl() if x & s == s and x | t == t]
	n = len(a)
	t ^= s
	s = 0
	C = [[0] * (n + 1) for i in range(n + 1)]
	for i in range(n + 1):
		for j in range(i + 1):
			if j == 0:
				C[i][j] = 1
			elif i > 0:
				C[i][j] = C[i - 1][j] + C[i - 1][j - 1]
	D = [0] * (n + 1)
	for i in range(n + 1):
		for j in range(1, min(k, n) + 1):
			D[i] += C[i][j]
	for i in range(n, 0, -1):
		D[i] -= D[i - 1]
	l = list()
	for i in range(20, -1, -1):
		if t & 1 << i:
			l.append(i)
	p = len(l)
	na = list()
	for x in a:
		v = 0
		for i in l:
			v = v << 1 | x >> i & 1
		na.append(v)
	pc = [popcount(i) for i in range(1 << p)]
	l = [0] * (1 << p)
	ans = 0
	for bit in range(1 << p):
		cur = 0
		for x in na:
			l[bit & x] += 1
			cur += D[l[bit & x]]
		for x in na:
			l[bit & x] -= 1
		if pc[bit] & 1:
			ans -= cur
		else:
			ans += cur
	print(ans)
	return
solve()


def cmb(n, r, mod):
	if r < 0 or r > n:
		return 0
	r = min(r, n - r)
	return g1[n] * g2[r] * g2[n - r] % mod
mod = 10 ** 18 + 7
N = 50
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)
(N, K, T, S) = map(int, input().split())
a = list(map(int, input().split()))
must0 = [i for i in range(18) if S >> i & 1 == 0]
must1 = [i for i in range(18) if T >> i & 1 == 1]
A = []
for val in a:
	check = True
	for j in must0:
		check = check & (val >> j & 1 == 0)
	for j in must1:
		check = check & (val >> j & 1 == 1)
	if check:
		A.append(val)
if not A:
	print(0)
	exit()
bit = []
for i in range(18):
	if i not in must0 and i not in must1:
		bit.append(i)
for i in range(len(A)):
	temp = 0
	for j in range(len(bit)):
		temp += (A[i] >> bit[j] & 1 == 1) * 2 ** j
	A[i] = temp
ans = 0
n = len(bit)
for i in range(2 ** n):
	dic = {}
	for a in A:
		val = a & i
		if val not in dic:
			dic[val] = 0
		dic[val] += 1
	temp = 0
	for val in dic:
		for j in range(1, min(K, dic[val]) + 1):
			temp += cmb(dic[val], j, mod)
	popcount = 0
	for j in range(n):
		popcount += i >> j & 1
	ans += temp * (-1) ** popcount
print(ans % mod)