线性基求交(2019牛客国庆集训派对day4)

摘要:
想法:在线性基相交之后,有几个基是2^的幂。

题意:https://ac.nowcoder.com/acm/contest/1109/C

问你有几个x满足A,B集合都能XOR出x。

思路:

就是线性基求交后,有几个基就是2^几次方。

  1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);
  2 #include <cstdio>//sprintf islower isupper
  3 #include <cstdlib>//malloc  exit strcat itoa system("cls")
  4 #include <iostream>//pair
  5 #include <fstream>//freopen("C:\Users\13606\Desktop\草稿.txt","r",stdin);
  6 #include <bitset>
  7 //#include <map>
  8 //#include<unordered_map>
  9 #include <vector>
 10 #include <stack>
 11 #include <set>
 12 #include <string.h>//strstr substr
 13 #include <string>
 14 #include <time.h>//srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
 15 #include <cmath>
 16 #include <deque>
 17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less
 18 #include <vector>//emplace_back
 19 //#include <math.h>
 20 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor
 21 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)
 22 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
 23 //******************
 24 int abss(int a);
 25 int lowbit(int n);
 26 int Del_bit_1(int n);
 27 int maxx(int a,int b);
 28 int minn(int a,int b);
 29 double fabss(double a);
 30 void swapp(int &a,int &b);
 31 clock_t __STRAT,__END;
 32 double __TOTALTIME;
 33 void _MS(){__STRAT=clock();}
 34 void _ME(){__END=clock();__TOTALTIME=(double)(__END-__STRAT)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;}
 35 //***********************
 36 #define rint register int
 37 #define fo(a,b,c) for(rint a=b;a<=c;++a)
 38 #define fr(a,b,c) for(rint a=b;a>=c;--a)
 39 #define mem(a,b) memset(a,b,sizeof(a))
 40 #define pr printf
 41 #define sc scanf
 42 #define ls rt<<1
 43 #define rs rt<<1|1
 44 typedef long long ll;
 45 const double E=2.718281828;
 46 const double PI=acos(-1.0);
 47 //const ll INF=(1LL<<60);
 48 const int inf=(1<<30);
 49 const double ESP=1e-9;
 50 const int mod=(int)1e9+7;
 51 const int N=(int)1e6+10;
 52 
 53 struct node
 54 {
 55     long long base[62];
 56 
 57     void Init()
 58     {
 59         for(int i=0;i<61;++i)
 60             base[i]=0;
 61     }
 62 
 63     bool check(long long x)
 64     {
 65         for(int i=61;i>=0;--i)
 66         {
 67             if(x&(1LL<<i))
 68             {
 69                 if(!base[i])return 0;
 70                 else x^=base[i];
 71             }
 72         }
 73         return 1;
 74     }
 75 
 76     void Insert(long long x)
 77     {
 78         for(int i=61;i>=0;--i)
 79         {
 80             if(x>>i&1)
 81             {
 82                 if(base[i])
 83                     x^=base[i];
 84                 else
 85                 {
 86                     base[i]=x;
 87                     break;
 88                 }
 89             }
 90         }
 91     }
 92 }BASE[5],temp,v,ans;
 93 
 94 ll a[N],b[N];
 95 void merge(const node &a,node &b,node &ans)
 96 {//  https://blog.csdn.net/qcwlmqy/article/details/97584411
 97     temp=v=a;
 98     fo(i,0,60)
 99     {
100         if(b.base[i])
101         {
102             long long x=b.base[i],now=0;
103             int g=0;
104             for(int j=60;j>=0;j--)
105             {
106                 if(x>>j&1)
107                 {
108                     if(!temp.base[j])
109                     {
110                         g=1;
111                         temp.base[j]=x;
112                         v.base[j]=now;
113                         break;
114                     }
115                     x^=temp.base[j];now^=v.base[j];
116                 }
117             }
118             if(!g)
119                 ans.Insert(now);
120         }
121     }
122 }
123 int main()
124 {
125     int n;
126     while(~sc("%d",&n))
127     {
128         BASE[1].Init();
129         BASE[2].Init();
130         ans.Init();
131         for(int i=1;i<=n;++i)
132             sc("%lld",&a[i]),BASE[1].Insert(a[i]);
133         for(int i=1;i<=n;++i)
134             sc("%lld",&b[i]),BASE[2].Insert(b[i]);
135         merge(BASE[1],BASE[2],ans);
136         int cnt=0;
137         for(int i=0;i<61;++i)
138             if(ans.base[i])
139                 cnt++;
140         ll ANS=1;
141         for(int i=1;i<=cnt;++i)
142             ANS*=2;
143         pr("%lld
",ANS);
144     }
145     return 0;
146 }
147 
148 /**************************************************************************************/
149 
150 int maxx(int a,int b)
151 {
152     return a>b?a:b;
153 }
154 
155 void swapp(int &a,int &b)
156 {
157     a^=b^=a^=b;
158 }
159 
160 int lowbit(int n)
161 {
162     return n&(-n);
163 }
164 
165 int Del_bit_1(int n)
166 {
167     return n&(n-1);
168 }
169 
170 int abss(int a)
171 {
172     return a>0?a:-a;
173 }
174 
175 double fabss(double a)
176 {
177     return a>0?a:-a;
178 }
179 
180 int minn(int a,int b)
181 {
182     return a<b?a:b;
183 }

免责声明:文章转载自《线性基求交(2019牛客国庆集训派对day4)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇减2或减3(很搞的贪心)2019牛客国庆集训派对day6Points Division(线段树+DP)2019牛客暑期多校训练营(第一场)下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

开发环境部署 开发环境部署 &lt; Main &lt; TWiki 开发环境部署 1. 部署 2. 软件包 1. 部署 0. 自动化部署 附件: auto_depl.tar 功能:将以下部署环境安装操作:将包解压,用root运行work.sh即可 1. boost库 功能: 提供线程、文件操作、正则表达式、通信框架等跨平台类库主页: http://www.boost.org 安装:开发

开发环境部署 < Main < TWiki 开发环境部署 1. 部署 2. 软件包 1. 部署 0. 自动化部署 附件: auto_depl.tar 功能:将以下部署环境安装操作:将包解压,用root运行work.sh即可 1. boost库 功能: 提供线程、文件操作、正则表达式、通信框架等跨平台类库主页: http://w...

Emacs学习笔记(一)

Emacs是什么?E. M. A. C. S.emacs Makes A Computer SlowEscape Meta Alt Control Shiftemacs Makers Are Crazy Sickosemacs Makes All Computing Simpleemacs Makefiles Annihilate C-Shellsemacs...

NetBeans 时事通讯(刊号 # 61 Jun 25, 2009)

刊号 # 61 - Jun 25, 2009 项目新闻 GlassFish ESB v2.1 已发布——包括 NetBeans 6.5 开源项目 OpenESB 已经发布了最新版本:GlassFish ESB v2.1。此次发布包括了作为设计工具的 NetBeans IDE 6.5.1 和作为运行时的 GlassFish。下载包含...

Programming tutorials and source code examples

Programming tutorials and source code examples PostgreSQL SQL / MySQL MySQL Tutorial ASP.Net ASP.NET Tutorial Silverlight ASP.NET Open Source C# / C Sharp C# Book C# / C...

JSF: 动态生成的DataTable, 固定表头, 固定行标

自己写了段小代码, 希望可以供大家学习和参考。 代码里没有太多注释, 有时间的话我会补充上去。自己在写动态生成DataTable的时候也查阅了很多相关文章, 以及实现固定表头等等。在解决固定表头问题上我是用的两张表(加行标是3张表)实现的, 因为我发现如果用JSF1.1的化实现固定表头几乎不可能(如果有人有好的想法, 比如用JS比较在行的朋友请告诉我解决方...

文档中心 FetchURL Sina App Engine

文档中心 - FetchURL - Sina App Engine FetchURL 服务概要 应用场景 使用指南 抓取页面 发起POST请求 错误码参考 服务限制与配额 服务限制 分钟配额 常见问题 收起 服务概要 应用场景 使用指南 服务限制与配额 常见问题...