CF449D: Jzzhu and Numbers

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

题解

记 cvc_vcv​ 为 [ai=v][a_i=v][ai​=v] 的个数， NNN 为二进制位数。
设 fSf_SfS​ 表示位与和在二进制下包含 SSS 的子集数。
由定义易得:
fS=2∑S⊆TcTf_S=2^{\sum\limits_{S\sube T} c_T}fS​=2S⊆T∑​cT​

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

即:
ans=∑S=02N−1(−1)popcount(S)fSans=\sum_{S=0}^{2^N-1}(-1)^{popcount(S)}f_Sans=S=0∑2N−1​(−1)popcount(S)fS​

参考代码

#include
using namespace std;templateinline 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;tfor(int i=0;i<1<if(!(i&1<if(pcnt(i)&1)ans=(ans-f[i])%P;//容斥else ans=(ans+f[i])%P;}cout<<(ans+P)%P<<'\n';return 0;
}