XOR高斯消元 BZOJP2844 albus就是要第一个出场 albus nox战队介绍

【XOR高斯消元】【BZOJP2844】albus就是要第一个出场 albus nox战队介绍

感觉XOR高斯消元是个挺有意思的东西.
我又调了很久,纪念一下.


(顺便吐槽,最近如此糟糕的状态,高仿都会WA啊)


先讲下 HDU 3949 XOR http://acm.hdu.edu.cn/showproblem.php?pid=3949


题意是这样的.
给出A数组,共有N个数,你可以选其中一些出来XOR(至少一个数).
所以可能的XOR结果值排序后去重,问你排在第k个的结果值是多少.

解法是这样的:

定义数组的矩阵为,我们把数组中每个数用二进制表示出来的矩阵.(N行64列).

数组的集合为,数组所有可能取出任意大于一个数,互相XOR的结果值.

我们用原来A数组的N个数,类似高斯消元互相XOR成,新的A'数组.且A'具有以下性质:

1将A'从大到小排序,那么子数组A[i..n]的集合中的最大值<A[i-1]<A[i-2]..<A[1]

2A数组的集合<->A'数组的集合

具体怎么构造,先贴段代码:

#define rep(i,n) for (inti=1;i<=n;i++)#define rep2(i,l,r) for (inti=l;i<=r;i++)int Gauss(){ int m=31,cu=1; while (m--){ rep2(i,cu,n) if(a[i]>>m&1){ swap(a[i],a[cu]); rep(j,n)if(j!=cu&&a[j]>>m&1)a[j]^=a[cu]; cu++; break; } } return --cu;}

解释一下 为什么这样做+具体怎么做.首先,这是在数组的矩阵中做的.

定义,每行(数)的第一个(最高位)出现的1,为这行的代表.

如果A'的每行的代表,在数组的矩阵中的所在列,只有它这行有1(3). 显然就可以满足性质1了.【最高位决定一切,比它小的必没有最高位,那么怎么也不会XOR不出最高位】

又为了在已知A'数组的集合包含于A数组的集合的情况下【A'是由A xor来的,且x被xor多次最多只会保留一个】,尽量满足性质2. 即A'能互相xor的可能结果值要尽量多,即每行有尽量少的1【够自由,方便构造】(4).

为此. 我们从高到低位,尝试在这列中“授予"代表.
设当前第m位,为了(4),我们去找第m位有1且还没有代表的行.为了方便,程序中,没有代表的行是连续的,且为cu-n行.假设找到满足条件的第i行,把第i行变为有代表且代表为m.为了保持没有代表行连续的性质,我们将i与cu互换,cu+1.

由于m位为代表出现在cu行,那么其他所有m位为1的a[j]^=a[i].从而保证了(3).

会不会冲掉原来的代表呢?由于a[cu]的那些位已经被消成0了,所以显然不会.

然后就OK了.先再说两个可能存在的误区

1 矩阵中任意一列只有一个1. 这是错误的,反例如A={5,3} .

2 矩阵中任意一行只有一个1.这也是错误的,反例如A={3}.

其实性质一不需要这两个约束就可以满足.

鉴于性质1已经显然满足了,再说明一下为什么满足性质2.

假如,现在给第cu行授予位于第m位的代表.然后为了满足性质1大家xor了一下.

如果我们能够说明,这一步xor前与xor后所能互相xor的结果值的集合相同,那么一直推到最前面的初始序列,就可以说明满足性质2了.

xor前的可以分成三类 1)W={ Xcu 1 Ycu} 2)Q={Xi 1 Yi} 3)P={Xj 0Yj}

解释一下.Xz表示z行第m位前面的部分,Yz表示z行第m位后面的部分. 然后第一类就是cu行自己.第二类是所有第m位为1的集合,第三类是所有第m位为0的集合. (那么|W|+|Q|+|P|=n,Az=Xz1Yz)

经过这一步的xor后会变成:W'={Xcu 1 Ycu} Q'={(Xi 1 Yi)xor Acu}P'={Xj 0Yj}.

代表是从高到低位找的,且代表单独一列.所以显然有 Xcu=000..0 .Q'即={(Xi 1 (Yi xorAcu)}

显然 xor后的集合包含于xor前的集合【和前面A'属于A一个道理】.所以只需说明,任意一个xor前能产生的异或和,都能在xor后找到对应(即xor前的集合属于 xor后的集合)

对于某个异或和S,分成三类分别放一起后可以表示成S=wxor q xor p.

其中w为W中的那些放一起异或,q,p同理. 并且,由于有空集的存在w,q,p 都可以为0.

由于P=P',所以p肯定能在P'中构造出对于w,q,如果我们找到Q'中对应的,那些本来在Q中找到用来构造q的,异或起来.显然只有两种情况,得到 q'=q 或者 q'=q xor Acu.w'便可根据此调节:

