动态规划好题。
对于此题解，不懂的问题可以私信笔者。
解题方法
用 \(dp_{i,j}\) 表示前 \(i\) 个数选择了若干个数按位与之后为 \(j\) 的子序列个数。
接下来思考转移。
想到这里，你会发现按位与没有逆运算，一次我们要正推，例如 \(f_{i+2}=f_{i}+f_{i+1}\)。
那么转移方程不就来了嘛：
第 \(i+1\) 个数按位与 \(j\) 等于 原来的加上 \(dp_{i,j}\)。
\[dp_{i+1,j \& a_{i+1}}= dp_{i+1,j \& a_{i+1}}+dp_{i,j}\]还有就是不将第 \(i\) 个数加入此序列。
\[dp_{i+1,j}=dp_{i+1,j}+dp_{i,j} \]其中 \(\&\) 是按位与。
边界
计数题一定要有边界，否则算了等于白算（只有 \(0\)）。
\(dp_{0,63}=1\)，但是要特判。
特判：\(dp_{0,63}=1\) 相当于是空序列，是“借”的，因此当 \(k=6\) 时答案要减 \(1\)（因为此时 \(63\) 刚好有 \(6\) 个 \(1\)（二进制下））。
code
__builtin_popcount(i) 表示计算 \(i\) 的二进制中有多少个 \(1\)。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define mod 100000007
int a[200005];
ll dp[200005][70];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=0;i<=n;i++){
for(int j=0;j<=63;j++){
dp[i][j]=0;
}
}
dp[0][63]=1;
for(int i=0;i<n;i++){
for(int j=0;j<=63;j++){
dp[i+1][j&a[i+1]]=(dp[i+1][j&a[i+1]]+dp[i][j])%mod;
dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
}
}
ll ans=0;
for(int i=0;i<=63;i++){
if(__builtin_popcount(i)==k) ans=(ans+dp[n][i])%mod;
}
if(k==6) ans=((ans-1)+mod)%mod;
printf("%lld\n",ans);
}
return 0;
}
防抄袭万岁。