【学习笔记】子集DP

server/2024/9/24 20:20:29/

背景

有一类问题和子集有关。
给你一个集合 S S S,令 T T T S S S 的超集,也就是 S S S 所有子集的集合,求 T T T 中所有元素的和。

暴力1

先预处理子集的元素和 A i A_i Ai,再枚举子集。

for(int s=0; s<(1<<n); s++)for(int i=0; i<(1<<n); i++)if(s&i) f[s]+=A[i];

时间复杂度 O ( n 4 ) O(n^4) O(n4)

暴力2

其实枚举子集有个小 trick

for(int s=0; s<(1<<n); s++)for(int i=s; i>0; i=(i-1)&s)f[s]+=A[i];

由二项式定理,时间复杂度为 O ( 3 n ) O(3^n) O(3n)

子集DP

g s , i g_{s,i} gs,i 为状态为 s s s,只考虑后 i i i 位转移的答案。
那么转移就是

g s , i = { g s , i − 1 s & ( 1 < < i ) = 0 g s , i − 1 + g s ⨁ ( 1 < < i ) , i − 1 o t h e r w i s e g_{s,i} = \begin{cases} g_{s,i-1} & s\&(1<<i)=0 \\g_{s,i-1} +g_{s\bigoplus(1<<i),i-1}&otherwise\end{cases} gs,i={gs,i1gs,i1+gs(1<<i),i1s&(1<<i)=0otherwise
这样可以做到不重不漏的转移。
推荐一篇blog,非常形象:https://www.cnblogs.com/maple276/p/17975253

可以发现,这个转移只和上一层有关,所以第二维是可以省略的。

前缀和(子集向超集转移)
for(int i=0; i<n; i++)
{for(int s=0; s<(1<<n); s++){if(s&_2)(f[s]+=f[s^_2])%(mod-1);}_2<<=1;
}
后缀和(超集向子集转移)
for(int i=0; i<n; i++)
{for(int s=0; s<(1<<n); s++){if(!(s&_2))(f[s]+=f[s^_2])%(mod-1);}_2<<=1;
}
差分
//后缀差分
for(int i=0; i<20; i++)
{for(int s=0; s<S; s++){if(!(s&_2))(f[s]-=f[s^_2])%=mod;}_2<<=1;
}

例题

CF165E

定义 x x x y y y 相容为 x & y = 0 x\&y=0 x&y=0,给你一个序列 A A A,对于每个元素,在 A A A 中找到和它相容的元素。 ∣ A ∣ ≤ 1 0 6 , A i ≤ 4 × 1 0 6 |A|\leq 10^6,A_i\leq 4\times 10^6 A106,Ai4×106

思路

x & y = 0 x\&y=0 x&y=0 等价于 x ˜ & y = y \~x\&y=y x˜&y=y,那么只需要对 A A A做类似前缀和的操作,加法改成覆盖即可。

代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int S=1<<22;
void O_o()
{int n;cin>>n;vector<int> f(S,-1),a(n+1);for(int i=1; i<=n; i++){cin>>a[i];f[a[i]]=a[i];}int _2=1;for(int i=0; i<=21; i++){for(int s=0; s<S; s++){if(!(s&_2)) continue;if(f[s^_2]!=-1)f[s]=f[s^_2];}_2<<=1;}int t=S-1;for(int i=1; i<=n; i++){cout<<f[t^a[i]]<<" ";}cout<<"\n";
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cout<<fixed<<setprecision(2);int T=1;
//	cin>>T;while(T--){O_o();}
}

http://www.ppmy.cn/server/90383.html

相关文章

从0开始搭建vue + flask 旅游景点数据分析系统(一):创建前端项目

根据前面的爬虫课程&#xff0c;我们重新开一个坑&#xff0c;就是基于爬取到的数据&#xff0c;搭建一个vueflask的前后端分离的数据分析系统 1 通过这个系列教程可以学习到什么&#xff1f; 从0开始搭建一个 vue flask 的数据分析系统&#xff1b;了解系统的整体架构&…

vue3+ts+vite+electron+electron-packager打包成exe文件

目录 1、创建vite项目 2、添加需求文件 3、根据package.json文件安装依赖 4、打包 5、electron命令运行 6、electron-packager打包成exe文件 Build cross-platform desktop apps with JavaScript, HTML, and CSS | Electron 1、创建vite项目 npm create vitelatest 2、添…

网络安全的重要性与挑战

网络安全的重要性与挑战 网络安全是指保护网络系统中的数据免受未经授权的访问、泄露、篡改或破坏的过程。它关乎个人隐私的保护、企业资产的安全乃至国家安全的稳定。随着互联网和物联网的快速发展&#xff0c;网络攻击和威胁也越来越多样化和复杂化&#xff0c;网络安全已成为…

【深度学习入门】安装conda/miniconda、所需包类、CUDA与conda/Miniconda间的关系

深度学习入门 须知 本教程跟随李沐老师课程随笔&#xff0c;课程链接点击此处。 CUDA和Anaconda的关系 CUDA Toolkit是由Nvidia官方提供的完整工具包&#xff0c;其中提供了Nvidia驱动程序、开发CUDA程序相关的开发工具包等。 Anaconda在安装Pytorch等会用到的CUDA的框架时…

MongoDB教程(十九):MongoDB全文检索

&#x1f49d;&#x1f49d;&#x1f49d;首先&#xff0c;欢迎各位来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里不仅可以有所收获&#xff0c;同时也能感受到一份轻松欢乐的氛围&#xff0c;祝你生活愉快&#xff01; 文章目录 引言一、全文索…

模拟实现短信登录功能 (session 和 Redis 两种代码实例) 带前端演示

目录 整体流程 发送验证码 短信验证码登录、注册 校验登录状态 基于 session 实现登录 实现发送短信验证码功能 1. 前端发送请求 2. 后端处理请求 3. 演示 实现登录功能 1. 前端发送请求 2. 后端处理请求 校验登录状态 1. 登录拦截器 2. 注册拦截器 3. 登录完整…

C++ set

1. 背景 关联式容器 STL 中的部分容器&#xff0c;比如&#xff1a; vector 、 list 、 deque 、forward_list(C11)等&#xff0c;这些容器统称为序列式容器&#xff0c;因为其底层为线性序列的数据结构&#xff0c;里面存储的是元素本身。那什么是关联式容器&#xff1f;它与…

【计算机网络】三次握手、四次挥手

问&#xff1a;三次握手 四次挥手 TCP 连接过程是 3 次握手&#xff0c;终止过程是 4 次挥手 3次握手 第一步&#xff1a;客户端向服务器发送一个带有 SYN&#xff08;同步&#xff09;标志的包&#xff0c;指示客户端要建立连接。 第二步&#xff1a;服务器收到客户端的请求…