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

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**9+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)

Submission status: Wrong Answer

Solution code:
n,k,s,t=map(int,input().split())
b=list(map(int,input().split()))
a=[]
for i in range(n):
    for j in range(18):
        if (s>>j)&1 and not((b[i]>>j)&1):
            break
    else:
        for j in range(18):
            if not((t>>j)&1) and (b[i]>>j)&1:
                break
        else:
            a.append(b[i])
n=len(a)
k=min(n,k)
#dp[i] i個選んだ時に(S,T)となるのが何通り存在するか(Sが論理積でTが論理和)
#1-indexed
dp=[{(s,t):0} for i in range(k)]
for i in range(n):
    dp_sub=[dict() for i in range(k)]
    dp_sub[0][(a[i],a[i])]=1
    for j in range(k-1):
        for l in dp[j]:
            m=(l[0]&a[i],l[1]|a[i])
            if l in dp_sub[j+1]:
                dp_sub[j+1][m]+=dp[j][l]
            else:
                dp_sub[j+1][m]=dp[j][l]
    for j in range(k):
        for l in dp_sub[j]:
            if l in dp[j]:
                dp[j][l]+=dp_sub[j][l]
            else:
                dp[j][l]=dp_sub[j][l]
print(sum([dp[i][(s,t)] for i in range(k)]))

Submission status: Wrong Answer

Solution code:
def popcount_parity(x):
    for i in range(8):
        x ^= x >> (1 << i)
    return -1 if x & 1 else 1

C = [[1]]
CC = [0] * 51
K = 4
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])

N, K, S, T = map(int, input().split())
if S & T != S:
    print(0)
    exit()

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

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

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

# 初期状態はAND = 1111... (18桁)と OR = 0000...(18桁)
# ここに対してAND OR を取っていくDP
# 最後にdp[(S,T)]を数える
# ただしS,Tともに1の桁に0が入っている数
# S,Tともに0の桁に1が入っている数
# は除外する
# また、Sでは1だけどTでは0の桁があったらその時点で答えは0

binS = bin(S)[2:].zfill(18)
binT = bin(T)[2:].zfill(18)

bothone = set()
bothzero = set()

for i in range(len(binS)):
  if binS[i] == "1" and binT[i] == "1":
    bothone.add(i)
  elif binS[i] == "0" and binT[i] == "0":
    bothzero.add(i)
  elif binS[i] == "1" and binT[i] == "0":
    print(0)
    exit(0)

#print(bothone)
#print(bothzero)

from collections import defaultdict
dp = defaultdict(int)
dp[(2 ** 18 - 1,0)] = 1
for x in A:
  newdp = defaultdict(int)
  #print("x",x)
  for da,do in dp:
    newdp[(da,do)] += dp[(da,do)]
    newand = da & x
    newor = do | x
    #print("da",da,"do",do,"newand",newand,"newor",newor)
    # newandを18桁の2進数にしたとき、bothoneの桁に0があってはいけない
    # 同時に、bothzeroの桁に1があってもいけない
    bin_newand = bin(newand)[2:].zfill(18)
    ok = True
    for i in range(len(bin_newand)):
      if i in bothone and bin_newand[i] == "0":
        ok = False
        break
    if not ok:
      continue
    bin_newor = bin(newor)[2:].zfill(18)
    for i in range(len(bin_newor)):
      if i in bothzero and bin_newor[i] == "1":
        ok = False
        break
    if ok:
      newdp[(newand,newor)] += 1
  dp = newdp
#  print(dp)

#print(dp)
print(dp[(S,T)])

Submission status: Wrong Answer

Solution code:
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) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 0x0000007f


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

Submission status: Wrong Answer

Solution code:
1

Submission status: Wrong Answer

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('(i8[:],i8[:,:],i8)')
def f(counts, C, K):
    ret = 0
    for x in counts:
        for k in range(1, K + 1):
            ret += C[x, k]
    return ret

@njit('(i4,)', cache=True)
def popcount(n):
    ret = 0
    while n:
        ret += n & 1
        n >>= 1
    return ret

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

se = 0
for i in range(18):
    s, t = (S >> i) & 1, (T >> i) & 1
    if (s, t) == (0, 0):
        A = A[((A >> i) & 1) == 0]
    elif (s, t) == (1, 1):
        A = A[((A >> i) & 1) == 1]
    elif (s, t) == (1, 0):
        print(0)
        exit()
    else:
        se |= (1 << i)

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]

