一位在退学边缘疯狂试探的学渣为了高代不挂科做出的最终努力

33281378432849
## 1. 爪形行列式

1. 求$D_n = \left| {\begin{array}{*{20}{c}}
   {{x_1}}&1& \cdots &1\\
   1&{{x_2}}& \cdots &0\\
    \vdots & \vdots & \ddots &0\\
   1&0&0&{{x_n}}
   \end{array}} \right|$

## 2. 两三角型行列式

1. 求$D_n = \left| {\begin{array}{*{20}{c}}
   {{x_1}}&b& \cdots &b\\
   b&{{x_2}}& \cdots &b\\
    \vdots & \vdots & \ddots &b\\
   b&b&b&{{x_n}}
   \end{array}} \right|$
2. 求${D_n} = \left| {\begin{array}{*{20}{c}}
   {{x_1}}&b&b& \cdots &b\\
   a&{{x_2}}&b& \cdots &b\\
   a&a&{{x_3}}& \cdots &b\\
    \vdots & \vdots & \vdots & \ddots & \vdots \\
   a&a&a& \cdots &{{x_n}}
   \end{array}} \right|$
3. 求${D_n} = \left| {\begin{array}{*{20}{c}}
   d&b&b& \cdots &b\\
   c&x&a& \cdots &a\\
   c&a&x& \cdots &a\\
    \vdots & \vdots & \vdots & \ddots & \vdots \\
   c&a&a& \cdots &x
   \end{array}} \right|$

## 3. 两条线型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}}
  {{a_1}}&{{b_1}}&0& \cdots &0\\
  0&{{a_2}}&{{b_2}}& \cdots &0\\
  0&0&{{a_3}}& \cdots &0\\
   \vdots & \vdots & \vdots & \ddots & \vdots \\
  {{b_n}}&0&0& \cdots &{{a_n}}
  \end{array}} \right|$

## 4. 范德蒙德型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}}
  {{a_1^n}}&{{a_1^{n-1}b_1}}& \cdots &a_1b_1^{n-1}&b_1^n\\ a_2^n&a_2^{n-1}b_2&\cdots & a_2b_2^{n-1} &b_2^n\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_n^n & a_n^{n-1}b_n & \cdots & a_nb_n^{n-1}& b_n^n \\ a_{n+1}^n&a_{n+1}^{n-1}b_{n+1}&\cdots&a_{n+1}b_{n+1}^{n-1} &b_{n+1}^n
  \end{array}} \right|$

## 5. Hessenberg型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}}
  1&2&3& \cdots &n\\
  1&{ - 1}&0& \cdots &0\\
  0&2&{ - 2}& \cdots &0\\
   \vdots & \vdots & \vdots & \ddots & \vdots \\
  0&0&0& \cdots &{1 - n}
  \end{array}} \right|$

## 6. 三对角型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}}
  a&b&0& \cdots &0\\
  c&a&b& \cdots &0\\
  0&c&a& \cdots &0\\
   \vdots & \vdots & \vdots & \ddots & \vdots \\
  0&0&0& \cdots &a
  \end{array}} \right|$

## 7. 各行元素和相等型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}}
  {1 + {x_1}}&{{x_1}}&{{x_1}}& \cdots &{{x_1}}\\
  {{x_2}}&{1 + {x_2}}&{{x_2}}& \cdots &{{x_2}}\\
  {{x_3}}&{{x_3}}&{1 + {x_3}}& \cdots &{{x_3}}\\
   \vdots & \vdots & \vdots & \ddots & \vdots \\
  {{x_n}}&{{x_n}}&{{x_n}}& \cdots &{1 + {x_n}}
  \end{array}} \right|​$

## 8. 相邻两行对应元素相差K倍型行列式

