310414: CF1829H. Don't Blame Me
Description
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.
InputEach 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$.
OutputFor 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$.
ExampleInput6 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 13Output
31 10 10 1 4032 15
Input
题意翻译
给定一个长度为 $n$ 的正整数数组 $a$，求有多少个非空子序列，使得这些子序列中的元素的按位与结果在二进制下恰好有 $k$ 个 $1$。答案对 $10^9+7$ 取模。 输入包括多组测试数据。第一行包含一个正整数 $t$，表示测试数据组数。依次描述每组测试数据。 每组测试数据的第一行包含两个整数 $n$ 和 $k$，分别表示数组的长度和满足条件的按位与结果二进制中有 $k$ 个 $1$。 每组测试数据的第二行包含 $n$ 个整数 $a_i$，表示数组 $a$ 中的元素。 对于每组测试数据，输出一行一个整数，表示满足条件的子序列数量。Output
给定一个由n个正整数组成的数组a，计算有多少个非空子序列，使得这些子序列中元素的按位AND结果在二进制表示中恰好有k个置位的比特。答案可能很大，所以结果要对10^9+7取模。
输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含两个整数n和k（1≤n≤2×10^5，0≤k≤6），分别表示数组的长度和按位AND结果中置位比特的数量。
- 第二行包含n个整数a_i（0≤a_i≤63），表示数组a的元素。
- 保证所有测试用例的n之和不超过2×10^5。
输出：
- 对于每个测试用例，输出一个整数，表示满足条件的子序列数量，结果对10^9+7取模。
示例输入输出：
输入：
```
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
```
输出：
```
31
10
10
1
4032
15
```题目大意： 给定一个由n个正整数组成的数组a，计算有多少个非空子序列，使得这些子序列中元素的按位AND结果在二进制表示中恰好有k个置位的比特。答案可能很大，所以结果要对10^9+7取模。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含两个整数n和k（1≤n≤2×10^5，0≤k≤6），分别表示数组的长度和按位AND结果中置位比特的数量。 - 第二行包含n个整数a_i（0≤a_i≤63），表示数组a的元素。 - 保证所有测试用例的n之和不超过2×10^5。 输出： - 对于每个测试用例，输出一个整数，表示满足条件的子序列数量，结果对10^9+7取模。 示例输入输出： 输入： ``` 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 ``` 输出： ``` 31 10 10 1 4032 15 ```