Problem:


Score : 800 points

Problem Statement

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.

Sample Input 1

3 3 0 3
1 2 3

Sample Output 1

2

The conditions are satisfied when we choose \{1,2\} or \{1,2,3\}.

Sample Input 2

5 3 1 7
3 4 9 1 5

Sample Output 2

2

Sample Input 3

5 4 0 15
3 4 9 1 5

Sample Output 3

3



Sample input:
3 3 0 3
1 2 3


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations


def _and(l):
    ans = l[0]
    for i in range(1,len(l)):
        ans &= l[i]
    return ans


def _or(l, t):
    ans = 0
    for i in l:
        ans |= i
        if ans > t:
            return False
    if ans == t:
        return True
    else:
        return False


def main():
    n, k, s, t = map(int,input().split(' '))
    a = list(map(int,input().split(' ')))
    count = 0

    for i in range(2,k+1):
        for j in combinations(a, i):
            if s == _and(j) and _or(j, t):
                count +=1
    print(count)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

import random
import itertools
import operator
from functools import reduce
input1 = list(map(int, input().split()))
A = list(map(int, input().split()))
N = input1[0]
K = input1[1]
S = input1[2]
T = input1[3]

count = 0
for k in range(1, K + 1):
    list_k = list(itertools.combinations(A, k))
    # print(list_k)
    for i in list_k:
        tmp_S = reduce(operator.__and__, i)
        tmp_T = reduce(operator.__or__, i)
        if(tmp_S == S and tmp_T == T):
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations


def _and(l):
    ans = l[0]
    for i in range(1,len(l)):
        ans &= l[i]
    return ans


def _or(l):
    ans = 0
    for i in l:
        ans |= i
    return ans


def main():
    n, k, s, t = map(int,input().split(' '))
    a = list(map(int,input().split(' ')))
    count = 0

    for i in range(2,k+1):
        for j in combinations(a, i):
            if s == _and(j) and t == _or(j):
                count +=1
    print(count)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def popcount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 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


