首页 > 其他分享 >线性基学习总结

线性基学习总结

时间:2023-01-30 21:34:54浏览次数:40  
标签:总结 表示 元素 枚举 学习 集合 异或 线性

0.引入
令长度为\(n\)的有限集合\(S_0\in \mathbb{Z}\),考虑用01串表示其中的每个元素以及异或后可能产生的值,显然至少需要\(\lceil log_2 max(S_0)\rceil\)位来表示,同时会产生一个封闭集。
但是如果直接枚举生成需要枚举\(2^n\)次,因此需要一个更高效的表示方式。

1.线性基
线性基是用于表示集合\(S\)中的元素的基底,且\(S\)中元素由线性基中的元素互相异或产生。
举例: \(\{1, 2, 3, 4, 5, 6, 7\}\) 的一种线性基为 \(\{1, 2, 4\}\)。

2.例题

给定有限集合\(S\),求\(S\)的最大异或和。

先举个例子:\(S = \{1, 2, 3, 4, 5, 6, 7, 8\}\)
一眼可以看出必须包含\(8\)。为啥?因为如果不包含\(8\)那第\(4\)位上必为\(0\)。

标签:总结,表示,元素,枚举,学习,集合,异或,线性
From: https://www.cnblogs.com/aspectofthemind/p/17077291.html

相关文章

  • 后端应用分层经验总结
    后端应用分层是什么,例如:你用SpringMVC开发web程序、项目用三层架构分包,这些都用了分层思想。MVC模式包含了三部分:视图(view):负责界面显示、处理用户交互。如......
  • MarkDown学习
    Markdown学习一、标题通过井号个数控制标题级数一级标题二级标题三级标题以此类推二、字体粗体:内容由两个星号括起来斜体:内容由一个星号括起来斜体加粗:内容由......
  • Linux学习-DAY6
    第4章Vim编辑器与Shell脚本命令1.Vim文本编辑器Vim编辑器中设置了3种模式—命令模式、末行模式和编辑模式,每种模式分别又支持多种不同的命令快捷键,这大大提高了工作效率,而......
  • 进程管理学习2
    4进程管理死锁问题设备分配形成环路进程通信问题导致死锁定义各并发进程彼此互相等待对方所拥有的资源,且这些并发进程在得到对方的资源之前不会释放自己所拥有的资......
  • jQuery基础学习随笔 2023
    jQuery多库共存//1.如果$符号冲突,就使用jQueryconsole.log(jQuery("div"));//$("div")//......
  • RxJava2.x的理解与总结
    RxJava2.x的理解与总结RxJava是一个基于观察者设计模式将链式编程和异步结合在一起的开源库。链式编程通过查看GitHub开源项目的简介开源知道,RxJava有几个基类。他们......
  • PYTHON银行机器学习:回归、随机森林、KNN近邻、决策树、高斯朴素贝叶斯、支持向量机SV
    全文下载链接:http://tecdat.cn/?p=26219最近我们被客户要求撰写关于银行机器学习的研究报告,包括一些图形和统计输出。该数据与银行机构的直接营销活动相关,营销活动基于电......
  • 前期学习准备
    学习资料个人博客:https,证书过期,忽略 https://www.liuqingzheng.top/cnblogs博客(后期迁移到这里,高级部分的内容) https://www.cnblogs.com/liuqingzheng知乎 https:/......
  • Day01 Markdown学习
    一级标题(一个)二级标题(两个)三级标题(三井号键)ctrl+(1~6)快捷标题加粗部分(两个星号)斜体部分(一个星号)斜体加粗(三个星号)删除线(两个波浪号)无序列表无序列表有序......
  • 2023/1/30 考试总结
    7.30~7.50啥也不会,摆大烂。8.00~8.30T3应该是经典容斥,但是转移顺序怪怪的。似乎走到每个点的组合唯一,然后组成新的坐标系就能做了。8.30~9.50细节比较多,调了半天。1......