n = se
ans = 0
while True:
    k = popcount(se ^ n)
    nums, counts = np.unique(A & n, return_counts=True)
    x = f(counts, C, K)
    if k & 1:
        ans -= x
    else:
        ans += x
    if n == 0:
        break
    n = (n - 1) & se
print(ans)

Submission status: Wrong Answer

Solution code:
def main(N, M, K, S, T, A):
  L = []
  for i in range(M):
    k = 1 << i
    s = S & k
    t = T & k
    if not((not s) and t): continue
    L.append(0)
    L.append(0)
    for j in range(N):
      if A[j] & k:
        L[-1] |= (1 << j)
      else:
        L[-2] |= (1 << j)

  R = [{} for i in range(K + 1)]
  R[0][0] = 1
  for i in range(N):
    t = 0
    for j in range(len(L)):
      if L[j] & (1 << i):
        t |= (1 << j)
    for j in range(K-1, -1, -1):
      for k in R[j].keys():
        d = k | t
        if d in R[j + 1]:
          R[j + 1][d] += 1
        else:
          R[j + 1][d] = 1
          
  ans = 0
  n = (1 << len(L)) - 1
  for i in range(K + 1):
    if n in R[i]:
      ans += R[i][n]

  print(ans)



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

M = max(len(bin(S)), len(bin(T))) - 2
for i in range(N):
  M = max(M, len(bin(A[i])) - 1)

D = [0] * N
L = []

for i in range(M):
  k = 1 << i
  s = S & k
  t = T & k
  if s & (not t):
    print(0)
    exit()
  if (not s) & (not t):
    for i in range(N):
      if A[i] & k:
        D[i] = 1
  elif s & t:
    for i in range(N):
      if not (A[i] & k):
        D[i] = 1

B = []
cnt = 0
for i in range(N):
  if D[i] == 1:
    cnt += 1
  else:
    B.append(A[i])

N -= cnt

main(N, M, K, S, T, B)

Submission status: Wrong Answer

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

if S & T != S:
    print(0)
    exit()

cond = []
for n in range(N):
    if S & A[n] == S and ~T & A[n] == 0:
        cond.append(A[n])

Submission status: Wrong Answer

Solution code:
import itertools
n, k, s, t = map(int, input().split())
a = list(map(int, input().split()))
table = dict()
for v in a:
    table[v] = [0] * 18
    for i in range(18):
        if v>>i & 1:
            table[v][17-i] = 1
ans = 0
for pattern in itertools.product([0, 1], repeat=n):
    if 1 not in pattern:
        continue
    ans_s = 0
    ans_t = 0
    s_ = [False] * 18
    t_ = [True] * 18
    for i, v in enumerate(pattern):
        if v == 1:
            for index, l in enumerate(table[a[i]]):
                if l == 1:
                    s_[index] = True
                else:
                    t_[index] = False
    for k, v in enumerate(s_):
        if v == True:
            ans_s += 2**(18-k-1)
    for n, v in enumerate(t_):
        if v == True:
            ans_t += 2**(18-n-1)
    if ans_s == s and ans_t == t:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,k,s,t=[int(j)for j in input().split()]
a=[int(j)for j in input().split()]
if s==t:
    ans=0
    for i in a:
        if i==s:
            ans+=1
    print(ans)
    exit()
i=0
l=[]
for i in range(20):
    p=s>>i&1
    q=t>>i&1
    if p==1 and q==0:
        print(0)
        exit()
    if p==1 and q==1:
        l.append(1)
    elif p==0 and q==0:
        l.append(0)
    else:
        l.append(2)

ll=[]
for i in a:
    j=0
    b=True
    for j in range(19):
        p=i>>j&1
        if l[j]==1 and p!=1:
            b=False
            break
        elif l[j]==0 and p!=0:
            b=False
            break
    if b:
        ll.append(i)
lk=[]
lc=[]
for j in range(20):
    if l[j]==2:
        lk.append([])
        lc.append(j)

for i in ll:
    for idx,j in enumerate(lc):
        p=i>>j&1
        lk[idx].append(p)