popcntsum = ((1<<64) - 1)
Fa = [0] + [popcntsum//((1<<(1<<(i-1)))+1) for i in range(1,7)]
Fb = [0] + [Fa[i]<<(1<<(i-1)) for i in range(1,7)]
fila1 = Fa[1]
filb1 = Fb[1]
fila2 = Fa[2]
filb2 = Fb[2]
fila3 = Fa[3]
filb3 = Fb[3]
fila4 = Fa[4]
filb4 = Fb[4]
fila5 = Fa[5]
filb5 = Fb[5]
fila6 = Fa[6]
filb6 = Fb[6]
def popcount64(x):
    x = (x&fila1) + ((x&filb1)>>1)
    x = (x&fila2) + ((x&filb2)>>2)
    x = (x&fila3) + ((x&filb3)>>4)
    x = (x&fila4) + ((x&filb4)>>8)
    x = (x&fila5) + ((x&filb5)>>16)
    x = (x&fila6) + ((x&filb6)>>32)
    return x



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
    
    
    ans = 0
    for k in range(1, K+1):
        ans += comb(L, k)
    #print(B, ans)
    for U in range(1, 1<<Jm):
        R = []
        res = 0
        for i in range(Jm):
            if (1<<i) & U:
                R.append(i)
        #print(R)
        for idx in range(L):
            cnt = JJ
            for r in R:
                cnt &= G[r][idx]
            #print('c', cnt)
            res += calc[popcount64(cnt)]
        #print(U, (-1 if len(R)&1 else 1)*res)
        ans += (-1 if len(R)&1 else 1)*res
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,K,S,T = input().split()
N = int(N)
K = int(K)
S = int(S)
T = int(T)
A = input().split()
counted = 0

for a in range(N):
  A[a] = int(A[a])

  
if S == T:
  if S in A:
    counted = A.count(S)

for num in range(1,K+1):
  if num == 1:
    baby = 0
  else:
    for kumiawase in itertools.combinations(A, num):
      bitted = 0b111111111111111111
      bitting = 0b000000000000000000
      for nannko in range(len(kumiawase)):
        bitted = kumiawase[nannko] & bitted
        bitting = kumiawase[nannko] | bitting

      if bitted == S and bitting == T:
        counted += 1

        
print(counted)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

n, k, and_, or_ = map(int, input().split())
lst = sorted([int(n) for n in input().split()])
lst = [n for n in lst if n & and_ == and_ and n | or_ == or_]
n = len(lst)
# print(lst)


@lru_cache(None)
def fac(n):
    return 1 if n <= 1 else n * fac(n - 1)


def choose(a, b):
    return fac(a) // fac(b) // fac(a - b)


@lru_cache(None)
def f(i, k, a, b):
    if a == and_ and b == or_:
        return sum(choose(n - i, x) for x in range(1 + min(k, n - i)))
    elif i == n:
        return 0
    else:
        return (f(i + 1, k - 1, a & lst[i], b | lst[i]) if k > 0 else 0) + f(i + 1, k, a, b)


print(sum(f(i + 1, k - 1, x, x) for i, x in enumerate(lst)))

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools


def main():
    n, k, s, t = list(map(int, input().split()))
    a = list(map(int, input().split()))

    # mask = 1 << (math.ceil(math.sqrt(s)) + 1) - 1
    a.sort()
    for i, e in enumerate(a):
        if s <= e:
            break
    else:
        return 0

    max_value = 2 ** math.ceil(math.sqrt(t))
    for j, e in enumerate(a):
        if max_value < e:
            break

    result = 0
    cand = []
    for m in range(i, j + 1):
        if (s & a[m]) == s and (t | a[m]) == t:
            cand.append(a[m])
            if a[m] == s and a[m] == t:
                result += 1

    for i in range(2, k + 1):
        for c in itertools.combinations(cand, i):
            sr = c[0]
            tr = 0

            for e in c:
                sr &= e
                tr |= e
            if sr == s and tr == t:
                result += 1

    return result

if __name__ == '__main__':
    result = main()
    print(result)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, k, s, t = map(int, input().split())
a = [int(i) for i in input().split()]

answers = 0

for i in range(2, k+1):
    c = list(itertools.combinations(a, i))

    for x in c:
        xlist = list(x)
        vAnd = xlist[0]
        vOr = xlist[0]

        for y in range(1, len(xlist)):
            vAnd &= xlist[y]
            vOr |= xlist[y]

        if vAnd == s and vOr == t:
            answers += 1

print(answers)

Submission status: Time Limit Exceeded

Solution code:


N, K, S, T = map(int, input().split())
A = list(map(int, input().split()))

import math
p = math.floor(math.log2(T))+1
#print(p)

A_ = []
for a in A:
    #print(a & S)
    if (S <= a) and (a < 2**p) and (a & S == S):
        A_.append(a)
        
#print(A_)

import itertools

count = 0
for k in range(1, K+1):
    com = list(itertools.combinations(A_, k))
    for c in com:
        AND = c[0]
        OR = c[0]
        for i in range(1, len(c)):
            AND &= c[i]
            OR |= c[i]
        if (AND == S) and (OR == T):
            count += 1
        

print(count)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

n, k, and_, or_ = map(int, input().split())
lst = sorted([int(n) for n in input().split()])
lst = [n for n in lst if n & and_ == and_ and n | or_ == or_]
n = len(lst)
# print(lst)


@lru_cache(None)
def f(i, k, a, b):
    if i == n:
        return a == and_ and b == or_
    else:
        return (f(i + 1, k - 1, a & lst[i], b | lst[i]) if k > 0 else 0) + f(i + 1, k, a, b)


print(sum(f(i + 1, k - 1, x, x) for i, x in enumerate(lst)))

Submission status: Time Limit Exceeded

Solution code:
def calc_all(arr):
    res = None
    for i in arr:
        if res is None:
            res = i
        else:
            res = res & i
        # print(res)
    return res


def calc_any(arr):
    res = None
    for i in arr:
        if res is None:
            res = i
        else:
            res = res | i
    return res


import itertools
N, K, S, T = map(int, input().split())
A = list(map(int, input().split()))

counta = 0
for j in range(1, K+1):
    for i in itertools.combinations(A, j):
        if calc_all(i) == S and calc_any(i) == T:
            # print(i)
            counta = counta + 1
print(counta)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def helper(l):
  a = 0
  b = 0xffff
  for v in l:
    a = a | v
    b = b & v
  return a, b

N, K, S, T = map(int, input().split())

#print(N)
#print(K)
#print(S)
#print(T)

A = input().split()
L = [int(b.strip()) for b in A]
#print(L)

count = 0

for i in range(1, K+1):
  c = itertools.combinations(L, i)
  for v in c:
    #print(v)
    # 論理和と論理積が一致していたらカウントする
    a, b = helper(v)
    #print(a)
    #print(b)
    if a == T and b == S:
      count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools


def main():
    n, k, s, t = list(map(int, input().split()))
    a = list(map(int, input().split()))

    # mask = 1 << (math.ceil(math.sqrt(s)) + 1) - 1
    a.sort()
    for i, e in enumerate(a):
        if s <= e:
            a = a[i:]
            break
    else:
        return 0

    max_value = 2 ** math.ceil(math.sqrt(t))
    for i, e in enumerate(a):
        if max_value < e:
            a = a[:i]
            break

    result = 0
    for i in range(1, k + 1):
        for c in itertools.combinations(a, i):
            sr = c[0]
            tr = 0
            for e in c:
                if (s & e) == s:
                    sr &= e
                else:
                    break

                tr |= e
                if tr > t:
                    break
            if sr == s and tr == t:
                result += 1
    return result


if __name__ == '__main__':
    result = main()
    print(result)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, k, s, t = map(int, input().split())
a = list(map(int, input().split()))
com = []

for i in range(1, k + 1):
    com += itertools.combinations(a, i)
  
count = 0

for i in range(1, len(com)):
    b = com[i][0]
    c = com[i][0]
    if len(com[i]) == 1:
        pass
    else:
        for j in range(1, len(com[i])):
            b =  b & com[i][j]
            c = c | com[i][j]
    if b == s and c == t:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, K, S, T = map(int, input().split())
B = list(map(int, input().split()))
ans = 0
A = []
for i in range(N):
    if B[i] >= S:
        A.append(B[i])
N = len(A)
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

for i in range(1, 2**N):
    if popcount(i) <= K:
        start = 0
        for j in range(N):
            if((i >> j) & 1):
                if start == 1:
                    s = s&A[j]
                    t = t | A[j]
                else:
                    s = A[j]
                    t = A[j]
                    start = 1
        if (s == S) and (t == T):
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!python3.8
# -*- coding: utf-8 -*-
# tokiomarine2020/tokiomarine2020_e
import sys
from itertools import combinations
from operator import and_, or_
from functools import reduce

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, K, S, T = i2nn()
    A = list(filter(lambda n:n & S == S and n | T == T, map(int, i2s().split(' '))))
    cnt = 0
    for r in range(1, K+1):
        for c in combinations(A, r):
            if reduce(and_, c) == S and reduce(or_, c) == T:
                cnt += 1
    print(cnt)
    return

main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

n, k, and_, or_ = map(int, input().split())
lst = sorted([int(n) for n in input().split()])


@lru_cache(None)
def f(i, k, a, b):
    if i == n:
        return k >= 0 and a == and_ and b == or_
    elif (a is not None and a & and_ != and_) or (b is not None and b > or_ != or_) or k < 0:
        return False
    else:
        return f(i + 1, k - 1, lst[i] if a is None else a & lst[i], lst[i] if b is None else b | lst[i]) + f(i + 1, k, a, b)


print(f(0, k, None, None))

Submission status: Time Limit Exceeded

Solution code:
import itertools


def main():
    n, k, s, t = list(map(int, input().split()))
    a = list(map(int, input().split()))

    # mask = 1 << (math.ceil(math.sqrt(s)) + 1) - 1
    result = 0
    for i in range(1, k + 1):
        for c in itertools.combinations(a, i):
            sr = c[0]
            tr = 0
            for e in c:
                if (s & e) == s:
                    sr &= e
                else:
                    break

                tr |= e
                if tr > t:
                    break
            if sr == s and tr == t:
                result += 1
    return result


if __name__ == '__main__':
    result = main()
    print(result)

Submission status: Time Limit Exceeded

Solution code:

N, K, S, T = map(int, input().split())
A = list(map(int, input().split()))


import itertools

count = 0
for k in range(1, K+1):
    com = list(itertools.combinations(A, k))
    for c in com:
        AND = c[0]
        OR = c[0]
        for i in range(1, len(c)):
            AND &= c[i]
            OR |= c[i]
        if (AND == S) and (OR == T):
            count += 1
        

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys 
from collections import deque
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def solve(n,k,s,t,a):
    count = 0
    for bit in range(2**n):
        if bin(bit).count('1')<=k:
            ss = -1
            tt = -1
            for i in range(n):
                if (bit>>i)&1:
                    if ss==-1 or tt==-1:
                        ss = tt = a[i]
                    else:
                        ss &= a[i]
                        tt |= a[i]
            if ss==s and tt==t:
                count += 1
    return count

def main():
    tmp = deque(LI())
    n,k,s,t = tmp.popleft(),tmp.popleft(),tmp.popleft(),tmp.popleft()
    a = LI()
    print(solve(n,k,s,t,a))
    return

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

n, k, and_, or_ = map(int, input().split())
lst = sorted([int(n) for n in input().split()])


@lru_cache(None)
def f(i, k, a, b):
    if i == n:
        return k >= 0 and a == and_ and b == or_
    elif (a is not None and a < and_) or (b is not None and b > or_) or k < 0:
        return False
    else:
        return f(i + 1, k - 1, lst[i] if a is None else a & lst[i], lst[i] if b is None else b | lst[i]) + f(i + 1, k, a, b)


print(f(0, k, None, None))

Submission status: Accepted

Solution code:
def popcount(x):
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 0x0000007f

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)

