CF1829H题解

· · 题解

DP。

设计状态 f(i,j) 表示以 i 为结尾的子序列，与运算和为 j 的方案数。

状态转移考虑选 / 不选 a_i 的方案数：

\begin{aligned} f(i,j)&=f(i,j)+f(i-1,j)\\ f(i,j\&a_i)&=f(i,j\&a_i)+f(i-1,j) \end{aligned}

对于 a_i，它自己可以成为一个与运算和为 a_i 的子序列。

找到每一个满足 \text{popcount}(i)=k 的 i，答案即为：\sum f(n,i)。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int mod=1e9+7,maxn=2e5+5;
int a[maxn],f[maxn][65];

int popcount(int x)
{
    int cnt=0;
    while(x) x&=(x-1),cnt++;
    return cnt;
}

void solve()
{
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) memset(f[i],0,sizeof f[i]),f[i][a[i]]=1;
    for(int i=1;i<=n;i++) 
        for(int j=0;j<64;j++) f[i][j]=(f[i-1][j]+f[i][j])%mod,f[i][j&a[i]]=(f[i-1][j]+f[i][j&a[i]])%mod;
    int ans=0;
    for(int i=0;i<64;i++) if(popcount(i)==k) ans=(ans+f[n][i])%mod;
    cout<<ans<<endl;
}

signed main()
{
    int t;cin>>t;
    while(t--) solve();
    return 0;
}