首页 > 代码库 > Codeforces 449D：Jzzhu and Numbers
Codeforces 449D：Jzzhu and Numbers
Codeforces 449D：Jzzhu and Numbers
题目链接：http://codeforces.com/problemset/status?friends=on
题目大意：给出$n$个数，求有多少种组合使得$a_{i_1}\&a_{i_2}\&...\&a_{i_k}=0(0 \leqslant i < n)$，答案对$10^9+7$取模.
容斥原理+DP
设位与$(\&)$后二进制表示中有$k$个$1$的组合数为$A_k$，则有，
$A_0=$所有情况$-A_1+A_2-...+(-1)^kA_k=$所有情况$+\sum_{i=1}^k(-1)^kA_k$.
关键在于求出$A_k$.
我们曾在这道题（http://www.cnblogs.com/barrier/p/6664229.html）里求过：
$n$个数中，与$x$位与后仍为$x$的个数$f(x)$，
而若干个数位与后为$x$的组合数为$2^{f(x)}-1$.
至此，已能够求出$A_K$.
若设$g(x)$为$x$的二进制表示中$1$的个数，则$A_0=$所有情况$+\sum_{i=1}^k(-1)^{g(i)}(2^{f(i)}-1)$.
（由于任何数位与$0$均为$0$，所以有$f(0)=n$，故可以化简成$A_0=\sum_{i=0}^k(-1)^{g(i)}(2^{f(i)}-1)$）
对于这道题来说，可以预处理$2^k\%mod$，总复杂度为$O(nlgn)$.
（当然也可以不进行预处理，考虑到乘法溢出，复杂度为$O(nlg^3n)$，也是可以过的...）
代码如下：
1 #include <cstdio> 2 #define N 1000005 3 using namespace std; 4 typedef long long ll; 5 const int mod=1e9+7; 6 int n,t,f[1<<20],pow2[1<<20]; 7 int mus(int x,int y){ 8 return (x-y+mod)%mod; 9 }10 void getf(){11 for(int i=0;i<20;++i)12 for(int j=0;j<(1<<20);++j)13 if((j&(1<<i))==0)f[j]+=f[j|(1<<i)];14 }15 int solve(){16 getf();17 int ans=mus(pow2[n],1);18 for(int i=1;i<(1<<20);++i){19 int g=0;20 for(int j=0;j<20;++j)if(i&(1<<j))g++;21 if(g&1)ans=mus(ans,mus(pow2[f[i]],1));22 else ans=(ans+mus(pow2[f[i]],1))%mod;23 }24 return ans;25 }26 int main(void){27 scanf("%d",&n);28 for(int i=0;i<n;++i){29 scanf("%d",&t);30 f[t]++;31 }32 pow2[0]=1;33 for(int i=1;i<=1000000;++i)pow2[i]=(2*pow2[i-1])%mod;34 printf("%d\n",solve());35 }
Codeforces 449D：Jzzhu and Numbers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。