高斯消元与xor方程组

时间:2021-10-02 06:15:00
for(i=;i<=n;i++)
{
for(j=i+;j<=n;j++)
if(a[j]>a[i]) swap(a[i],a[j]);
if(!a[i]) break;
for(j=;j>=;j--)
if(a[i]>>j&)
{
for(k=;k<=n;k++)
if(i!=k && (a[k]>>j&)) a[k]^=a[i];
break;
}
}

对着这个代码思(dan)考(teng)了一星期。。。

UPD:好像这两份代码干的事情一样?做完之后每一个数的最高位上只有这一个1。T_T谁能告诉我这两份代码有什么区别?各有什么用?还有为什么要这么做?

for(int i=;i<=n;i++)
for(int j=;j>=;j--)
{
if(a[i]>>(j-)&)
{
if(!lb[j]){lb[j]=a[i];break;}
else a[i]^=lb[j];
}
}

我们来证明一下,为什么消了元之后的a数组的任何一种选法对应原数组的一种选法?(SX问题,神犇请无视T_T)

假如我们有一个集合S=[x,S-{x}],那么对集合S选取的一种方案可以对应到S'=[x,{y^x|y∈{S-{x}}}]

令S-{X}=A,{y^x|y∈{S-{x}}}=B

因为假如这个方案

1)选x

i)另外选了奇数个A中的元素,那么S‘中的方案对应为  不选x,在B中选对应的元素

ii)另外选了偶数个A中的元素,那么S’中的方案对应为  选x,在B中选对应的元素

2)不选x

i)另外选了奇数个A中的元素,那么S‘中的方案对应为  选x,在B中选对应的元素

ii)另外选了偶数个A中的元素,那么S’中的方案对应为  不选x,在B中选对应的元素

所以这是一一对应的。所以我们就可以随便用某个方程取异或其它方程,选与不选还是相互独立且合法的。

(咦?我怎么想到了矩阵的初等变换?)

求大神给出简单证明T_T