n=len(lk[0])
m=len(lk)
lll=[]
import copy
import itertools
for i,j in itertools.combinations(range(n),2):
    if lk[0][i]!=lk[0][j]:
        lll.append((i,j))
for idx in range(1,m):
    tmp=[]
    for i,j in lll:
        if lk[idx][i]!=lk[idx][j]:
            tmp.append((i,j))
    lll=copy.deepcopy(tmp)
ans=0
for i in range(1,n+1):
    for x in itertools.combinations(range(n),i):
        b=True
        for k in range(m):
            o,z=0,0
            for j in x:
                if lk[k][j]==0:
                    o+=1
                else:
                    z+=1
            if o*z==0:
                b=False
                break
        if b:
            ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

nkst = list(map(int,input().split()))
i = list(map(int,input().split()))

n = nkst[0]
k = nkst[1]
s = nkst[2] # 論理積=&
t = nkst[3] # 論理和=|

cnt = 0

for val in range(k):
    if val+1== 1:
        continue;

    lst = list(itertools.combinations(i,val+1))
    
    for item in lst:
        if len(item)==2:
            if item[0]&item[1]==s and item[0]|item[1]==t:
                cnt += 1
        if len(item)==3:
            if item[0]&item[1]&item[2]==s and item[0]|item[1]|item[2]==t:
                cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
n,k,s,t=list(map(int,input().split()))
arr=list(map(int,input().split()))
count=0
for i in range(1,k):
	for arr1 in combinations(arr,i):
	    bit_or=arr1[0]
	    bit_and=arr1[0]
	    if len(arr1)>1:
	        for j in range(0,len(arr1)):
	            bit_or=bit_or|arr1[j]
	            bit_and=bit_and|arr[j]
	    if bit_or==t and bit_and==s:
	        count+=1
print(count)

Submission status: Wrong Answer

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

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62


def x():
    dp[0] = 0
    for s, c in zip(S, C):
        for i in range(1 << N):
            j = i | s
            x = dp[i] + c
            if dp[j] > x:
                dp[j] = x

    answer = dp[-1]


def solve(N: int, K: int, S: int, T: int, A: "List[int]"):
    ValidA = []
    for a in A:
        # logical sum  : must a | T =
        # print(a, a | T, a & S)
        if (a | T) != T:
            continue
        # logical multiply:
        if (a & S) != S:
            continue
        ValidA.append(a)
    # 論理和 だんだん大きくなる
    # 論理積 小さくなるはず
    dp = collections.defaultdict(int)
    x = (1 << 19) - 1
    dp[(0, x)] = 1
    for a in ValidA:
        ndp = collections.defaultdict(int)
        for (l, r) in sorted(dp.keys(), key=lambda x: (-x[0], x[1])):
            ndp[(l | a), (r & a)] += dp[(l, r)]
            # if (l | a) == 15 and (r & a) == 0:
            #     print(l, r, "merge", a,dp[(l, r)])
        for k, v in ndp.items():
            dp[k] += v
        # print(a, dp)

    print(dp[(T, S)])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, S, T, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,k,s,t = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    jk = s^t
    oks = []
    for i in a:
        if i&s == s and i|t == t:
            oks.append(i&jk)
    if jk == 0:
        print(pow(2,len(oks)))
        exit()
    dp = defaultdict(int)
    dp[(jk,0)] = 1
    for i in oks:
        dpj = set(dp.items())
        for dk,dv in dpj:
            dki,dkj = dk
            dp[(dki&i,dkj|i)] += dv
        print(dp)

    print(dp[(0,jk)])





    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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 = 5

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

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

bin_str = format(S, '08b')
c = 0
for l in range(2**N):
  binstr_l = format(l, '050b')
  lnum = 0
  for i in range(50):
    if binstr_l[i] == 1:
      lnum += 1
  if lnum > K:
    break
  a = 2**18-1
  o = 0
  for i in range(N):
    if(binstr_l[50-1 - i] == '1'):
      a = a & A[i]
      o = o | A[i]
  if a == S and o == T:
    c += 1
print(c)

Submission status: Wrong Answer

Solution code:
#n,k,s,t = (int(x) for x in input().split())
n,k,s,t = map(int, input().split())
#print(n,k,s,t)
#ss = (int(x) for x in input().split())
ss = list(map(int, input().split()))

