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: Runtime Error

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 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, k+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)

    return
    pc = [0]*(1 << p)
    for bit in range(1 << p):
        for i in range(p):
            if not bit & (1 << i):
                pc[bit | (1 << i)] = pc[bit] + 1
    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: Runtime Error

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 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, k+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 = [0]*(1 << p)
    for bit in range(1 << p):
        for i in range(p):
            if not bit & (1 << i):
                pc[bit | (1 << i)] = pc[bit] + 1
    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: Runtime Error

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 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, k+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 = [0]*(1 << p)
    for bit in range(1 << p):
        for i in range(p):
            if not bit & (1 << i):
                pc[bit | (1 << i)] = pc[bit] + 1
    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: Runtime Error

Solution code:
import sys
import numpy as np

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: Runtime Error

Solution code:
import sys
import numpy as np

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

A = 1024

def main(N, V, W, v, L):
    def precompute(N, V, W):
        U = 10**5 + 10
        dp = np.zeros((A, U), np.int32)
        for v in range(1, min(A, N + 1)):
            p = v // 2
            dp[v] = dp[p]
            dp[v, W[v]:] = np.maximum(dp[v, W[v]:], dp[p, :-W[v]] + V[v])
            for i in range(1, U):
                dp[v][i] = max(dp[v][i], dp[v][i - 1])
        return dp

    dp = precompute(N, V, W)
    values = np.empty(A, np.int32)
    weights = np.empty(A, np.int32)

    def solve(i, lim, values, weights, dp):
        if i < A:
            return dp[i][lim]
        values[0] = 0
        weights[0] = 0
        p = 0
        while i >= A:
            for j in range(1 << p):
                values[j + (1 << p)] = values[j] + V[i]
                weights[j + (1 << p)] = weights[j] + W[i]
            p += 1
            i >>= 1
        best = 0
        for n in range(1 << p):
            if weights[n] > lim:
                continue
            x = dp[i][lim - weights[n]] + values[n]
            best = max(best, x)
        return best

    Q = len(v)
    for i in range(Q):
        x = solve(v[i], L[i], values, weights, dp)
        print(x)

        
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(i4,i4[:],i4[:],i4[:],i4[:])')(main)
    cc.compile()
    exit()

from my_module import main

N = int(readline())
stdin = np.array(read().split(), np.int32)
V = np.zeros(N + 1, np.int32)
W = np.zeros(N + 1, np.int32)
V[1:] = stdin[:N + N:2]
W[1:] = stdin[1:N + N:2]
query = stdin[N + N + 1:]
v, L = query[::2].copy(), query[1::2].copy()

main(N, V, W, v, L)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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

A = 512

def main(N, V, W, v, L):
    def precompute(N, V, W):
        U = 10**5 + 10
        dp = np.zeros((A, U), np.int32)
        for v in range(1, min(A, N + 1)):
            p = v // 2
            dp[v] = dp[p]
            dp[v, W[v]:] = np.maximum(dp[v, W[v]:], dp[p, :-W[v]] + V[v])
            for i in range(1, U):
                dp[v][i] = max(dp[v][i], dp[v][i - 1])
        return dp

    dp = precompute(N, V, W)
    values = np.empty(A, np.int32)
    weights = np.empty(A, np.int32)

    def solve(i, lim, values, weights, dp):
        if i < A:
            return dp[i][lim]
        values[0] = 0
        weights[0] = 0
        p = 0
        while i >= A:
            for j in range(1 << p):
                values[j + (1 << p)] = values[j] + V[i]
                weights[j + (1 << p)] = weights[j] + W[i]
            p += 1
            i >>= 1
        best = 0
        for n in range(1 << p):
            if weights[n] > lim:
                continue
            x = dp[i][lim - weights[n]] + values[n]
            best = max(best, x)
        return best

    Q = len(v)
    for i in range(Q):
        x = solve(v[i], L[i], values, weights, dp)
        print(x)

        
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(i4,i4[:],i4[:],i4[:],i4[:])')(main)
    cc.compile()
    exit()

