当前位置: 首页 > news >正文

关于子集的枚举与高维前缀和

今天集训的题我已经写不动了,下周开始会复习 dp, 现在就提前把一些东西补一补,这个说不好会在之后状压里边用到。

枚举子集

如何遍历一个集合的子集

通常我们会采取递归的方式,是 \(O(2^n)\) 的,但是这个样子我们在具体使用的时候是很不方便的,尤其是我们在对于一些二进制的东西做文章的时候。

所以我们需要这个循环形式的枚举子集。

for(int s=u; s; s=(s-1)&u)

这个样子我们就是在枚举 \(s\)\(u\) 的子集了。

先谈正确性,后谈复杂度。

为什么这个东西可以不重不漏?

很明显的,我们的减一是严格下降的,按位与是严格不升的,每一次操作必然会变小,故不会重复。

至于正确性,我们的减一实际上是删除 s 中最后一个一,再把它的右边全部变成一。我们为了让这个东西变成新的子集,我们需要删除 u 之中没有包含的 1,这个我们直接按位与清除一下就好啦。

时间复杂度就是明显的了,我们仅仅需要关注 1 的数量,复杂度自然是 \(O(2^{popcount(u)})\)

如何遍历一个集合子集的子集

for(int m=0; m<(1<<n); ++m){for(int s=m; s; s=(s-1)&m){......}
}

也就是直接套用上边的。

这个东西的复杂度是奇妙的,它竟然是 \(O(3^n)\) 的,比我们想象中要底很多很多。

如果 \(m\) 拥有 \(k\)\(1\),那么我们会枚举出来 \(2^k\) 个子集。

而对于一个 \(k\),我们可以找出来 \(\binom{n}{k}\) 个对应的集合满足有 \(k\) 个 1。

总数就变成了:\(\sum_{k=0}^{n}\binom{n}{k}2^k\)

根据二项式定理,这个东西等于 \((1+2)^n\) 的展开,因此是 \(O(3^n)\) 的,似乎很有用,避免了我们傻傻的 \(2^n\times 2^n\) 的枚举。

高维前缀和

又称 sosdp,我不知道为什么。

我们平常做一维或者二维前缀和都是用容斥原理求的,以二维为例。

\(sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]\)

但是我们还有一个求法,就是一维一维处理。

for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)a[i][j] += a[i - 1][j];
for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)a[i][j] += a[i][j - 1];

like that.

这个样子是一样的,我们采取这个思路。

对于求解 \(0\le i\le 2^n-1\)\(\sum_{j\in i} a[j]\) 这样的东西,我们可以使用这个思路。

我们不妨把集合看作多维空间中的点,第 \(i\) 位的 0/1 表示第 \(i\) 维的坐标。

于是乎就可以像之前那么做了,枚举维数与子集,在当前维度是 1 的地方从当前维度是 0 的地方转移过来。

for(int i=0; i<n; ++i){for(int j=0; j<(1<<n); ++j){if(j&(1<<i)) dp[j]+=dp[j^(1<<i)];}
}

于是就没有了,显然我们从枚举子集的 \(O(3^n)\) 优化到了 \(O(n\times 2^n)\)

http://www.hskmm.com/?act=detail&tid=22511

相关文章:

  • HyperWorks 14.0 轮毂仿真全流程详细教程
  • 原来的OJ怎么没了?
  • 【Linux】库的链接与加载 - 详解
  • CSP-S模拟26
  • 存在是必然的有机系统,好事多磨,心诚则灵
  • 2025 年陶土砖厂家权威推荐 TOP 品牌排行榜,劈开 / 红色 / 干挂 / 砌筑 / 仿古 / 透气 / 耐火 / 异型 / 装饰 / 外墙陶土砖产品厂家推荐
  • AGC015E Mr.Aoki Incubator
  • 2025 年臭氧发生器厂家 TOP 实力工厂推荐榜单排名,大中型 / 水处理 / 多功能臭氧发生器推荐这十家公司!
  • 2025 年采光瓦厂家 TOP 企业品牌推荐排行榜,详解数字化工厂与就近发货实力采光瓦推荐这十家公司!
  • 2025 年合成树脂瓦厂家 TOP 企业品牌推荐排行榜,防腐方案与定制能力全景对比合成树脂瓦公司推荐!
  • 2025 年人造草坪足球场厂家推荐 TOP10 品牌权威排行榜单,深度剖析人造草坪足球场行业优势公司
  • 2025 年望远镜厂家 TOP 企业品牌推荐排行榜,助你精准选购性价比高的望远镜推荐这十家公司!
  • Coze源码分析-资源库-删除数据库-后端源码-安全与错误处理 - 详解
  • 动手动脑实验性问题总结
  • 链表实现双端队列
  • FFmpeg和ZLMediaKit 实现本地视频推流
  • SQL 多表查询速查:JOIN、子查询一文全掌握 - 详解
  • 深入解析:数字和字节:Linux 中的内存如何工作?
  • AtCoder Beginner Contest 424 425 部分题解
  • 关于滚动数组
  • 第九篇
  • 2025 年宁波搬家公司推荐 TOP 权威榜单发布,多维度解读宁波搬家服务公司创新亮点举措
  • 2025 年检测器厂家推荐 TOP 品牌权威排名,防爆火焰 / 一体化火焰 / 紫外线火焰 / 离子火焰 / 红外线火焰 / 红紫外复合火焰 / 智能火焰检测器公司推荐
  • 9-29
  • 10-1
  • 2025母线槽源头厂家 TOP 工厂权威榜单揭晓,密集型、封闭、浇筑、耐火、防火、防水、插接式母线槽公司推荐!
  • 2025 年衬氟鹤管源头厂家 TOP 企业品牌推荐排行榜,天然气 / 低温 / LNG / 撬装 / 底装 / 火车 / 装卸车 / 上装 / 衬氟 / 下装鹤管公司推荐这 10 家
  • 2025 铜覆钢圆钢生产商厂家 TOP 企业品牌推荐榜单,铜覆钢接地极 / 棒 / 圆钢 / 扁钢 / 圆线 / 绞线 / 角钢 / 扁铁 / 管公司推荐这 10 家
  • 2025 年喷雾干燥机厂家 TOP 企业品牌推荐排行榜,无锡 / 常州喷雾干燥机 / 离心式 / 压力式 / 气流 / 造粒 / 有机溶剂 / 闭路循环 / 闭式循环 / 实验喷雾干燥机公司推荐!
  • 2025 年工业吊扇最新推荐权威排行榜:TOP5 优质品牌全面解析,助力企业高效选购