def ok(l, s, t):
  a = 0
  for i in l:
    a = a & i
  if a == s:
    a = 0
    for i in l:
      a = a | i
    if a == t:
      return True
  return False


print(s)

Submission status: Wrong Answer

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
    na = deque()
    for i in range(n):
        print(s&1,a[i]&1)
        A = a[i]
        if A<=t:
            if s&1:
                if s&1==A&1:
                    na.append(A)
            else:
                na.append(A)
    a = na
    n = len(a)
    for bit in range(2**n):
        tmp = bin(bit).count('1')
        if tmp<=k:
            ss = tt = -1
            stp = 0
            for i in range(n):
                if (bit>>i)&1:
                    if ss==-1 or tt==-1:
                        ss = a[i]
                        tt = a[i]
                        stp += 1
                    else:
                        ss &= a[i]
                        tt |= a[i]
                        stp+=1
                if stp==tmp:
                    break
            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 = deque(LI())
    print(solve(n,k,s,t,a))
    return

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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 a == and_ and b == or_:
        return 1 << 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: Wrong Answer

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

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)


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

Solution code:
N, K, S, T = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
for i in range(1, 2**N):
    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:
n,k,s,t=map(int,input().split())
b=list(map(int,input().split()))
a=[]
for i in range(n):
    for j in range(18):
        if (s>>j)&1 and not((b[i]>>j)&1):
            break
    else:
        for j in range(18):
            if not((t>>j)&1) and (b[i]>>j)&1:
                break
        else:
            a.append(b[i])
n=len(a)
k=min(n,k)
#dp[i] i個選んだ時に(S,T)となるのが何通り存在するか(Sが論理積でTが論理和)
#1-indexed
dp=[{(s,t):0} for i in range(k)]
for i in range(n):
    dp_sub=[dict() for i in range(k)]
    dp_sub[0][(a[i],a[i])]=1
    for j in range(k-1):
        for l in dp[j]:
            m=(l[0]&a[i],l[1]|a[i])
            if m in dp_sub[j+1]:
                dp_sub[j+1][m]+=dp[j][l]
            else:
                dp_sub[j+1][m]=dp[j][l]
    for j in range(k):
        for l in dp_sub[j]:
            if l in dp[j]:
                dp[j][l]+=dp_sub[j][l]
            else:
                dp[j][l]=dp_sub[j][l]
print(sum([dp[i][(s,t)] for i in range(k)]))

Submission status: Time Limit Exceeded

Solution code:
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) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 0x0000007f


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

Submission status: Time Limit Exceeded

Solution code:
import itertools

nkst = list(map(int,input().split()))
i = list(map(int,input().split()))

n = nkst[0]
k = nkst[1]
s = nkst[2] # 論理積=&
t = nkst[3] # 論理和=|

cnt = 0

for val in range(k):
    if val+1== 1:
        continue;

    lst = list(itertools.combinations(i,val+1))
    
    for item in lst:
       # print(item)
        for idx in range(len(item)):
            if idx==0:
                and_result = item[idx]
                or_result = item[idx]
            else:
                and_result = item[idx]&and_result
                or_result = item[idx]|or_result
                
                if or_result>t:
                    break

        if and_result==s and or_result==t:
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools

nkst = list(map(int,input().split()))
i = list(map(int,input().split()))

n = nkst[0]
k = nkst[1]
s = nkst[2] # 論理積=&
t = nkst[3] # 論理和=|

cnt = 0

for val in range(k):
    if val+1== 1:
        continue;

    lst = list(itertools.combinations(i,val+1))
    
    for item in lst:
       # print(item)
        for idx in range(len(item)):
            if idx==0:
                and_result = item[idx]
                or_result = item[idx]
            else:
                and_result = item[idx]&and_result
                or_result = item[idx]|or_result

        if and_result==s and or_result==t:
            cnt += 1

print(cnt)

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n,k,s,t=map(int,input().split())
a=list(map(int,input().split()))
ans=0
for c in range(1,k+1):
  for i in combinations(range(n),c):
    ss=a[i[0]]
    tt=a[i[0]]
    for j in i:
      ss&=a[j]
      tt|=a[j]
    if ss==s and tt==t:
      ans+=1
print(ans)
# カス　アホ