注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[CodeForces][#257 Div.1 D]Jzzhu and Numbers  

2014-10-14 08:08:46|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
D. Jzzhu and Numbers
依旧是看的题解
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1e6+10;
const int MOD = 1E9+7;
const int LOGN = 21;
int n,m,data[N];
int two[50];
int f[LOGN][N];
int scan(){int i=0;scanf("%d",&i);return i;}
void update(int &a,int b){
a+=b;
if(a >= MOD)a-=MOD;
if(a < 0) a+=MOD;
}
int pow(int x,int k){
int re=1;
for(;k;k/=2,x=((long long)x*x)%MOD)
if(k&1)re = ((long long)re*x)%MOD;
return re;
}
int main(){
//freopen("in.txt", "r", stdin);
int i,j;
for(two[0] = 1,i = 1;i<=30;i++)two[i] = two[i-1]*2;
int mn=0,mlogn,ans=0;
n = scan();
for(i=1;i<=n;i++)mn = max(mn,(data[i] = scan()));
if(mn)mlogn = log2(mn);
else mlogn=0;
for(i=1;i<=n;i++)f[0][data[i]]++;

//f[i][j] 表示i位以后必须完全相同,前i位只要and结果不变就行
//f[mlogn][j] & x = x
for(i=0;i<=mlogn;i++)
for(j=0;j<=mn;j++){
if(j & two[i])
update(f[i+1][j],f[i][j]),
update(f[i+1][j^two[i]],f[i][j]);
else
update(f[i+1][j],f[i][j]);
}

for(i=0;i<=mn;i++){
int tmp = pow(2,f[mlogn+1][i])-1,cot=0,ii=i;
for(;ii;ii/=2)if(ii&1)cot++;
if(cot&1)update(ans,-tmp);
else update(ans,tmp);
}
printf("%d\n",ans);
return 0;
}

题解:
    容斥原理。
    首先Dp预处理出f[i]表示i&x = i的个数
    那么设状态f[i][j]表示前j位满足i&x=i,后面的位必须相等
        对于f[i][j]如果i的第j位是1,那么 = f[i-1][j]
        如果i的第j位是0,那么 = f[i-1][j] + f[i-1][j^(1<<(i-1))]
    对于f[i][max]中保留的数,必定有全部and之后再and i = i,不等于题目需要的0,属于不合法方案。所以又变成了合法方案 - 不合法方案适用容斥原理。
其实我还是不太懂容斥原理
  评论这张
 
阅读(69)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017