1. 求${D_n} = \left| {\begin{array}{*{20}{c}}
   0&1&2& \cdots &{n - 1}\\
   1&0&1& \cdots &{n - 2}\\
   2&1&0& \cdots &{n - 3}\\
    \vdots & \vdots & \vdots & \ddots & \vdots \\
   {n - 1}&{n - 2}&1& \cdots &0
   \end{array}} \right|$
2. 求${D_n} = \left| {\begin{array}{*{20}{c}}
   1&a&{{a^2}}& \cdots &{{a^{n - 1}}}\\
   {{a^{n - 1}}}&1&a& \cdots &{{a^{n - 2}}}\\
   {{a^{n - 2}}}&{{a^{n - 1}}}&1& \cdots &{{a^{n - 3}}}\\
    \vdots & \vdots & \vdots & \ddots & \vdots \\
   a&{{a^2}}&{{a^3}}& \cdots &1
   \end{array}} \right|$

【BZOJ 3811】玛里苟斯

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3811
神犇题解Ⅰ:https://blog.sengxian.com/solutions/bzoj-3811
神犇题解Ⅱ:http://yyy.is-programmer.com/posts/200623.html

解题报告

这题这么神,我们来分情况讨论:

1. $k = 1$

这就是一般的期望题。因为期望的线性,所以我们在二进制位下每一位分开考虑:

如果这一位上每一个数都是$0$,那么贡献肯定为$0$
如果有一个数为不为$0$那么我们有贡献的概率为$\frac{1}{2}$

证明的话,可以设$f_{1,0/1}$为考虑到第i个数,异或起来为0/1的概率
写出$DP$式子可以很轻松地发现这俩总是对半分,Q.E.D

于是我们直接把所有数$or$起来,然后除二输出即可
时间复杂度:$O(n)$

2. $k = 2$

这不是一般的期望题了,不是线性的,不能直接加 /(ㄒoㄒ)/~~
但我们发现某一个异或和为$(b_mb_{m-1} \cdots b_0)_{bin}$的话
其中第$i$位与第$j$位的贡献为$b_i \cdot b_j \cdot 2^{i+j}$

因为$b_i$与$b_j$是线性的,所以我们就可以枚举$i,j$然后直接加起来了!
根据$k = 1$时得到的结论,不难发现:

如果这两位独立则贡献的概率为$\frac{1}{4}$
如果这两位不独立,那么贡献的概率为$\frac{1}{2}$
如果这两位中有至少一位从没出现过,那么概率为$0$

于是我们暴力枚举$i,j$直接算贡献就可以了
时间复杂度:$O(62n + 62^2)$

3. $k \ge 3$

我们先来看一个结论:若$E(x^k) < 2^{63}$,初始集合中的每个数小于$2^{22}$
证明的话,sengxian教我的:

不妨用反证法,考虑答案为:$\sum\limits_{s \in \{1,2,\cdots,n\}}{\frac{v^3}{2^n}}$
假如有一个数的二进制下第$22$位出现了$1$,有$2^{n-1}$个集合异或起来后这一位为$1$
所以这一位的贡献就已经为$2^{63}$了,又因为答案小于$2^{63}$,矛盾,故不可能,Q.E.D

所以我们可以求出这些数的线性基,然后暴力枚举线性基的子集
根据$k = 1$时的人生经验,我们又可以得到每一种情况出现的概率相等
于是我们暴力枚举,然后暴力算贡献就可以了
时间复杂度:$O(21n + 2^{21})$

【BZOJ 4644】经典傻逼题

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4644
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5734792.html
神犇题解Ⅱ:http://blog.csdn.net/neither_nor/article/details/53997223

解题报告

首先,如果我们把边权异或到点上
原问题就可以转化为:选一些点,使NIM和最大
于是就是线性基的锅了,时间复杂度:$ \frac{{nm{L^2}}}{{{\rm{64}}}}$

然后我们发现这么做会T
于是对时间进行分治
这样的话,复杂度优化到:$ \frac{{m\log m{L^2}}}{{{\rm{64}}}}$

