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

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

容斥原理  

2017-08-04 21:11:48|  分类: 算法&数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
容斥原理 - 杨鸿飞 - 杨鸿飞的博客
求证:A or B or C or ...=A+B+...-A and B-A and C-B and C-...+A and B and C...(参与and的元素有奇数个就+,否则-)
证明:数学归纳法,已知A or B=A+B-A and B,推A or B or C
        A or B or C
      =(A or B)or C
      =(A or B)+C-(A or B) and C    ->(A or B)看成A,C看成B,代入A or B=A+B-A and B
      =A+B-A and B+C-(A and C) or (B and C)
->A和B的并集与C的交集,就是A与C的交集,B与C的交集的合并->(A or B) and C=(A and C) or (B and C)
      =A+B-A and B+C-[A and C + B and C - (A and C) and (B and C)]
      =A+B+C-A and B-A and C-B and C+A and B and C

 
=============================
模板:

for (int i=1; i<(1<<n); i++) //从1开始
{
s=ALL //使s and x=x

int k=-1; //0个时是偶数,要减

for (int j=0; j<n; j++)
if (((1<<j)&i))
{
k*=-1; //奇偶变化

s=And(s,a[j]);
}

ans+=q(s)*k;
}

用递归写可以少一维这个for (int j=0; j<n; j++)
  评论这张
 
阅读(6)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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