线性基小结

学习线性基

我们在处理异或问题的时候可能会遇到某些恶心的问题,比如:

1.给定一个集合,可以让任意多个数异或,求最大/小异或和

2. 给定一个集合,可以让任意多个数异或,求第k小异或和

3. 给定一个集合,可以让任意多个数异或,求x能否被异或出来

这些问题我们可以使用线性基来解决。

何为线性基

线性基是一个集合,它的大小是log2原集合的值域,它的定义是

1.线性基中集合的数任意个数异或出来的值域集合与原数集合 完 全 一 致(除了没有0

2.线性基中任意个数异或出来都不会为0

其中设线性基有log2原集合的值域个数字,那么pi为最高位1在i位上的那个数字(取唯一)

那让我们来构造线性基吧

void insert(long long x)
{
	for (int i=50;i>=0;i--)
	{
		if (!(x>>i&1)) continue;//如果第i位是1才做
		if (!p[i]) {p[i]=x;break;}//如果未被占用则占用
		x^=p[i];//否则去掉当前这一位1,并且保证性质1.
	}
}

很短对吧,那让我们看看上面说的3个问题

实际问题

给定一个集合,可以让任意多个数异或,求最大/小异或和

最大值的话只要构造线性基然后从高位到低位如果当前这一位pi异或了以后能让ans变大就异或,因为异或高位大才是王道

#include<bits/stdc++.h>
using namespace std;
long long n,p[55];
void insert(long long x)
{
	for (int i=50;i>=0;i--)
	{
		if (!(x>>i&1)) continue;
		if (!p[i]) {p[i]=x;break;}
		x^=p[i];
	}
}
int main()
{
	scanf("%lld",&n);
	for (long long a,i=1;i<=n;i++)
	{
		scanf("%lld",&a);
		insert(a);
	}
	long long ans=0;
	for (int i=50;i>=0;i--)
	{
		if ((ans^p[i])>ans) ans^=p[i];
	}
	cout<<ans<<endl;
	return 0;	
} 

最小值,只需要从低位向高位判断如果pi!=0直接输出pi即可,注意判断可不可以异或出0,这一点你们看了第三个问题或者第二个就会明白了,代码自己写写吧,我没写。

给定一个集合,可以让任意多个数异或,求第k小异或和

需要改造一下线性基,目的是让第i位为1的元素 (即pi) 在线性基中只有他的第i位为1。 处理完后再把p数组的元素从小到大依次放进p2数组,因为最高位固定,所以直接循环放 。然后神奇的规律来了:求第k小时,只要把k二进制拆分,第i位是1就异或 b[i] ,这我也不知道什么规律,反正很好记。(貌似是因为最小数依次是p0,p1,p0^p1,p2,p2^p0,p2^p1,p2^p0^p1)这里就要有异或为0的问题了,就是0是否可以做最小值。

#include<bits/stdc++.h>
using namespace std;
long long a,dp[200],dp1[200],cnt=0,n,m,f=0;
void insert(long long x)
{
    for(int i=62;i>=0;i--)
    {
        if(x>>i&1)
        {
            if(!dp[i]){dp[i]=x;return;}
			x^=dp[i];
        }
    }
    f=1;//如果x还是没有找到空的pi,那x一定被异或成0了,说明x可以被之前的数异或出来,那么最小值就可以为0
}
void change()
{
    for(int i=0;i<=62;i++)
    {
        for(int j=i-1;j>=0;j--) if(dp[i]>>j&1) dp[i]^=dp[j];//保证只有pi的i位有1且满足性质1
        if(dp[i]) dp1[cnt++]=dp[i];
    }
}
long long kth_min(long long k)
{
    long long ans=0;
    for(int i=0;i<cnt;i++) if(k>>i&1) ans^=dp1[i];
    return ans;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    scanf("%lld",&a),insert(a);
    change();//处理
    unsigned long long tot=1LL<<cnt;//因为sigma i=[1,cnt] C(i,cnt)=2^cnt也就是异或的所有不同的(请注意不是n是cnt了)取值
    scanf("%lld",&m);
    for (int i=1;i<=m;i++)
    {
	long long k;
	scanf("%lld",&k);
	k-=f;如果能取0,那么所有排名下降一位
    	if(tot<=k) cout<<"-1"<<endl;//如果k比全部不同取值还大就不可能
    	else cout<<kth_min(k)<<endl;
	}
    return 0;
}

给定一个集合,可以让任意多个数异或,求x能否被异或出来

其实我2,3难度放反了说。。。

问题不大,相信大家看了2都知道怎么做了

bool insert(long long x)
{
    for(int i=62;i>=0;i--)
    {
        if(x>>i&1)
        {
            if(!dp[i]){dp[i]=x;return 0;}
	    x^=dp[i];
        }
    }
    return 1;//如果x还是没有找到空的pi,那x一定被异或成0了,说明x可以被之前的数异或出来
}

例题明天更(现在0:13哦)

评论

  1. bessie_goes_moo
    4年前
    2020-4-01 0:17:04

    %%%写的太好了

    • void_struct 博主
      4年前
      2020-4-01 0:18:12

      还没看就评论的屑

  2. yzxoi
    4年前
    2020-4-15 11:29:15

    %%%写的太好了

  3. yzxoi
    4年前
    2020-4-15 11:36:06

    Orz

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