网站首页
编程语言
数据库
系统相关
其他分享
编程问答
直接证明
2024-11-21
枚举子集的方法
可能在状压dp中运用的会比较多——首先直接看代码(再来解释):for(intj=st,t;j;j=(j-1)&st)t=st^j;其中,st是枚举的集合,j是子集,t是j对于st的补集。但是要注意这个办法没有枚举空集,需要自行处理。考虑证明一下:我们分三步,分别证明正确性、不重、不漏:正确性由于这个j=(j-1)&st,所