题解
知识点：线性dp，位运算。
考虑设 \(f_{i,j}\) 表示考虑了前 \(i\) 个数字，与和为 \(j\) 的方案数。转移方程显然。
注意初值为 \(f_{0,63} = 1\) 表示空集，此时注意 \(k = 6\) 时要减去空集这一个方案。
当然也可以选择不加入空集，但dp过程需要特别处理只选自己的方案。
时间复杂度 \(O(64n)\)
空间复杂度 \(O(64n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 1e9 + 7;
int a[200007];
int f[200007][64];
bool solve() {
int n, k;
cin >> n >> k;
for (int i = 1;i <= n;i++) cin >> a[i];
f[0][63] = 1;
for (int i = 1;i <= n;i++) {
for (int j = 0;j <= 63;j++) f[i][j] = 0;
for (int j = 0;j <= 63;j++) {
(f[i][j] += f[i - 1][j]) %= P;
(f[i][a[i] & j] += f[i - 1][j]) %= P;
}
}
int ans = 0;
for (int i = 0;i <= 63;i++) if (__builtin_popcount(i) == k) (ans += f[n][i]) %= P;
cout << ans - (k == 6) << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}