首页 > 其他分享 >[学习笔记] 线性基

[学习笔记] 线性基

时间:2023-08-15 19:12:18浏览次数:31  
标签:cnt xor int void 笔记 学习 bs 线性

你说我一个连线性基都不会的人怎么可能走的远,我跟你说我也是这么想的,但是你先别急。

一、线性基

OI 中常用全部的就是 \(2\) 进制下的异或线性基。

线性基就是可以把一个集合里的数转化成一组基,使得这组基里所有 xor 出来的结果于原集合 xor 出来的结果完全一致。

这是一个线性基模板:

struct linear_basis_awa {
  ll bs[64];
  int cnt;
  inline void init () {
    for (int i = 0;i < 64; ++ i) bs[i] = 0;
    cnt = 0;
  }
  inline void ins (ll x) {
    if (!x) return ;
    for (int i = 62;i >= 0; -- i) {
      if (x & (1ll << i)) {
        if (bs[i]) x ^= bs[i];
        else {
          cnt ++;
          bs[i] = x;
          break;
        }
      }
    }
  }
  inline ll query_maxxor (ll x) {
    ll res = x;
    for (int i = 62;i >= 0; -- i) {
      if ((res ^ bs[i]) > res) res ^= bs[i];
    }
    return res;
  }
  inline void merge_bas (linear_basis_awa O) {
    for (int i = 0;i < 64; ++ i) ins (O.bs[i]);
  }
  inline void operator = (linear_basis_awa O) {
    for (int i = 0;i < 64; ++ i) bs[i] = O.bs[i];
    cnt = O.cnt;
  }
};

其中这里的 \(bs_{w}\) 是最高位为 \(2^w\) 的基向量。

线性基的插入

如果 \(x\) 这个数内包含 \(2^w\) 这一位,如果基中已经有,那么直接异或掉 \(2^w\),否则那就直接加入 \(x\),然后结束,时间复杂度 \(O(\log w)\)。

线性基求最大 xor 和

对于 query_maxxor (int v) 函数的解释:查询 \(\displaystyle \max_{S \subseteq \text{base}} \left[\left(\bigoplus_{x \in S} x\right) \oplus v\right]\);做法:贪心,如果 \(2^x\) 这一位异或下来是 \(1\),那么一定要比后面所有位都是 \(1\) 产生的贡献之和(\(2^x - 1\))还要大,所以我们从高位往低位贪心肯定是最优的,时间复杂度 \(O(\log w)\)。

线性基 xor 值计数

因为线性基里的数都是线性无关的,所以任意一个子集(不含 \(0\))xor 出来的值都互不相同,如果含 \(0\) 总共就是 \(2^{cnt}\) 种情况,其中 \(cnt\) 是基中非 \(0\) 的数的数量。

线性基合并

直接将一个线性基里的数暴力插入到另一个线性基里即可,时间复杂度 \(O(\log^2 w)\)。

标签:cnt,xor,int,void,笔记,学习,bs,线性
From: https://www.cnblogs.com/RB16B/p/17632205.html

相关文章

  • 一文预览 | 8 月 16 日 NVIDIA 在 WAVE SUMMIT深度学习开发者大会 2023精彩亮点抢先看
    由深度学习技术及应用国家工程研究中心主办,百度飞桨和文心大模型承办的WAVESUMMIT深度学习开发者大会2023,将于8月16日在北京与大家见面。NVIDIA作为技术合作伙伴,将携手百度飞桨参与这场技术盛会。在这次大会中,NVIDIA与飞桨共规划了四大活动亮点,包括NVIDIA人工智能工作坊—......
  • 《深入理解Java虚拟机》读书笔记:Class类文件的结构
    Class类文件的结构 Sun公司以及其他虚拟机提供商发布了许多可以运行在各种不同平台上的虚拟机,这些虚拟机都可以载入和执行同一种平台无关的的程序存储格式——字节码(ByteCode),从而实现了程序的......
  • openGauss学习笔记-40 openGauss 高级数据管理-锁
    openGauss学习笔记-40openGauss高级数据管理-锁如果需要保持数据库数据的一致性,可以使用LOCKTABLE来阻止其他用户修改表。例如,一个应用需要保证表中的数据在事务的运行过程中不被修改。为实现这个目的,则可以对表使用进行锁定。这样将防止数据不被并发修改。LOCKTABLE只在一......
  • 软件测试|深入学习 Docker Logs
    简介Docker是一种流行的容器化技术,它能够帮助用户将应用程序及其依赖项打包成一个可移植的容器。Dockerlogs是Docker提供的用于管理容器日志的命令,本文将深入学习Dockerlogs的使用和管理,帮助用户更好地监测和解决容器问题。DockerLogs命令dockerlogs命令是Docker的日......
  • C语言指针初级学习笔记
    目的在于了解指针的基本概念和一些用法下面是本阶段导图:基本概念inta=10;int*p=&a;指针就是地址,p为指针变量,存放地址的一个最小的内存单元为一字节32位机器指针所占内存4字节64位机器指针所占内存8字节指针类型1.指针决定访问指针类型决定了指针解引用访问的字节大小int*......
  • anaconda迁移深度学习虚拟环境 &在云服务器上配置
    1anaconda虚拟环境操作1、查看虚拟环境condainfo-e2、创建新的虚拟环境condacreate-ndeeplearning_allpippython=3.63、激活新建的虚拟环境Condaactivatedeeplearning_all2环境中相关库的版本即安装说明(这些库都是对应匹配的)pipinstallnumpy==1.16.0-ihttps://......
  • C学习4
    1、二分查找(折半查找)#include<stdio.h>intmain(){intarr[]={1,2,3,4,5,6,7,8,9,10};intleft=0;intsz=sizeof(arr)/sizeof(arr[0]);intright=sz-1;intk;printf("请输入要查找的数字:");scanf_s("%d",&am......
  • SpringBoot3 学习笔记 (整合Druid)
    一、Druid Github地址:https://github.com/alibaba/druid/二、配置数据源1、在https://mvnrepository.com/artifact/com.alibaba/druid上找最新的版本 2、在pom.xml中添加上Druid数据源依赖<!--https://mvnrepository.com/artifact/com.alibaba/druid--><dependency......
  • 记录学习day1
    今天在boss上统计了一下.net初级开发技能要求接下来就按照这个学习路线来进行了,随机找了南宁的5家公司下面是要求  前端技术:JavaScript(6)vueAjax(4)bootstrap(2)jquery(2)UniappknokoutJS(不如vue)前端库:jquery-easyuielem后端:webapi(4)ASP.NETMVC(3)多......
  • SpringBoot3 学习笔记 (整合Mybatis-plus)
    1、引入依赖,网址:https://mvnrepository.com/artifact/com.baomidou 找到mybatis-plus-boot-starter这里最新版本为3.5.3.2,点击进去2、在pom.xml中添加依赖,并确认依赖中已经有了mysql-connector-j的依赖<!--https://mvnrepository.com/artifact/com.baomidou/mybatis-pl......