Submission status: Accepted

Solution code:
def popcount(x):
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 0x0000007f

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 and j!=50:
            cmb[i+1][j+1]+=cmb[i][j]
        if i!=50:
            cmb[i+1][j]+=cmb[i][j]

for i in range(1,51):
    for j in range(2,51):
        cmb[i][j]+=cmb[i][j-1]

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)
for i in range(2**n):
    t=set([])
    for a in A:
        data[a&i]+=1
        t.add(a&i)
    temp=0
    for val in t:
        temp+=cmb[data[val]][min(K,data[val])]
    ans+=temp*(-1)**popcount(i)
    for val in t:
        data[val]=0

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def popcount_parity(x):
    x ^= x >> 1
    x ^= x >> 2
    x ^= x >> 4
    x ^= x >> 8
    x ^= x >> 16
    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
    c = 0
    for t in D.values():
        c += CC[t]
    ans += c * popcount_parity(i)
    if not i: break
    i = (i - 1) & aa
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main(A, B, C):
    counts = np.zeros(1 << 18, np.int32)
    popcount = np.zeros(1 << B, np.int32)
    for i in range(B):
        popcount[1 << i:1 << i + 1] = popcount[:1 << i] + 1

    answer = 0
    for i in range(1 << B):
        k = popcount[i]
        t = 0
        for x in A & i:
            n = counts[x]
            counts[x] += 1
            t -= C[n]
            t += C[n + 1]
        for x in A & i:
            counts[x] = 0
        if k & 1:
            t = -t
        answer += t
    return answer
  
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(i4[::1],i4,i8[::1])')(main)
    cc.compile()
    exit()
