[关闭]
@KirinBill 2018-02-27T23:43:37.000000Z 字数 18443 阅读 1048

线性基学习笔记

线性代数

目录


数学知识

向量空间(Wikipedia

向量空间是线性代数研究的基本对象,可以简单的认为是在高中就是直角坐标系里的所有向量组成的集合。其实我们可以很多其它集合也看做向量,同时定义一下向量加法和标量乘法,就可以通过基向量的运算来表示出其它所有向量,这也是一个向量空间了。
定义为向量空间,其中为域(中元素的范围,大概类似于定义域),为集合,中的元素称为向量,向量加法,标量乘法。并且要求运算满足条公理(见维基百科)。


线性相关与线性无关(Wikipedia

对于向量空间中的一个向量组,若存在不全为的一组数,使得,则称这个向量组线性相关,否则称为线性无关
线性相关有些地方就类似与高中数学的两个向量共线。


线性组合(Wikipedia

对于向量空间中的一个向量组,一组数,和一个新向量,称是向量组的一个线性组合,而且必然有
之所以叫线性组合,是因为如果将这个向量空间以直角坐标系的形式呈现,那么向量仍是直的,也就是说线性组合的运算不会弯曲向量。

性质:一组向量线性无关其中不存在一个向量是该组的其它向量的一个线性组合


张成

对于向量空间中的一个向量组,其所有线性组合构成的集合称为其张成,记做
例子:高中数学中,平面的一个向量基底,其张成就是整个平面的所有向量,其张成空间就是整个平面,因为平面上的所有向量都可以用它们的线性组合表示(即写成的形式)。


基(Wikipedia

若向量空间中的一个向量组即可张成出,又是线性无关的,则称其为的一个基,为该向量空间的维数。

性质:

  1. 是能张成的极小集合,其任何真子集都不能张成出
  2. 是该向量空间中线性无关的极大集合,该向量空间中不存在其它线性无关的向量集合使是其真子集;
  3. 中的每一个向量都可以用中的一个唯一的线性组合表示。

第三点感性的证明就是如果存在不唯一的方案,那么一定说明中有一个向量可以通过其它向量的线性组合表示,与定义矛盾。
总之,基向量就类似于高中数学用的基底,我们可以用它来代表一个向量空间,从而“减小”向量空间的大小。


线性相关性引理


线性基

定义


算法

Sengxian巨佬那里偷来的例子:

一开始矩阵是这样的:


加入,矩阵变为:

加入,添加到最后一行,同时为了维护对角矩阵,消去第一行的最低位,矩阵变为:

加入,由于第一行已经有数了,它被异或为 ,加入第二行,同时为了维护对角矩阵,消去第一行的第二位,矩阵变为:

剩下的数都加不上了。

代码:

  1. class LinearB{
  2. private:
  3. long long c[MAXDIM];
  4. void ist(long long x){
  5. for(int i=MAXDIM-1;i>=0;--i){
  6. if(~x>>i&1) continue;
  7. if(c[i]) x^=c[i];
  8. else{
  9. c[i]=x;
  10. for(int j=i-1;j>=0;--j){
  11. if(c[i]>>j&1) c[i]^=c[j];
  12. }
  13. for(int j=i+1;j<MAXDIM;++j){
  14. if(c[j]>>i&1) c[j]^=c[i];
  15. }
  16. break;
  17. }
  18. }
  19. }
  20. public:
  21. void init(long long a[],int n){
  22. for(int i=1;i<=n;++i)
  23. ist(a[i]);
  24. }
  25. };

练习

1.[LOJ 113] 最大异或和

代码:

  1. #include <cstdio>
  2. const int MAXN=55,MAXDIM=55;
  3. long long a[MAXN];
  4. class LinearB{
  5. private:
  6. long long c[MAXDIM];
  7. void ist(long long x){
  8. for(int i=MAXDIM-1;i>=0;--i){
  9. if(~x>>i&1) continue;
  10. if(c[i]) x^=c[i];
  11. else{
  12. c[i]=x;
  13. for(int j=i-1;j>=0;--j){
  14. if(c[i]>>j&1) c[i]^=c[j];
  15. }
  16. for(int j=i+1;j<MAXDIM;++j){
  17. if(c[j]>>i&1) c[j]^=c[i];
  18. }
  19. break;
  20. }
  21. }
  22. }
  23. public:
  24. void init(long long a[],int n){
  25. for(int i=1;i<=n;++i)
  26. ist(a[i]);
  27. }
  28. long long qry_max(){
  29. long long ret=0;
  30. for(int i=0;i<MAXDIM;++i)
  31. ret^=c[i];
  32. return ret;
  33. }
  34. }lb;
  35. int main(){
  36. int n;
  37. scanf("%d",&n);
  38. for(int i=1;i<=n;++i)
  39. scanf("%lld",&a[i]);
  40. lb.init(a,n);
  41. printf("%lld",lb.qry_max());
  42. return 0;
  43. }

2.[LOJ 114] k大异或和

代码:

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. using std::sort;
  5. using std::vector;
  6. const int MAXN=1e5+5,MAXDIM=55;
  7. long long a[MAXN];
  8. class LinearB{
  9. private:
  10. long long span_sz;
  11. bool has_zero;
  12. long long c[MAXDIM];
  13. vector<long long> vec;
  14. void ist(long long x){
  15. for(int i=MAXDIM-1;i>=0;--i){
  16. if(~x>>i&1) continue;
  17. if(c[i]) x^=c[i];
  18. else{
  19. c[i]=x;
  20. for(int j=i-1;j>=0;--j){
  21. if(c[i]>>j&1) c[i]^=c[j];
  22. }
  23. for(int j=i+1;j<MAXDIM;++j){
  24. if(c[j]>>i&1) c[j]^=c[i];
  25. }
  26. break;
  27. }
  28. }
  29. }
  30. public:
  31. void init(long long a[],int n){
  32. for(int i=1;i<=n;++i)
  33. ist(a[i]);
  34. for(int i=0;i<MAXDIM;++i){
  35. if(c[i]) vec.push_back(c[i]);
  36. }
  37. // long long !!!
  38. span_sz=(1LL<<vec.size())-1;
  39. if(n>vec.size()) has_zero=true;
  40. sort(vec.begin(),vec.end());
  41. }
  42. long long kth_val(long long k){
  43. if(has_zero) --k;
  44. if(k>span_sz) return -1;
  45. long long ret=0;
  46. for(int i=0;i<vec.size();++i){
  47. if(k>>i&1) ret^=vec[i];
  48. }
  49. return ret;
  50. }
  51. }lb;
  52. int main(){
  53. int n;
  54. scanf("%d",&n);
  55. for(int i=1;i<=n;++i)
  56. scanf("%lld",&a[i]);
  57. lb.init(a,n);
  58. int m;
  59. scanf("%d",&m);
  60. long long k;
  61. for(int i=1;i<=m;++i){
  62. scanf("%lld",&k);
  63. printf("%lld\n",lb.kth_val(k));
  64. }
  65. return 0;
  66. }

3.[BZOJ 4269] 再见Xor

代码:

  1. #include <cstdio>
  2. const int MAXN=100005,MAXDIM=32;
  3. int n;
  4. int a[MAXN];
  5. class LinearB{
  6. private:
  7. int c[MAXDIM];
  8. void ist(int x){
  9. for(int i=MAXDIM-1;i>=0;--i){
  10. if(~x>>i&1) continue;
  11. if(c[i]) x^=c[i];
  12. else{
  13. c[i]=x;
  14. for(int j=i-1;j>=0;--j){
  15. if(c[i]>>j&1) c[i]^=c[j];
  16. }
  17. for(int j=i+1;j<MAXDIM;++j){
  18. if(c[j]>>i&1) c[j]^=c[i];
  19. }
  20. break;
  21. }
  22. }
  23. }
  24. public:
  25. void init(int a[],int n){
  26. for(int i=1;i<=n;++i)
  27. ist(a[i]);
  28. }
  29. int qry_max(){
  30. int ret=0;
  31. for(int i=0;i<MAXDIM;++i)
  32. ret^=c[i];
  33. return ret;
  34. }
  35. int lb_min(){
  36. for(int i=0;i<MAXDIM;++i){
  37. if(c[i]) return c[i];
  38. }
  39. }
  40. }lb;
  41. int main(){
  42. scanf("%d",&n);
  43. for(int i=1;i<=n;++i)
  44. scanf("%d",&a[i]);
  45. lb.init(a,n);
  46. int max=lb.qry_max();
  47. printf("%d %d",max,max^lb.lb_min());
  48. return 0;
  49. }

4.[BJOI 2011] 元素

代码:

  1. #include <cstdio>
  2. #include <algorithm>
  3. using std::sort;
  4. const int MAXN=1005,MAXDIM=60;
  5. int n;
  6. struct data{
  7. int val;
  8. long long id;
  9. static bool cmp_val(const data &a,const data &b){
  10. return a.val>b.val;
  11. }
  12. }w[MAXN];
  13. class LinearB{
  14. private:
  15. long long c[MAXDIM];
  16. public:
  17. bool ist(long long x){
  18. for(int i=MAXDIM-1;i>=0;--i){
  19. if(~x>>i&1) continue;
  20. if(c[i]) x^=c[i];
  21. else{
  22. c[i]=x;
  23. for(int j=i-1;j>=0;--j){
  24. if(c[i]>>j&1) c[i]^=c[j];
  25. }
  26. for(int j=i+1;j<MAXDIM;++j){
  27. if(c[j]>>i&1) c[j]^=c[i];
  28. }
  29. return true;
  30. }
  31. }
  32. return false;
  33. }
  34. };
  35. inline int greedy(){
  36. static LinearB lb;
  37. sort(w+1,w+n+1,data::cmp_val);
  38. int ret=0;
  39. for(int i=1;i<=n;++i){
  40. if(lb.ist(w[i].id))
  41. ret+=w[i].val;
  42. }
  43. return ret;
  44. }
  45. int main(){
  46. scanf("%d",&n);
  47. for(int i=1;i<=n;++i)
  48. scanf("%lld%d",&w[i].id,&w[i].val);
  49. printf("%d",greedy());
  50. return 0;
  51. }

5.[WC 2011] Xor

代码:

  1. #include <cstdio>
  2. #include <vector>
  3. using std::vector;
  4. const int MAXN=50005,MAXM=100005,MAXDIM=60;
  5. int he[MAXN];
  6. long long dis[MAXN];
  7. vector<long long> cir;
  8. struct line{
  9. int to,nex;
  10. long long w;
  11. }ed[MAXM<<1];
  12. class LinearB{
  13. private:
  14. long long c[MAXDIM];
  15. void ist(long long x){
  16. for(int i=MAXDIM-1;i>=0;--i){
  17. if(~x>>i&1) continue;
  18. if(c[i]) x^=c[i];
  19. else{
  20. c[i]=x;
  21. for(int j=i-1;j>=0;--j){
  22. if(c[i]>>j&1) c[i]^=c[j];
  23. }
  24. for(int j=i+1;j<MAXDIM;++j){
  25. if(c[j]>>i&1) c[j]^=c[i];
  26. }
  27. break;
  28. }
  29. }
  30. }
  31. public:
  32. void init(vector<long long> &a){
  33. for(int i=0;i<a.size();++i)
  34. ist(a[i]);
  35. }
  36. long long qry_max(long long x){
  37. for(int i=MAXDIM-1;i>=0;--i){
  38. if(~x>>i&1) x^=c[i];
  39. }
  40. return x;
  41. }
  42. }lb;
  43. inline void addE(int u,int v,long long w){
  44. static int cnt;
  45. ed[++cnt]=(line){v,he[u],w};
  46. he[u]=cnt;
  47. }
  48. void DFS(int u,int fa){
  49. static bool vis[MAXN];
  50. vis[u]=true;
  51. for(int i=he[u],v;i;i=ed[i].nex){
  52. v=ed[i].to;
  53. if(v==fa) continue;
  54. if(!vis[v]){
  55. dis[v]=dis[u]^ed[i].w;
  56. DFS(v,u);
  57. }
  58. else cir.push_back(dis[u]^dis[v]^ed[i].w);
  59. }
  60. }
  61. int main(){
  62. int n,m;
  63. scanf("%d%d",&n,&m);
  64. long long w;
  65. for(int i=1,u,v;i<=m;++i){
  66. scanf("%d%d%lld",&u,&v,&w);
  67. addE(u,v,w),addE(v,u,w);
  68. }
  69. DFS(1,0);
  70. lb.init(cir);
  71. printf("%lld",lb.qry_max(dis[n]));
  72. return 0;
  73. }

6.[SCOI 2016] 幸运数字

代码:

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <cmath>
  5. using std::swap;
  6. const int MAXN=20005,MAXDIM=61,MAXLOG=15;
  7. int n;
  8. int he[MAXN],de[MAXN],anc[MAXN][MAXLOG];
  9. long long w[MAXN];
  10. struct line{int to,nex;}ed[MAXN<<1];
  11. class LinearB{
  12. public:
  13. long long c[MAXDIM];
  14. void ist(long long x){
  15. for(int i=MAXDIM-1;i>=0;--i){
  16. if(~x>>i&1) continue;
  17. if(c[i]) x^=c[i];
  18. else{
  19. c[i]=x;
  20. for(int j=i-1;j>=0;--j){
  21. if(c[i]>>j&1) c[i]^=c[j];
  22. }
  23. for(int j=i+1;j<MAXDIM;++j){
  24. if(c[j]>>i&1) c[j]^=c[i];
  25. }
  26. break;
  27. }
  28. }
  29. }
  30. LinearB(){memset(c,0,sizeof(c));}
  31. LinearB& operator +=(const LinearB &that){
  32. for(int i=0;i<MAXDIM;++i){
  33. if(that.c[i]) ist(that.c[i]);
  34. }
  35. return *this;
  36. }
  37. LinearB operator +(const LinearB &that)const{
  38. LinearB ret=*this;
  39. ret+=that;
  40. return ret;
  41. }
  42. long long qry_max(){
  43. long long ret=0;
  44. for(int i=0;i<MAXDIM;++i)
  45. ret^=c[i];
  46. return ret;
  47. }
  48. }lb[MAXN][MAXLOG];
  49. inline void addE(int u,int v){
  50. static int cnt;
  51. ed[++cnt]=(line){v,he[u]};
  52. he[u]=cnt;
  53. }
  54. void DFS(int u){
  55. de[u]=de[anc[u][0]]+1;
  56. lb[u][0].ist(w[u]);
  57. lb[u][0].ist(w[anc[u][0]]);
  58. for(int i=1,lim=log2(de[u]);i<=lim;++i){
  59. anc[u][i]=anc[anc[u][i-1]][i-1];
  60. lb[u][i]=lb[u][i-1]+lb[anc[u][i-1]][i-1];
  61. }
  62. for(int i=he[u],v;i;i=ed[i].nex){
  63. v=ed[i].to;
  64. if(v!=anc[u][0]){
  65. anc[v][0]=u;
  66. DFS(v);
  67. }
  68. }
  69. }
  70. inline long long dbl_jump(int u,int v){
  71. if(u==v) return w[u];
  72. if(de[u]<de[v]) swap(u,v);
  73. LinearB ret;
  74. for(int d=de[u]-de[v],i=0;d;++i,d>>=1){
  75. if(d&1){
  76. ret+=lb[u][i];
  77. u=anc[u][i];
  78. }
  79. }
  80. if(u==v) return ret.qry_max();
  81. for(int i=MAXLOG-1;i>=0;--i){
  82. if(anc[u][i]!=anc[v][i]){
  83. ret+=lb[u][i]+lb[v][i];
  84. u=anc[u][i],v=anc[v][i];
  85. }
  86. }
  87. ret+=lb[u][0]+lb[v][0];
  88. return ret.qry_max();
  89. }
  90. int main(){
  91. int q;
  92. scanf("%d%d",&n,&q);
  93. for(int i=1;i<=n;++i)
  94. scanf("%lld",&w[i]);
  95. for(int i=1,u,v;i<n;++i){
  96. scanf("%d%d",&u,&v);
  97. addE(u,v),addE(v,u);
  98. }
  99. DFS(1);
  100. for(int i=1,u,v;i<=q;++i){
  101. scanf("%d%d",&u,&v);
  102. printf("%lld\n",dbl_jump(u,v));
  103. }
  104. return 0;
  105. }

7.[BJOI 2011] 梦想封印

代码:

  1. #include <cstdio>
  2. #include <set>
  3. using std::set;
  4. const int MAXN=5005,MAXM=20005,MAXQ=MAXM,MAXDIM=60;
  5. int he[MAXN],del_id[MAXQ];
  6. long long dis[MAXN],ans[MAXQ];
  7. bool vis[MAXN],del[MAXM];
  8. set<long long> se;
  9. struct graph{
  10. int u,v;
  11. long long w;
  12. }G[MAXM];
  13. struct line{
  14. int to,nex;
  15. long long w;
  16. }ed[MAXM<<1];
  17. class LinearB{
  18. private:
  19. int sz;
  20. long long c[MAXDIM];
  21. void upd_attrib(){
  22. static long long tmp[MAXN];
  23. tmp[0]=0;
  24. for(set<long long>::iterator iter=se.begin();iter!=se.end();++iter)
  25. tmp[++tmp[0]]=*iter;
  26. se.clear();
  27. for(int i=1;i<=tmp[0];++i)
  28. se.insert(attrib(tmp[i]));
  29. }
  30. public:
  31. void ist(long long x){
  32. for(int i=MAXDIM-1;i>=0;--i){
  33. if(~x>>i&1) continue;
  34. if(c[i]) x^=c[i];
  35. else{
  36. ++sz;
  37. c[i]=x;
  38. for(int j=i-1;j>=0;--j){
  39. if(c[i]>>j&1) c[i]^=c[j];
  40. }
  41. for(int j=i+1;j<MAXDIM;++j){
  42. if(c[j]>>i&1) c[j]^=c[i];
  43. }
  44. upd_attrib();
  45. break;
  46. }
  47. }
  48. }
  49. long long attrib(long long x){
  50. for(int i=MAXDIM-1;i>=0;--i){
  51. if(x>>i&1) x^=c[i];
  52. }
  53. return x;
  54. }
  55. int size(){return sz;}
  56. }lb;
  57. inline void addE(int u,int v,long long w){
  58. static int cnt;
  59. ed[++cnt]=(line){v,he[u],w};
  60. he[u]=cnt;
  61. }
  62. void DFS(int u,int fa,long long dis){
  63. vis[u]=true;
  64. ::dis[u]=dis;
  65. se.insert(lb.attrib(dis));
  66. for(int i=he[u],v;i;i=ed[i].nex){
  67. v=ed[i].to;
  68. if(v==fa) continue;
  69. if(!vis[v]) DFS(v,u,dis^ed[i].w);
  70. else lb.ist(::dis[u]^::dis[v]^ed[i].w);
  71. }
  72. }
  73. inline void addE(graph &e){
  74. if(vis[e.u] && vis[e.v])
  75. lb.ist(dis[e.u]^dis[e.v]^e.w);
  76. else{
  77. addE(e.u,e.v,e.w),addE(e.v,e.u,e.w);
  78. if(vis[e.u]) DFS(e.v,e.u,dis[e.u]^e.w);
  79. else if(vis[e.v]) DFS(e.u,e.v,dis[e.v]^e.w);
  80. }
  81. }
  82. inline long long cal(){return se.size()*(1LL<<lb.size())-1;}
  83. int main(){
  84. int n,m,q;
  85. scanf("%d%d%d",&n,&m,&q);
  86. for(int i=1;i<=m;++i)
  87. scanf("%d%d%lld",&G[i].u,&G[i].v,&G[i].w);
  88. for(int i=1;i<=q;++i){
  89. scanf("%d",&del_id[i]);
  90. del[del_id[i]]=true;
  91. }
  92. for(int i=1;i<=m;++i){
  93. if(!del[i]) addE(G[i]);
  94. }
  95. DFS(1,0,0);
  96. ans[++q]=cal();
  97. for(int i=q-1;i;--i){
  98. addE(G[del_id[i]]);
  99. ans[i]=cal();
  100. }
  101. for(int i=1;i<=q;++i)
  102. printf("%lld\n",ans[i]);
  103. return 0;
  104. }

8.[BZOJ 2844] albus就是要第一个出场

代码:

  1. #include <cstdio>
  2. #include <vector>
  3. using std::vector;
  4. const int MAXN=100005,MAXDIM=31,P=10086;
  5. int a[MAXN];
  6. class LinearB{
  7. private:
  8. int c[MAXDIM];
  9. vector<int> vec;
  10. void ist(int x){
  11. for(int i=MAXDIM-1;i>=0;--i){
  12. if(~x>>i&1) continue;
  13. if(c[i]) x^=c[i];
  14. else{
  15. c[i]=x;
  16. for(int j=i-1;j>=0;--j){
  17. if(c[i]>>j&1) c[i]^=c[j];
  18. }
  19. for(int j=i+1;j<MAXDIM;++j){
  20. if(c[j]>>i&1) c[j]^=c[i];
  21. }
  22. break;
  23. }
  24. }
  25. }
  26. public:
  27. int size(){return vec.size();}
  28. void init(int a[],int n){
  29. for(int i=1;i<=n;++i)
  30. ist(a[i]);
  31. for(int i=0;i<MAXDIM;++i){
  32. if(c[i]) vec.push_back(i);
  33. }
  34. }
  35. int get_rk(int x){
  36. int ret=0;
  37. for(int i=0;i<vec.size();++i){
  38. if(x>>vec[i]&1) ret+=1<<i;
  39. }
  40. ++ret; //线性基全不选的情况
  41. return ret;
  42. }
  43. }lb;
  44. int pow(int x,int y){
  45. int ret=1;
  46. for(;y;x=(long long)x*x%P,y>>=1){
  47. if(y&1) ret=(long long)ret*x%P;
  48. }
  49. return ret;
  50. }
  51. int main(){
  52. int n;
  53. scanf("%d",&n);
  54. for(int i=1;i<=n;++i)
  55. scanf("%d",&a[i]);
  56. lb.init(a,n);
  57. int q;
  58. scanf("%d",&q);
  59. printf("%d",((long long)(lb.get_rk(q)%P-1+P)%P*pow(2,n-lb.size())%P+1)%P);
  60. return 0;
  61. }

9.[清华集训 2014] 玛里苟斯

代码:

  1. #include <cstdio>
  2. #include <vector>
  3. using std::vector;
  4. const int MAXN=100005;
  5. int n,K;
  6. unsigned long long a[MAXN];
  7. inline void solve1(){
  8. unsigned long long ret=0;
  9. for(int i=1;i<=n;++i)
  10. ret|=a[i];
  11. printf("%llu",ret>>1);
  12. if(ret&1) printf(".5");
  13. }
  14. inline void solve2(){
  15. int tmp=0;
  16. unsigned long long ret=0;
  17. bool flag;
  18. for(int i=0;i<32;++i){
  19. flag=false;
  20. for(int j=1;j<=n;++j){
  21. if(a[j]>>i&1){
  22. flag=true;
  23. break;
  24. }
  25. }
  26. if(!flag) continue;
  27. for(int j=0;j<32;++j){
  28. flag=false;
  29. for(int k=1;k<=n;++k){
  30. if(a[k]>>j&1){
  31. flag=true;
  32. break;
  33. }
  34. }
  35. if(!flag) continue;
  36. flag=false;
  37. for(int k=1;k<=n;++k){
  38. if((a[k]>>i&1)!=(a[k]>>j&1)){
  39. flag=true;
  40. break;
  41. }
  42. }
  43. //tmp是目前除不了的贡献,记到一起最后除
  44. //单位是1/2,对于i=j=0时才可能为-2,但此时flag比为false,不存在,所以这里只有÷2的情况
  45. if(i+j-1-flag<0) ++tmp;
  46. else ret+=1LL<<i+j-1-flag; //除过了(左移位数-1-flag)
  47. }
  48. }
  49. ret+=tmp>>1;
  50. printf("%llu",ret);
  51. if(tmp&1) printf(".5");
  52. }
  53. inline void solve3(){
  54. static int lb[22];
  55. static vector<int> vec;
  56. for(int i=1;i<=n;++i){
  57. for(int j=21;j>=0;--j){
  58. if(~a[i]>>j&1) continue;
  59. if(lb[j]) a[i]^=lb[j];
  60. else{
  61. lb[j]=a[i];
  62. for(int k=j-1;k>=0;--k){
  63. if(lb[j]>>k&1) lb[j]^=lb[k];
  64. }
  65. for(int k=j+1;k<22;++k){
  66. if(lb[k]>>j&1) lb[k]^=lb[j];
  67. }
  68. break;
  69. }
  70. }
  71. }
  72. for(int i=0;i<22;++i){
  73. if(lb[i]) vec.push_back(lb[i]);
  74. }
  75. long long ret1=0,ret2=0,tmp1,tmp2;
  76. for(int i=0,tmp,lim=1<<vec.size();i<lim;++i){
  77. tmp=0;
  78. for(int j=0;j<vec.size();++j){
  79. if(i>>j&1) tmp^=vec[j];
  80. }
  81. tmp1=0,tmp2=1;
  82. for(int j=1;j<=K;++j){
  83. tmp1*=tmp,tmp2*=tmp;
  84. tmp1+=tmp2>>vec.size();
  85. tmp2&=lim-1;
  86. }
  87. ret1+=tmp1,ret2+=tmp2;
  88. ret1+=ret2>>vec.size();
  89. ret2&=lim-1;
  90. }
  91. printf("%lld",ret1);
  92. if(ret2) printf(".5");
  93. }
  94. int main(){
  95. scanf("%d%d",&n,&K);
  96. for(int i=1;i<=n;++i)
  97. scanf("%llu",&a[i]);
  98. if(K==1) solve1();
  99. else if(K==2) solve2();
  100. else solve3();
  101. return 0;
  102. }

动态删除

1.[HAOI 2017] 八纵八横

代码:

  1. #include <iostream>
  2. #include <bitset>
  3. #include <algorithm>
  4. #include <vector>
  5. using std::cin;
  6. using std::cout;
  7. using std::ios;
  8. using std::bitset;
  9. using std::swap;
  10. using std::vector;
  11. const int MAXN=505,MAXM=505,MAXP=1005,MAXBIT=1005,MAXDIM=MAXBIT;
  12. int n,m,p;
  13. int he[MAXN],opt_st[MAXP];
  14. bitset<MAXBIT> dis[MAXN],ans[MAXP];
  15. struct graph{
  16. int u,v;
  17. bitset<MAXBIT> w;
  18. }G[MAXM],opt[MAXP];
  19. vector<graph> nTreeE;
  20. struct line{
  21. int to,nex;
  22. bitset<MAXBIT> w;
  23. }ed[MAXN<<1];
  24. class UFS{
  25. private:
  26. int fa[MAXN],dist[MAXN];
  27. public:
  28. void init(int n){
  29. for(int i=1;i<=n;++i)
  30. fa[i]=i,dist[i]=1;
  31. }
  32. int find(int x){
  33. if(x==fa[x]) return x;
  34. fa[x]=find(fa[x]);
  35. return fa[x];
  36. }
  37. void uni(int x,int y){
  38. if(dist[x]<dist[y]) swap(dist[x],dist[y]);
  39. fa[y]=x,dist[x]+=(dist[y]==dist[x]);
  40. }
  41. };
  42. class LinearB{
  43. private:
  44. bitset<MAXBIT> c[MAXDIM];
  45. public:
  46. void ist(bitset<MAXBIT> &x){
  47. for(int i=MAXDIM-1;i>=0;--i){
  48. if(x[i]==0) continue;
  49. if(c[i][i]) x^=c[i];
  50. else{
  51. c[i]=x;
  52. for(int j=i-1;j>=0;--j){
  53. if(c[i][j]) c[i]^=c[j];
  54. }
  55. for(int j=i+1;j<MAXDIM;++j){
  56. if(c[j][i]) c[j]^=c[i];
  57. }
  58. break;
  59. }
  60. }
  61. }
  62. bitset<MAXBIT> qry_max(){
  63. bitset<MAXBIT> ret;
  64. for(int i=0;i<MAXDIM;++i)
  65. ret^=c[i];
  66. return ret;
  67. }
  68. };
  69. class segT{
  70. #define ls (u<<1)
  71. #define rs (ls|1)
  72. private:
  73. vector<bitset<MAXBIT> > vec[MAXP<<2];
  74. void ist(int u,int l,int r,int lp,int rp,bitset<MAXBIT> &x){
  75. if(lp<=l && r<=rp){
  76. vec[u].push_back(x);
  77. return;
  78. }
  79. int mid=l+r>>1;
  80. if(lp<=mid) ist(ls,l,mid,lp,rp,x);
  81. if(rp>mid) ist(rs,mid+1,r,lp,rp,x);
  82. }
  83. void DC(int u,int l,int r,LinearB lb,bitset<MAXBIT> ans[]){
  84. for(int i=0;i<vec[u].size();++i)
  85. lb.ist(vec[u][i]);
  86. if(l==r){
  87. ans[l]=lb.qry_max();
  88. return;
  89. }
  90. int mid=l+r>>1;
  91. DC(ls,l,mid,lb,ans);
  92. DC(rs,mid+1,r,lb,ans);
  93. }
  94. public:
  95. void ist(int l,int r,bitset<MAXBIT> x){ist(1,0,p,l,r,x);}
  96. void DC(bitset<MAXBIT> ans[]){
  97. LinearB lb;
  98. DC(1,0,p,lb,ans);
  99. }
  100. #undef ls
  101. #undef rs
  102. }T;
  103. inline void out_bitset(bitset<MAXBIT> &x){
  104. int cur;
  105. for(cur=MAXBIT-1;cur;--cur){
  106. if(x[cur]) break;
  107. }
  108. for(;cur>=0;--cur) cout<<x[cur];
  109. }
  110. inline void addE(int u,int v,bitset<MAXBIT> &w){
  111. static int cnt;
  112. ed[++cnt]=(line){v,he[u],w};
  113. he[u]=cnt;
  114. }
  115. inline void spanT(){
  116. static UFS ufs;
  117. ufs.init(n);
  118. for(int i=1,u,v,ufa,vfa;i<=m;++i){
  119. u=G[i].u,v=G[i].v;
  120. ufa=ufs.find(u),vfa=ufs.find(v);
  121. if(ufa!=vfa){
  122. ufs.uni(ufa,vfa);
  123. addE(u,v,G[i].w),addE(v,u,G[i].w);
  124. }
  125. else nTreeE.push_back(G[i]);
  126. }
  127. }
  128. void DFS(int u,int fa){
  129. for(int i=he[u],v;i;i=ed[i].nex){
  130. v=ed[i].to;
  131. if(v!=fa){
  132. dis[v]=dis[u]^ed[i].w;
  133. DFS(v,u);
  134. }
  135. }
  136. }
  137. inline void fast_ios(){
  138. ios::sync_with_stdio(false);
  139. cin.tie(NULL);
  140. }
  141. int main(){
  142. fast_ios();
  143. cin>>n>>m>>p;
  144. for(int i=1;i<=m;++i)
  145. cin>>G[i].u>>G[i].v>>G[i].w;
  146. spanT();
  147. DFS(1,0);
  148. for(int i=0;i<nTreeE.size();++i)
  149. T.ist(0,p,dis[nTreeE[i].u]^dis[nTreeE[i].v]^nTreeE[i].w);
  150. int k=0;
  151. char cmd[10];
  152. for(int i=1,x;i<=p;++i){
  153. cin>>cmd;
  154. //add
  155. if(cmd[1]=='d'){
  156. opt_st[++k]=i;
  157. cin>>opt[k].u>>opt[k].v>>opt[k].w;
  158. }
  159. //cancel
  160. else if(cmd[1]=='a'){
  161. cin>>x;
  162. T.ist(opt_st[x],i-1,dis[opt[x].u]^dis[opt[x].v]^opt[x].w);
  163. opt_st[x]=0;
  164. }
  165. else{
  166. cin>>x;
  167. T.ist(opt_st[x],i-1,dis[opt[x].u]^dis[opt[x].v]^opt[x].w);
  168. cin>>opt[x].w;
  169. opt_st[x]=i;
  170. }
  171. }
  172. for(int i=1;i<=k;++i){
  173. if(opt_st[i]) T.ist(opt_st[i],p,dis[opt[i].u]^dis[opt[i].v]^opt[i].w);
  174. }
  175. T.DC(ans);
  176. for(int i=0;i<=p;++i){
  177. out_bitset(ans[i]);
  178. cout<<'\n';
  179. }
  180. return 0;
  181. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注