原题链接

题解

1.先想想能不能暴力？
发现好像不行，因为不知道哪些元素组合的按位与能恰好有k个1
2.观察数据范围，发现 \(a_i \leq 63\) 也就是说，按位与的结果最大不会大于63 ，即 6 位 1 ，这暗示着我们可能可以从这里入手，即遍历所有按位与的情况，然后判断每种有k个1的按位与，有几个子序列能达到
3.对于每种有k个1的按位与，如何得出有几个子序列能达到它呢？
这里就是状态的巧妙之处了
所有子序列 = \(\sum_{i=1}^{n} S_i\) 其中 \(S_i\) 是以 \(i\) 为结尾的子序列
设 \(dp[i][j]\) 有多少个结尾不大于 \(i\) 的子序列（前缀和的思想好像在dp里经常出现）， 且其按位与能达到 j
则 \(dp[i][j\ \& \ a_i]=dp[i-1][j\ \& \ a_i]+dp[i-1][j]\)
即若已知前 \(i\) 个数，按位与能达到 \(j\) 和 \(a_i\ \&\ j\) 的子序列个数，那么前 \(i+1\) 个数，按位与能达到 \(a_i\ \&\ j\) 的子序列个数也已知

code

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int a[200005]={0};
int dp[200005][70]={0};
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;

        for(int i=1;i<=n;i++) cin>>a[i];

        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=63;j++) dp[i][j] = dp[i-1][j];
            for(int j=63;j>=0;j--)
            {
                dp[i][j & a[i]] = (dp[i][j & a[i]] + dp[i-1][j]) % mod;
            }
            dp[i][a[i]] = (dp[i][a[i]] + 1LL) % mod;
        }

        int ans=0;
        for(int i=63;i>=0;i--)
        {
            int cnt=0;
            int tem=i;
            while(tem)
            {
                cnt += (tem % 2LL);
                tem >>= 1LL;
            }
            if(cnt == k) ans = (ans + dp[n][i]) % mod;
        }
        cout << ans << endl;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=63;j++) dp[i][j]=0;
        }
    }
    return 0;
}