然后Claris还说可以用Method of Four Russians
这样话,复杂度就变成了:$ \frac{{m\log m{L^2}}}{{{\rm{64logL}}}}$

【Codeforces 662A】Gambling Nim

题目传送门:http://codeforces.com/problemset/problem/662/A
官方题解:http://codeforces.com/blog/entry/44408

说人话就是亦或和为0的概率是多少
考虑把ai全部亦或起来为sum的话
那就是求{ai^bi}有多少个子集亦或和为sum
这样的话,岂不就是线性基的拿手好戏了?

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500000+9;
const int SGZ = 61+9;

int n,cnt;
LL a[N],b[N],bas[SGZ],sum; 

inline LL read(){
	char c=getchar(); LL ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline bool insert(LL w) {
	for (int i=61;~i;i--) if (w&(1LL<<i)) {
		if (bas[i]) {
			w ^= bas[i];
		} else {
			bas[i] = w;
			return true;
		}
	}	
	return false;
}

inline LL pow(LL w, int t) {
	LL ret = 1;
	while (t) {
		if (t & 1) ret *= w;
		w *= w; t >>= 1;
	}
	return ret;
}

int main(){
	n = read();
	for (int i=1;i<=n;i++) {
		a[i] = read();
		b[i] = read();
		sum ^= a[i];
		cnt += insert(a[i] ^ b[i]);
	}
	if (!cnt && !sum) {
		puts("0/1");
	} else if (insert(sum)) {
		puts("1/1");
	} else {
		printf("%I64d/%I64d\n",pow(2LL,cnt)-1,pow(2LL,cnt));
	}
	return 0;
}

【BZOJ 2844】albus就是要第一个出场

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2844
数据生成器:http://paste.ubuntu.com/23312434/

话说这个题啊!还是挺有意思哒!
有一个结论:如果相同的数要计入答案的话,那每种答案出现了2^(n-线性基的数量)
证明:既然都为0了,那么取不取都不影响答案,于是可以随便搞一搞

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 10086;
const int N = 100000+9;
const int SGZ = 30+9;

int n,m,arr[N],bas[SGZ],cnt,vout;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline bool insert(int w) {
	for (int i=30;~i;i--) if (w&(1<<i)) {
		if (bas[i]) {
			w ^= bas[i];
		} else {
			bas[i] = w;
			return true;
		}
	}
	return false;
}

inline int pow(int w , int t) {
	int ret = 1;
	while (t) {
		if (t&1) ret = (LL)ret * w % MOD;
		w = (LL)w * w % MOD; t >>= 1;
	}
	return ret;
}

int main(){
	n = read();
	for (int i=1;i<=n;i++) {
		arr[i] = read();
		cnt += insert(arr[i]);
	}
	m = read();
	for (int i=30,tmp=pow(2,n-cnt);~i;i--) if (bas[i]) {
		cnt--;
		if (m&(1<<i)) {
			vout += tmp * (1LL<<cnt) % MOD;
			vout %= MOD;
		}
	}
	printf("%d\n",(vout+1)%MOD);
	return 0;
}

【HDU 3949】XOR

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3949

这个题ihopenot都说是水题了,那我也扔一份代码就跑吧!
想看题解的戳这里:http://acm.hdu.edu.cn/showproblem.php?pid=3949

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 10000+9;

int n,bas[70],cnt,m;
LL arr[N],l,r,STA,tag;

inline void insert(LL &w, int num) {
	for (int i=61;~i;i--) if (w & (1LL<<i)) {
		if (bas[i]) {
			w ^= arr[bas[i]];
		} else {
			bas[i] = num;
			break;
		}
	}
	if (!w) tag = 1;
}

inline LL cal(LL w) {
	LL ret = 0;
	for (int i=0,cur=0;i<cnt;i++) {
		while (!bas[cur]) cur++;
		if (w&(1LL<<i)) ret ^= arr[bas[cur]];
		cur++;
	}
	return ret;
}

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	for (int T=read(),tot=1;T;T--,tot++) {
		printf("Case #%d:\n",tot);
		memset(bas,0,sizeof(bas));
		memset(arr,0,sizeof(arr));
		cnt = tag = 0; 
	 
		n = read();
		for (int i=1;i<=n;i++) {
			cin>>arr[i];
			insert(arr[i],i);
		}	
		
		for (int i=0;i<=61;i++) if (bas[i]) {
			++cnt;
			for (int j=i+1;j<=61;j++) if (bas[j]) {
				if (arr[bas[j]] & (1LL<<i)) {
					arr[bas[j]] ^= arr[bas[i]];
				}
			}
		}	
		
		m = read(); STA = (1LL<<cnt) - 1;
		for (int i=1;i<=m;i++) {
			LL tmp; scanf("%I64d",&tmp); tmp -= tag;
			if (STA < tmp) puts("-1");
			else printf("%I64d\n",cal(tmp));
		}
	}
	return 0;
}

