高斯消元与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

相关文章