【状态设计优化DP+位运算】CF871div4 H

阳光穿透心脏的1/2处 2024-03-22 13:26 45阅读 0赞

[Problems - Codeforces][]

题意：

给定一个序列，问有多少子序列，使得子序列的元素之与的位数是K

![3fff87c32c8d4316adbbb0137bacf517.png][]

思路：

子序列：一定是计数DP

ai只有63：不能对ai状压，这样空间就是(1<<63)，根本开不下，虽然说也能做

可以试试这样的状态设计：

设dp\[i\]\[j\]为前i个数，子序列与之和为j的方案数

然后就是按选不选ai来分类

统计答案的时候枚举一下就行

重要的是在初始化的时候，应该初始化成(1<<6)-1，因为与是越与越小的

最后统计答案的时候，若K=6，则需要减1，因为需要减去初始化的那个部分

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxv=1e6+10; 
    const int mod=1e9+7;
    
    int N,K;
    int a[mxn],dp[mxn][110];
    
    void solve(){
    	cin>>N>>K;
    	for(int i=0;i<=N;i++){
    		for(int j=0;j<=63;j++) dp[i][j]=0;
    	}
    	for(int i=1;i<=N;i++) cin>>a[i];
    	dp[1][a[1]]+=1;
    	dp[1][63]+=1;
    	for(int i=2;i<=N;i++){
    		for(int j=0;j<=63;j++){
    			dp[i][j]=dp[i-1][j];
    		}
    		for(int j=0;j<=63;j++){
    			dp[i][j&a[i]]=(dp[i][j&a[i]]+dp[i-1][j])%mod;
    		}
    	}
    	int ans=0;
    	for(int j=0;j<=63;j++){
    		if(__builtin_popcount(j)==K) ans=(ans+dp[N][j])%mod;
    	}
    	cout<<(K==6?ans-1:ans)<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problems - Codeforces]: https://codeforces.com/contest/1829/problems
[3fff87c32c8d4316adbbb0137bacf517.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/95fe2447888444dda62558a7474696d8.png