CF449D: Jzzhu and Numbers

原题链接:https://codeforces.com/problemset/problem/449/D

题解

记 $c_v$ 为 $[a_i=v]$ 的个数， $N$ 为二进制位数。
设 $f_S$ 表示位与和在二进制下包含 $S$ 的子集数。
由定义易得:
$$f_S=2^{\sum _{S\subseteq T}{c}_T}$$

(不用减一，包含空集)
可由 $SOSDP$ 枚举超集在 $O(2^{N}N)$ 内求出。
由容斥原理可知答案:
$$\begin{array}{rl}位与和为0的子集数=& 位与和二进制下至少有0个1的子集数\\ & -位与和二进制下至少有1个1的子集数\\ & +位与和二进制下至少有2个1的子集数\\ & ...\end{array}$$

即:
$$ans=\sum _{S=0}^{2^N-1}(-1{)}^{popcount(S)}{f}_S$$

参考代码

#include<bits/stdc++.h>
using namespace std;template<class T>inline void read(T&x){//快读char c,last=' ';while(!isdigit(c=getchar()))last=c;x=c^48;while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);if(last=='-')x=-x;
}const int MAXN=1e6+7,P=1e9+7,m=20;
int n;
int a[MAXN];
int f[MAXN<<1];//注意要开到1<<20以上int qpow(int x,int p){//快速幂(没必要,打2的幂次表即可)int ret=1;for(;p;x=1ll*x*x%P,p>>=1)if(p&1)ret=1ll*ret*x%P;return ret;
}int pcnt(int x){//popcount求二进制下1个数int ret=0;while(x){ret+=x&1;x>>=1;}return ret;
}int main()
{read(n);for(int i=1;i<=n;++i){read(a[i]);++f[a[i]];}for(int t=0;t<m;++t){for(int i=0;i<1<<m;++i){if(!(i&1<<t))f[i]+=f[i^1<<t];//SOS DP计算超集}}for(int i=0;i<1<<m;++i)f[i]=qpow(2,f[i]);int ans=0;for(int i=0;i<1<<m;++i){if(pcnt(i)&1)ans=(ans-f[i])%P;//容斥else ans=(ans+f[i])%P;}cout<<(ans+P)%P<<'\n';return 0;
}