from my_module import main

N, K, S, T = map(int, readline().split())
A = np.array(readline().split(), np.int32)

def convert_problem(S, T, A):
    ng = np.zeros(len(A), np.bool)
    B = np.zeros_like(A)
    n = 0
    for i in range(18):
        s, t = (S >> i) & 1, (T >> i) & 1
        if (s, t) == (0, 0):
            ng |= ((A >> i) & 1) == 1
        elif (s, t) == (1, 1):
            ng |= ((A >> i) & 1) == 0
        elif (s, t) == (1, 0):
            print(0)
            exit()
        else:
            B += ((A >> i) & 1) << n
            n += 1
    return B[~ng], n

A, B = convert_problem(S, T, A)

C = np.zeros((100, 100), np.int64)
C[0, 0] = 1
for n in range(1, 100):
    C[n, :-1] += C[n - 1, :-1]
    C[n, 1:] += C[n - 1, :-1]
C = C[:, 1:K + 1].sum(axis=1)

print(main(A, B, C))

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i4[::1],i4,i8[::1])', cache=True)
def main(A, B, C):
    counts = np.zeros(1 << 18, np.int32)
    popcount = np.zeros(1 << B, np.int32)
    for i in range(B):
        popcount[1 << i:1 << i + 1] = popcount[:1 << i] + 1

    answer = 0
    for i in range(1 << B):
        k = popcount[i]
        t = 0
        for x in A & i:
            n = counts[x]
            counts[x] += 1
            t -= C[n]
            t += C[n + 1]
        for x in A & i:
            counts[x] = 0
        if k & 1:
            t = -t
        answer += t
    return answer
  
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(i4[::1],i4,i8[::1])')(main)
    cc.compile()
    exit()