【BZOJ 3569】DZY Loves Chinese II

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3569
数据生成器:http://paste.ubuntu.com/23227745/

这个题,是我到目前为止,做过的最妙的一道题
没有之一

给每一个非树边搞一个权值
然后亦或到它所覆盖的每一条树边上去
考虑不联通的情况:删掉了一条树边和所有覆盖他的非树边
及一个子集的亦或和为0
于是像求线性基一样,判一下是否线性无关即可

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;
const int M = 1000000+9;
const int MOD = 9999971; 
const int SGZ = 40;

int head[N],nxt[M],to[M],n,m,q,val[M];
int vis[N],c[SGZ],cnt,bas[SGZ],sym[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(int u, int v) {
	static int T = 1;
	to[++T] = v; nxt[T] = head[u]; head[u] = T; 
	to[++T] = u; nxt[T] = head[v]; head[v] = T; 
}

void DFS1(int w, int f) {
	vis[w] = 1;
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
		if (vis[to[i]]) {
			int W = rand()*(rand()%MOD); val[i] ^= W; val[i^1] ^= W;
			sym[w] ^= W; sym[to[i]] ^= W;	
		} else DFS1(to[i],w);
	}
}

void DFS2(int w, int f) {
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f && !val[i]) 
		DFS2(to[i], w), val[i] ^= sym[to[i]], 
		val[i^1] ^= sym[to[i]], sym[w] ^= sym[to[i]];
}

inline bool update(int w) {
	for (int i=0,tmp=val[w];i<=30;i++) if (tmp&(1<<i)) {
		if (!bas[i]) {bas[i] = tmp; return false;}
		else {tmp ^= bas[i]; if (!tmp) return true;}
	} return val[w]?false:true;
}

int main(){
	srand(9999971); n = read(); m = read(); 
	for (int i=1;i<=m;i++) Add_Edge(read(),read());
	DFS1(1,1); DFS2(1,1);
	for (int q=read(),k,tag;q;q--) {
		k = read(); tag = 1; memset(bas,0,sizeof(bas));
		for (int i=1;i<=k;i++) c[i] = read()^cnt;
		for (int i=1;i<=k && tag;i++) if (update(c[i]*2)) puts("Disconnected"), tag = 0;
		if (tag) puts("Connected"), cnt++;
	}
	return 0;
}

【BZOJ 4004】[JLOI2015] 装备购买

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4004
数据生成器:http://paste.ubuntu.com/23209631/

这个题目,看一眼,就是要求一组花费最小的线性基
第一次写,写的整数高斯消元,发现爆了long long
第二次改成double,发现精度不够
第三次,搞成整数高斯消元+MOD,遂过之
想一想,如果不用线性基,只是求一组线性基的话,MOD确实没影响

另外网上用double写的标程全部被叉掉了,不要问我是怎么知道的 qwq
1248545547

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 500+9;
const int MOD = 1000000007;
 
int n,m,f[N][N],bas[N],cost[N],num[N],cnt,vout; 
 