from my_module import main

N = int(readline())
stdin = np.array(read().split(), np.int32)
V = np.zeros(N + 1, np.int32)
W = np.zeros(N + 1, np.int32)
V[1:] = stdin[:N + N:2]
W[1:] = stdin[1:N + N:2]
query = stdin[N + N + 1:]
v, L = query[::2], query[1::2]

main(N, V, W, v, L)

Submission status: Runtime Error

Solution code:
def solve(n, k, s, t, a_list):

    if s & t != s:
        return 0

    s_list = [0] * 18
    t_list = [0] * 18
    ab_list = [[0] * 18 for _ in range(n)]

    for i in range(18):
        s_list[i] = (s // (2 ** i)) % 2
        t_list[i] = (t // (2 ** i)) % 2
        for m in range(n):
            ab_list[m][i] = (a_list[m] // (2 ** i)) % 2

    # select
    m_list = []
    for m in range(n):
        flag = True
        for i in range(18):
            if s_list[i] == 1 and ab_list[m][i] == 0:
                # fail
                flag = False
            if t_list[i] == 0 and ab_list[m][i] == 1:
                # fail
                flag = False
        if flag:
            m_list.append(m)

    mm = len(m_list)
    if mm == 0:
        return 0

    u = 0
    for i in range(18):
        if s_list[i] == 0 and t_list[i] == 1:
            u += 2 ** i

    # new list
    a_list_new = [a_list[m] & u for m in m_list]

    res = 0

    for m in range(mm):
        # force use
        dp = [[0] * (2 ** 18) for _ in range(mm)]
        a = a_list_new[m]
        dp[0][0] = 1
        for n in range(m + 1, mm):
            for i in range(mm - 1, 0, -1):
                for j in range(2 ** 18):
                    dp[i][j | (a_list_new[n] ^ a)] += dp[i - 1][j]
        for i in range(k):
            res += dp[i][u]

    return res


def main():
    n, k, s, t = map(int, input().split())
    a_list = list(map(int, input().split()))
    res = solve(n, k, s, t, a_list)
    print(res)


def test():
    assert solve(3, 3, 0, 3, [1, 2, 3]) == 2
    assert solve(5, 3, 1, 7, [3, 4, 9, 1, 5]) == 2
    assert solve(5, 4, 0, 15, [3, 4, 9, 1, 5]) == 3


if __name__ == "__main__":
    test()
    main()

Submission status: Runtime Error

Solution code:


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

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

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

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):
            break
    if (AND == S) and (OR == T):
        break
        
if K == k:
    print(1)
    exit()

#print(c)
a = max(0, len(A_)-k)
count = 1
for i in range(1, K-k+1):
    #print(combinations_count(a, i))
    if a >= i:
        count += combinations_count(a, i)

print(count)

Submission status: Runtime Error

Solution code:
a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())
x=a-b
y=abs(x)
if v*t>=(y+w*t):
    print("YES")
else:
    print("NO")

Submission status: Runtime Error

Solution code:


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

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

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

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):
            break
    if (AND == S) and (OR == T):
        break

#print(c)
a = max(0, len(A_)-k)
count = 1
for i in range(1, K-k+1):
    #print(combinations_count(a, i))
    if a >= i:
        count += combinations_count(a, i)

print(count)

Submission status: Runtime Error

Solution code:
hu

Submission status: Runtime Error

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

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

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):
            break
    if (AND == S) and (OR == T):
        break

#print(c)
a = len(A_)-k
count = 1
for i in range(1, K-k+1):
    #print(combinations_count(a, i))
    count += combinations_count(a, i)

print(count)

Submission status: Runtime Error

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: Runtime Error

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 1 << sum(choose(n - i, x) for x in range(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)))