Don't Blame Me (Codeforces 1829H)
Tags: Math, bitmasks

Sadly, the problem setter couldn't think of an interesting story, thus he just asks you to solve the following problem.Given an array $$$a$$$ consisting of $$$n$$$ positive integers, count the number of non-empty subsequences for which the bitwise $$$\mathsf{AND}$$$ of the elements in the subsequence has exactly $$$k$$$ set bits in its binary representation. The answer may be large, so output it modulo $$$10^9+7$$$.Recall that the subsequence of an array $$$a$$$ is a sequence that can be obtained from $$$a$$$ by removing some (possibly, zero) elements. For example, $$$[1, 2, 3]$$$, $$$[3]$$$, $$$[1, 3]$$$ are subsequences of $$$[1, 2, 3]$$$, but $$$[3, 2]$$$ and $$$[4, 5, 6]$$$ are not.Note that $$$\mathsf{AND}$$$ represents the bitwise AND operation.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.The first line of each test case consists of two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$0 \le k \le 6$$$) — the length of the array and the number of set bits that the bitwise $$$\mathsf{AND}$$$ the counted subsequences should have in their binary representation.The second line of each test case consists of $$$n$$$ integers $$$a_i$$$ ($$$0 \leq a_i \leq 63$$$) — the array $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single integer — the number of subsequences that have exactly $$$k$$$ set bits in their bitwise $$$\mathsf{AND}$$$ value's binary representation. The answer may be large, so output it modulo $$$10^9+7$$$.


Sample Inputs:
6
5 1
1 1 1 1 1
4 0
0 1 2 3
5 1
5 5 7 4 2
1 2
3
12 0
0 2 0 2 0 2 0 2 0 2 0 2
10 6
63 0 63 5 5 63 63 4 12 13

Sample Outputs:
31
10
10
1
4032
15

Solution (Python):
from collections import Counter
testCases = int(input())
ans = []

def helper(v, hash, backT):
    temp = backT.copy()
    shift = (1 << hash[v]) - 1
    temp[v] = temp[v] + shift
    for i in range(0, 64):
        idx = i & v
        temp[idx] += backT[i] * shift
    return temp

def check(i, k):
    return bin(i).count('1', 2) == k

def sol():
    (_, k) = [int(x) for x in input().split()]
    backT = [0] * 64
    tempA = input().split()
    hash = Counter((int(x) for x in tempA))
    for v in hash:
        temp = helper(v, hash, backT)
        backT = temp.copy()
    count = 0
    for i in range(64):
        if check(i, k):
            count = count + backT[i]
    ans.append(count % int(1000000000.0 + 7))
for _ in range(testCases):
    sol()
for a in ans:
    print(a)

Solution (Python):
from collections import Counter
testCases = int(input())
ans = []

def helper(v, hash, backT):
    temp = backT.copy()
    shift = (1 << hash[v]) - 1
    temp[v] = temp[v] + shift
    for i in range(0, 64):
        idx = i & v
        temp[idx] += backT[i] * shift
    return temp

def check(i, k):
    return bin(i).count('1', 2) == k

def sol():
    (_, k) = [int(x) for x in input().split()]
    backT = [0] * 64
    tempA = input().split()
    hash = Counter((int(x) for x in tempA))
    for v in hash:
        temp = helper(v, hash, backT)
        backT = temp.copy()
    count = 0
    for i in range(64):
        if check(i, k):
            count = count + backT[i]
    ans.append(count % int(1000000000.0 + 7))
for _ in range(testCases):
    sol()
for a in ans:
    print(a)

Solution (Python):
from collections import Counter

def solution():
    (n, k) = map(int, input().split())
    a = Counter((int(i) for i in input().split()))
    dp = [0] * 64
    for num in a:
        new_dp = dp.copy()
        new_dp[num] += (1 << a[num]) - 1
        for i in range(64):
            new_dp[i & num] += dp[i] * ((1 << a[num]) - 1)
        dp = new_dp.copy()
    ans = 0
    for i in range(64):
        if bin(i).count('1', 2) == k:
            ans += dp[i]
    print(ans % MOD)
MOD = int(1000000000.0 + 7)
t = int(input())
for _ in range(t):
    solution()