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

枚举子集

枚举子集

发现自己经常记不住这个怎么写,就来写篇题解吧。

首先对于一个 \(n\) 位二进制数 \(x\),求二进制位上都是 \(x\) 的子集的数有哪些,

比如:101的子集有100、001、000。

然后这个东西如果直接 \(2^n\) 次枚举的话,复杂度就爆炸了。

所以可以用一个很厉害的东西,

代码长这样:

for(int i=(x-1)&x;i;i=(i-1)&x)

这个 \(i\) 直接就是枚举出来的子集了。

这个为啥是对的呢?

我的理解是,你普通枚举 \(i\)-- 了之后,可能出现一个地方 \(i\) 有个 \(1\) 但是 \(x\)\(0\)

所以你把 \(i\)\(x\) 与一下,来把这个 \(1\) 消掉就好了。

如果只求一个 \(x\) 的所有子集,那复杂度就是 \(2^n\)

但是如果求 \(1\sim 2^n-1\) 中的数字的所有子集,那这个的复杂度就是 \(3^n\)

(好像是用什么二项式定理求出来的,但是蒟蒻不会qwq)

例题

P3773 [CTSC2017] 吉夫特

发现组合数可以用 \(lucas\) 分解一下,相当于对于 \(2\le i \le k\)\(a_{b_i}\) 都要是 \(a_{b_{i-1}}\) 二进制位上的子集。

直接 \(dp\),设 \(f[i]\) 表示以 \(i\) 结尾的合法子序列个数。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10,mod=1e9+7;
int n,ans,f[N];
int main()
{scanf("%d",&n);for(int i=1,x;i<=n;i++){scanf("%d",&x);for(int j=(x-1)&x;j;j=(j-1)&x)f[j]=(f[j]+f[x]+1)%mod;ans=(ans+f[x])%mod;}printf("%d",ans);return 0;
}
http://www.hskmm.com/?act=detail&tid=14994

相关文章:

  • cv-css 快捷方式,将指定节点的计算样式获取下拉 获取tailwind网页样式成原生样式
  • day002
  • PyTorch图神经网络(四)
  • 软件工程:构建数字世界的基石
  • Avalonia 学习笔记07. Control Themes(控件主题)
  • matter 协议的架构;
  • matter 协议解析;
  • 9月23日
  • Nordic 的支持对Matter 协议的支持;
  • nRF54LM20A USB
  • nRF54LM20A GRTC
  • 2025年10款最佳生产力提效chrome插件推荐,亲测有用
  • Avalonia 学习笔记06. Page Layout(页面布局)
  • 发表第一篇文章,谈谈对软件工程的理解
  • nRF54LM20A 芯片分析;
  • 第二天
  • 内部类
  • NRF54L15 两者结合的jlink保护机制(硬件+软件)
  • 软件测试员的核心技能:一文掌握等价类划分与边界值分析
  • 《CBI 技术有聊》对话 OpenCSG:智能体落地困境与企业转型的必然路径
  • 个人对软件工程的理解
  • 9/23
  • NUMERICAL RESULT (2025/09/23)
  • 数组入门:从零基础到排序算法 - 教程
  • 用C/C++重构PowerShell:全面绕过安全机制的技术解析
  • Optuna v4.5新特性深度解析:GPSampler实现约束多目标优化
  • 题解:P4769 [NOI2018] 冒泡排序
  • 2025/9/23
  • Tita:更频繁的绩效考核周期的好处
  • 详细介绍:【Linux】Linux文件系统详解:从磁盘到文件的奥秘