inline int read(){char c=getchar(); int ret=0,f=1;while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret*f;} 
inline bool cmp(const int a, const int b) {return cost[a] < cost[b];}
 
inline void update(int w) {
    for (int i=1;i<=m;i++) if (f[w][i]) {
        if (!bas[i]) {bas[i] = w, cnt++, vout += cost[w]; break;}
        else {
        	int t2 = f[bas[i]][i], t1 = f[w][i];
            for (int j=1;j<=m;j++) f[w][j] = ((LL)f[w][j]*t2 - (LL)f[bas[i]][j]*t1) % MOD;
        }
    }
}
 
int main(){
    n = read(); m = read();
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) f[i][j] = read();
    for (int i=1;i<=n;i++) cost[i] = read(), num[i] = i;
    sort(num+1,num+1+n,cmp);
    for (int i=1;i<=n;i++) update(num[i]);
    printf("%d %d\n",cnt,vout);
    return 0;
}

【BZOJ 3105】[cqoi2013] 新Nim游戏

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3105

这个题目,考虑两个回合之后。
假如对手能够在在第二个回合搞出一个Nim和为0的东西,那我们岂不是输了?
所以我们不能给对手搞出Nim和为0的机会,而Nim和为Xor,不存在子集Nim和为0是线性无关
而我们又要子集最大(损失最小),所以我们要求的是一个极大线性无关子集
然后我们发现,这货不是线性基吗?
于是水之

#include<bits/stdc++.h>
#define LL long long
using namespace std;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int bas[32],arr[109];
inline bool update(int w) {
	for (int i=0;i<=31;i++) if (w & 1<<i) 
		if (bas[i]) w ^= bas[i];
		else {bas[i] = w; return 1;}
	return 0;
}

int main(){
	int k = read(); LL vout = 0; 
	for (int i=1;i<=k;i++) arr[i] = read(), vout += arr[i];
	sort(arr+1,arr+1+k);
	for (int i=k;i;i--) vout -= update(arr[i])*arr[i];
	printf("%lld\n",vout);
	return 0;
}

【算法笔记】再看线性基

线性基 -> 线性无关 -> 如果有一个新向量与当前的基线性无关,则加入后当前基底表示的空间更大
判断线性相关与否 -> 当前向量能否被当前基底表示 -> 如果不能,加入当前的基底中
线性基的大小 -> 空间的维度 -> 空间的大小 -> 空间最大,即线性基的个数越多 -> 线性基的大小与其插入顺序不相关 -> 线性基的插入顺序不会影响答案

因为线性基属于线性代数范畴,其深入理解又与拟阵挂钩,而拟阵则更为高深
所以今晚再一次回看线性基,仍然没有大彻大悟,不过确实有更深入的理解
感觉wiki上的这一段话或许能说明插入顺序不影响结果:
96453144

【BZOJ 4568】[Scoi2016] 幸运数字

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4568
数据生成器:http://paste.ubuntu.com/23202923/

《浅谈省选的时候还不会线性基的悲伤有多大》
今天重新看了一看,结果最开始写的是链剖,T到死 ←是男人就去ZGS的OJ上测,单点时限
后来重新写了LCA的版本,又T到死
于是暴力优化常数,最终5.9s勉强卡过

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 20000+9; 

int n,q,head[N],nxt[N*2],to[N*2];
LL arr[N];

inline int read(){char c=getchar(); int ret=0;while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret;}
inline LL readL(){char c=getchar(); LL ret=0; while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret;}

inline void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

namespace LCA{
	int fa[N][16],dep[N];
	LL f[N][16][61],POW[61];

	void DFS(int w, int f) {
		fa[w][1] = f; fa[w][0] = w; dep[w] = dep[f] + 1; 
		for (int i=head[w];i;i=nxt[i]) if (to[i] != f) DFS(to[i],w);
	} inline void DFS(){DFS(1,1);for (int i=0;i<=60;i++) POW[i] = 1LL<<i;}
	
