[关闭]
@xzyxzy 2018-04-06T08:31:00.000000Z 字数 2577 阅读 611

线性基

数学

作业部落链接:https://www.zybuluo.com/xzyxzy/note/1076707


前言

网上优秀博客:https://blog.sengxian.com/algorithms/linear-basis
机房大佬们的总结 yyb%yl%zsy orz

一、理解

所谓基大概就是指
在一个集合内定义一种运算,用基中的元素可以运算出所有用集合中的元素运算的结果
可以理解成基是一个集合的。。浓缩?

然后线性基呢就是这个运算是异或运算

二、性质

线性基中以每一位为最高位的1的数至多只有一个
所以把一个元素加入线性基中,那么

  1. if(x&(1<<j))
  2. {
  3. if(!p[j]){p[j]=x;break;}//一定要break!!
  4. else x^=p[j];
  5. }

三、题目

四、应用

一个技巧

代码

最大异或和(较简单【模板】线性基

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #define ll long long
  5. using namespace std;
  6. ll read()
  7. {
  8. char ch=getchar();ll h=0,t=1;
  9. while(ch!='-'&&(ch>'9'||ch<'0'))ch=getchar();
  10. if(ch=='-')t=-1,ch=getchar();
  11. while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
  12. return h*t;
  13. }
  14. ll N,A[70],ans;
  15. int main()
  16. {
  17. N=read();
  18. for(int i=1;i<=N;i++)
  19. {
  20. ll x=read();
  21. for(int j=63;j>=0;j--)
  22. if(x&(1LL<<j))
  23. {
  24. if(!A[j]){A[j]=x;break;}
  25. else x^=A[j];
  26. }
  27. }
  28. for(int i=63;i>=0;i--)
  29. if((ans^A[i])>ans)ans^=A[i];
  30. printf("%lld\n",ans);
  31. return 0;
  32. }

K小异或和(比较难以理解,纠结了一个晚上,想通了[HDU2949] XOR

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #define ll long long
  6. using namespace std;
  7. ll read()
  8. {
  9. char ch=getchar();ll h=0,t=1;
  10. while(ch!='-'&&(ch>'9'||ch<'0'))ch=getchar();
  11. if(ch=='-')t=-1,ch=getchar();
  12. while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
  13. return h*t;
  14. }
  15. ll T,p[100],Q[100],cnt,N,M,CC=0;
  16. void Insert(ll x)
  17. {
  18. for(ll i=63;i>=0;i--)
  19. {
  20. if(!(x>>i))continue;
  21. if(!p[i]){p[i]=x;return;}
  22. else x^=p[i];
  23. }
  24. CC=1;//表示线性基可以异或出0
  25. }
  26. void Rebuild()
  27. {
  28. for(ll i=63;i>=0;i--)
  29. for(ll j=i-1;j>=0;j--)
  30. if(p[i]&(1LL<<j))
  31. p[i]^=p[j];
  32. /*
  33. 重建线性基,使得p[i]某非最高位上有1当且仅当p[该位]=0
  34. 使得能够保证异或上p[i]一定会使答案增大
  35. */
  36. for(ll i=0;i<=63;i++)
  37. if(p[i])Q[cnt++]=p[i];
  38. }
  39. void Query(ll k)
  40. {
  41. if(k>=(1LL<<cnt)){puts("-1");return;}//超过所有能够异或出来的结果个数 (线性基中cnt个元素选或者不选)
  42. ll res=0;
  43. for(ll i=cnt-1;i>=0;i--)
  44. if(k&(1LL<<i))res^=Q[i];
  45. /*
  46. 在线性基Q[0]~Q[cnt-1]中,从小到大是
  47. Q[0],Q[1],Q[1]^Q[0],Q[2],Q[2]^Q[0],Q[2]^Q[1],Q[2]^Q[0]^Q[1].....
  48. 所以第k大的组成元素就是所有k的二进制位上的数的异或和
  49. */
  50. printf("%lld\n",res);
  51. }
  52. int main()
  53. {
  54. T=read();
  55. for(ll w=1;w<=T;w++)
  56. {
  57. N=read();cnt=0;CC=0;
  58. memset(p,0,sizeof(p));
  59. memset(Q,0,sizeof(Q));
  60. for(ll i=1;i<=N;i++)Insert(read());
  61. Rebuild();
  62. M=read();
  63. printf("Case #%lld:\n",w);
  64. for(ll i=1;i<=M;i++)
  65. {
  66. ll k=read()-CC;//查询第k小异或和
  67. if(!k)puts("0");
  68. else Query(k);
  69. }
  70. }
  71. return 0;
  72. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注