from my_module import main

N, K, S, T = map(int, readline().split())
A = np.array(readline().split(), np.int32)

def convert_problem(S, T, A):
    ng = np.zeros(len(A), np.bool)
    B = np.zeros_like(A)
    n = 0
    for i in range(18):
        s, t = (S >> i) & 1, (T >> i) & 1
        if (s, t) == (0, 0):
            ng |= ((A >> i) & 1) == 1
        elif (s, t) == (1, 1):
            ng |= ((A >> i) & 1) == 0
        elif (s, t) == (1, 0):
            print(0)
            exit()
        else:
            B += ((A >> i) & 1) << n
            n += 1
    return B[~ng], n

A, B = convert_problem(S, T, A)

C = np.zeros((100, 100), np.int64)
C[0, 0] = 1
for n in range(1, 100):
    C[n, :-1] += C[n - 1, :-1]
    C[n, 1:] += C[n - 1, :-1]
C = C[:, 1:K + 1].sum(axis=1)

print(main(A, B, C))

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i4[::1],i4,i8[::1])', cache=True)
def main(A, B, C):
    counts = np.zeros(1 << 18, np.int32)
    popcount = np.zeros(1 << B, np.int32)
    for i in range(B):
        popcount[1 << i:1 << i + 1] = popcount[:1 << i] + 1

    answer = 0
    for i in range(1 << B):
        k = popcount[i]
        t = 0
        for x in A & i:
            n = counts[x]
            counts[x] += 1
            t -= C[n]
            t += C[n + 1]
        for x in A & i:
            counts[x] = 0
        if k & 1:
            t = -t
        answer += t
    return answer

N, K, S, T = map(int, readline().split())
A = np.array(readline().split(), np.int32)

def convert_problem(S, T, A):
    ng = np.zeros(len(A), np.bool)
    B = np.zeros_like(A)
    n = 0
    for i in range(18):
        s, t = (S >> i) & 1, (T >> i) & 1
        if (s, t) == (0, 0):
            ng |= ((A >> i) & 1) == 1
        elif (s, t) == (1, 1):
            ng |= ((A >> i) & 1) == 0
        elif (s, t) == (1, 0):
            print(0)
            exit()
        else:
            B += ((A >> i) & 1) << n
            n += 1
    return B[~ng], n

A, B = convert_problem(S, T, A)

C = np.zeros((100, 100), np.int64)
C[0, 0] = 1
for n in range(1, 100):
    C[n, :-1] += C[n - 1, :-1]
    C[n, 1:] += C[n - 1, :-1]
C = C[:, 1:K + 1].sum(axis=1)

print(main(A, B, C))

Submission status: Accepted

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

def popcount(i):
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 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)
    #print(B, ans)
    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)]
        #print(U, (-1 if len(R)&1 else 1)*res)
        ans += (-1 if popcount(U)&1 else 1)*res
    print(ans)