	inline void merge(LL *a, LL *b) {
		for (int i=60;~i;i--) if (b[i]) {
			LL w = b[i]; for (int j=60;~j;j--) if (w&POW[j]) {
				if (!a[j]) {a[j] = w; break;}
				else w ^= a[j];
			}
		} 
	}
	
	inline void init() {
		for (int j=1;j<=n;j++) for (int i=60;~i;i--) if (POW[i]&arr[j]) {f[j][0][i] = arr[j]; break;}
		for (int i=1;i<=n;i++) memcpy(f[i][1],f[i][0],sizeof(f[i][0])), merge(f[i][1],f[fa[i][1]][0]);
		for (int i=1;i<=n;i++) for (int j=2;j<=15;j++) 
			fa[i][j] = fa[fa[i][j-1]][j-1], 
			memcpy(f[i][j],f[i][j-1],sizeof(f[i][j])),
			merge(f[i][j],f[fa[i][j-1]][j-1]);
	}
	
	inline LL query(int x, int y) {
		static LL bas[61]; memset(bas,0,sizeof(bas));
		if (dep[x] < dep[y]) swap(x,y);
		for (int i=15;~i;i--) if (dep[fa[x][i]] > dep[y]) 
			merge(bas,f[x][i]), x = fa[fa[x][i]][1];
		if (x == y) merge(bas,f[x][0]);  
		else {
			for (int i=15;~i;i--)  if (fa[x][i] != fa[y][i])
				merge(bas,f[x][i]), merge(bas,f[y][i]), 
				x = fa[fa[x][i]][1], y = fa[fa[y][i]][1];
			merge(bas,f[x][0]); 
		} LL ret = 0;
		for (int i=0;i<=60;i++) if (bas[i]) 
		for (int j=i+1;j<=60;j++) if (bas[j]&POW[i]) bas[j] ^= bas[i];
		for (int i=0;i<=60;i++) ret ^= bas[i];
		return ret;
	}	
};

int main(){
	n = read(); q = read();
	for (int i=1;i<=n;i++) arr[i] = readL();
	for (int i=1;i<n;i++) Add_Edge(read(),read());
	LCA::DFS(); LCA::init(); 
	for (int i=1;i<=q;i++) printf("%lld\n",LCA::query(read(),read()));
	return 0;
}

另外,%Claris,直接上点分治:http://www.cnblogs.com/clrs97/p/5451814.html

【BZOJ 4269】再见Xor

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4269
离线版题目:http://paste.ubuntu.com/18971803/

这个题目,拿到以后,一脸懵逼啊QAQ,想拿BFS乱搞一搞,估计会T,结果还是可耻地看了题解
高斯消元求线性基QAQ,又没有学过QAQ,I well vegtable are (T_T)
其实也不难,每一个数的二进制看成方程组,然后上高斯消元。
求出线性基之后,全部^起来就是最大值,找一个最小的^一下就是次小值

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 100000+9;

int n,arr[MAXN],cnt;

inline void Gauss(){
	for (int k=31;k;k--){
		int w = 1<<(k-1), pos;
		for (pos=cnt+1;pos<=n;pos++) 
			if (arr[pos]&w) break;
		if (pos==n+1) continue;
		else {
			swap(arr[++cnt], arr[pos]);
			for (int i=1;i<=n;i++)
				if (i!=cnt && (arr[i]&w))
					arr[i] ^= arr[cnt];
		}
	}	
}

int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&arr[i]);
	Gauss(); int vout = 0;
	for (int i=1;i<=cnt;i++) vout ^= arr[i];
	printf("%d ",vout);
	printf("%d\n",vout ^= arr[cnt]);
	return 0;
}

好像还有一种方法,写法跟在线求解亦或方程组很像。
但感觉不如直接高斯消元优雅,且时间复杂度相同,所以就不贴代码啦!