若q'=q,w=0 或者 q'=q xor Acu,w=Acu.. w'=0 ;若q'=q,w=Acu 或者 q'=q xor Acu,w=0..w'=Acu.

所以就感性的说明了性质2满足.由于我表达能力有限,不懂的话,就自己试试以上的以步骤来数学归纳的证明方法吧. 还是比较容易的..

好了,构造好A',那么就很方便了:把B数组排序,再把k二进制分解.找对应有1的XOR起来就好了.

举个例子 A'={8,5,2}找第3(011(2))个 ,就是 5 xor2.而找第5(101(2))个就是 8xor2.

有了A'的两个性质. 正确性还是比较显然的.当然,在性质2的基础上,性质1也很重要!


还要提到的是,HDU这题对于0要特判【由于至少要取1个】然后对于BZOJP2844这题是反一下.由于有误区1,显然不能直接((k^A'[i])==A'[i])这样判,而是尝试xor,看看是否还比k小,小的话就xor加入.【具体看程序】但是,会不会出现某行多余的1,最终会被消掉,但是当前却因此大于了k了呢?显然不会.首先由于代表是从高到低一个个尝试找的,所以所有代表的位数,一定高于非代表(多余的1)的位.如果这个多余的1会被消掉,那么必然至少还有一个代表没加入,而代表是单独一列只有自己一个1的.即那个代表没加入,则k的那个代表这一位必然为1,且当前必然为0.这个位高于那个多余的1所在位,所以就没事啦..
但是要注意,由于这里不去重,如果消完后有Q行至少有1个1,其他N-Q行全为0.那么任意一个结果值出现 2^(N-Q)次. 所以要乘上什么的,详见程序吧. 然后就好了 恩.
code:#include<cstdio>
#include< cstdlib>
#include< cstring>
#include< algorithm>

using namespace std;

typedef unsigned long long ll;
const ll mo=10086;
int n,a[100005],Q;
#define rep(i,n) for (int i=1;i<=n;i++)
#define rep2(i,l,r) for (int i=l;i<=r;i++)
void swap(int &a,int &b){ intt=a;a=b;b=t; }
int Gauss(){
intm=31,cu=1;
while(m--){
rep2(i,cu,n) if(a[i]>>m&1){
swap(a[i],a[cu]);
rep(j,n) if(j!=cu&&a[j]>>m&1)a[j]^=a[cu];
cu++;break;
}
}
return--cu;
}
int main(){
scanf("%d",&n);
rep(i,n)scanf("%d",&a[i]);
scanf("%d",&Q);
intva=Gauss(),cu=0; ll rk=0;
rep(i,va) if((cu^a[i])<=Q)cu^=a[i],rk+=(1ll<<(va-i))%mo,rk%=mo;
rep(i,n-va)rk<<=1,rk%=mo; rk++,rk%=mo;
printf("%llun",rk);
return0;
}

  

爱华网本文地址 » http://www.aihuau.com/a/25101011/72756.html

更多阅读

bzoj2322-梦想封印xor高斯消元 bzoj大视野

这道题第一眼看上去:跟bzoj2115那道xor高斯消元好像啊。复习了一遍那道题,然后还是不会做==于是各种无节操膜拜题解标程。这里确实是用到了2115的一些思想,那题做法:http://blog.sina.com.cn/s/blog_6e63f59e0101bklw.html那道题求的是x

高斯·奥特曼 艾斯奥特曼

编辑词条高斯·奥特曼目录出演播放日期剧情简介高斯·奥特曼形象解说特摄电视剧与电影资料剧集目录  高斯奥特曼  -日文原名: ウルトラマンコスモス  -英文名: ULTRAMAN COSMO

转 OpenCV编程案例:混合高斯模型CvGaussBGModel 使用案例

下面程序是使用混合高斯建模方法对目前进行检测的程序。运行时,需要传递视频文件的路径参数,或者连接摄像机,否则出错。selected from:http://www.opencv.org.cn/index.php/高斯背景建模http://baike.baidu.com/view/2663975.htm代码如

科学家的故事:数学王子高斯

http://www.youban.com/media-2829-6399.html高斯 1777年4月30日生于德国不伦瑞克;1855年2月23日卒于格丁根。他是近代数学奠基者之一,有“数学王子”之称。 高斯小时候,就很喜欢数学。有一天,高斯的父亲正在结算几个工人的工资,算

正十七边形的画法_danning428 高斯正十七边形画法

最早的十七边形画法创造人为高斯.高斯(1777~1855年),德国数学家、物理学家和天文学家.在童年时代就表现出非凡的数学天才.三岁学会算术,八岁因发现等差数列求和公式而深得老师和同学的钦佩.1799年以代数基本定理的四个漂亮证明获得

声明:《XOR高斯消元 BZOJP2844 albus就是要第一个出场 albus nox战队介绍》为网友瘋爺分享!如侵犯到您的合法权益请联系我们删除