20160406】滚出来浪学了高消和异或相关……一脸懵比

90 阅读 0 评论 60 点赞

我是靠谱客的博主满意老虎，这篇文章主要介绍20160406】滚出来浪学了高消和异或相关……一脸懵比，现在分享给大家，希望可以做个参考。

表示翘了几天课浪出来集hua训shui的Flaze被吓得飞起QuQ

嗯，今天讲了一上午的高消和异或，然而本蒟蒻觉得其实整间教室里的人除了我都觉得讲的是水题【T地一声哭了出来【表示还好昨天和FTC扯淡的时候被科普了一下垫底虽然还是被吓傻了x

总之就是一群方程和一群未知数，用每一个方程和其他方程加加减减，去掉其他方程里的某一个未知数【于是消到最后就每个方程都只剩一个未知数就可以开始浪了【然而裸的实数高消一般没啥题，于是引入了异或高消再到奇奇怪怪的异或和题

其实异或高消只是单纯地把加减换成异或，然后原本定义域是实数的未知数们表示只能取0或1了【总觉得我语死早QuQ毕竟语文老师是班主任，写成这样已经尽力了Orz

于是在消元的时候就有一些特殊情况QuQ

1)发现某一个未知数的系数全是一，这货就是一个自由元了……【就是说取值任意咯，如果是实数方程组那就是有无穷解，如果是异或的话那就解的个数*=2

2)未知数用完啦只剩方程啦……就看这些方程能不能满足【反正解的个数不是0就是1

3)方程用完了还剩一堆未知数，那剩下的就全是自由元【如果是实数高消，就是无穷解，如果是异或的话，就数一下自由元的个数（加上情况(1)的）（假装这个值是cnt），最后解的个数就是2^cnt

哦……似乎这个方程组自由元的个数是确定的，然而哪些是自由元可以自由确定，所以啊，高消的很多神du犇liu题就可以出了

==================================================================

嗯……以下都是异或的题了

假装共有n个未知数，cnt个自由元

1) 对于已知方程左半问能够组成多少种不同的情况

比如有很多个开关，一个开关能够控制若干个灯，刚开始所有灯都是关着的，问有多少种开灯的情况

这个时候的解就是2^(n-cnt)

n-cnt就是矩阵的秩，具体什么意思我也是懵逼的总之求这个东西的时候似乎可以把矩阵的横竖换一下，然后消元什么的就比较轻松了【假装自己会做】

2) 对于什么都给完了，问有多少组解，答案就是2^n了

【假装自己听懂了课认真地写着博客】

↓几个比较重要的思考题

•例1：给定n个非负整数，选2个，求最大的异或值。

•例2：给定n个非负整数，选任意多个，判断其异或值是否可以等于给定的非负整数s。

•例3：给定n个非负整数，选任意多个，异或结果有多少种？

•例4：给定n个非负整数，选任意多个，求最大的异或值。

•例5：给定n个非负整数，另给定非负整数s，从n个数中选任意多个，求其与s的最大异或值。

以及带异或玩的图论题（都是联通图）

•例1：给定一棵树，求最大的异或路径【这个的话直接记录每个点到根的异或和就好了，反正lca上面的那些直接被异或抵消掉了

•例2：给定一个无向图，求最大的异或割

•例3：给定一个无向图，求最大的异或环

（不必是简单环）

•练习题：给定一个无向图，求1到n的最大的异或路径

（不必是简单路径）

然后…………然后……？大概用异或的时候要注意可以抵消……顺便线性基这种东西也是很有趣的……【比如最后这个……写了一下午的题QuQ，最后发现自己太naive怒写线性基……关于线性gay什么的自行百度，反正我语死早【】

反正根据题意就是贪心地让尽量高的位上有基底，后面的自生自灭

于是黏上自己丑哭的呆马……【只写了最后一道题】【其实并没有写高斯消元23333】【才不是我写挂了只是写得太丑不忍心发x】

bzoj2115: [Wc2011] Xor

复制代码

/**************************************************************
Problem: 2115
User: Flaze
Language: C++
Result: Accepted
Time:728 ms
Memory:5376 kb
****************************************************************/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<bitset>
#include<iostream>
using namespace std;
int n,m;
struct t1{
int to,nxt;
long long lth;
}edge[200057];
int cnt_edge=0;
int fst[50057];
void addedge(int x,int y,long long lth){
edge[++cnt_edge].to=y;
edge[cnt_edge].lth=lth;
edge[cnt_edge].nxt=fst[x];
fst[x]=cnt_edge;
}
//===========================================
int vis[50057];
long long dis[50057];
int que[50057],head=0,tail=0;
long long tm[64];
void rjq(long long x){
for(int i=63;~i;--i)
if(x&(1ll<<i)){
if(tm[i])
x^=tm[i];
else{
tm[i]=x;
break;
}
}
}
void bfs(int now){
que[tail++]=now;
vis[now]=1;
while(head^tail){
now=que[head++];
for(int tmp=fst[now];tmp;tmp=edge[tmp].nxt){
if(vis[edge[tmp].to]){
if (dis[now]^dis[edge[tmp].to]^edge[tmp].lth)
rjq(dis[now]^dis[edge[tmp].to]^edge[tmp].lth);
}
else{
que[tail++]=edge[tmp].to;
vis[edge[tmp].to]=1;
dis[edge[tmp].to]=dis[now]^edge[tmp].lth;
}
}
}
}
//============================================
long long ans;
long long max_xor(long long s){
for(int i=63;~i;--i){
if((!((1ll<<i)&ans))&&tm[i])
ans^=tm[i];
}
return ans;
}
int main(){
memset(edge,0,sizeof(edge));
memset(fst,0,sizeof(fst));
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
memset(tm,0,sizeof(tm));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int a,b;
long long c;
scanf("%d%d%lld",&a,&b,&c);
addedge(a,b,c);
addedge(b,a,c);
}
bfs(1);
ans=dis[n];
//
cout<<ans<<endl;
cout<<max_xor(ans);
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/**************************************************************
Problem: 2115
User: Flaze
Language: C++
Result: Accepted
Time:728 ms
Memory:5376 kb
****************************************************************/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<bitset>
#include<iostream>
using namespace std;
int n,m;
struct t1{
int to,nxt;
long long lth;
}edge[200057];
int cnt_edge=0;
int fst[50057];
void addedge(int x,int y,long long lth){
edge[++cnt_edge].to=y;
edge[cnt_edge].lth=lth;
edge[cnt_edge].nxt=fst[x];
fst[x]=cnt_edge;
}
//===========================================
int vis[50057];
long long dis[50057];
int que[50057],head=0,tail=0;
long long tm[64];
void rjq(long long x){
for(int i=63;~i;--i)
if(x&(1ll<<i)){
if(tm[i])
x^=tm[i];
else{
tm[i]=x;
break;
}
}
}
void bfs(int now){
que[tail++]=now;
vis[now]=1;
while(head^tail){
now=que[head++];
for(int tmp=fst[now];tmp;tmp=edge[tmp].nxt){
if(vis[edge[tmp].to]){
if (dis[now]^dis[edge[tmp].to]^edge[tmp].lth)
rjq(dis[now]^dis[edge[tmp].to]^edge[tmp].lth);
}
else{
que[tail++]=edge[tmp].to;
vis[edge[tmp].to]=1;
dis[edge[tmp].to]=dis[now]^edge[tmp].lth;
}
}
}
}
//============================================
long long ans;
long long max_xor(long long s){
for(int i=63;~i;--i){
if((!((1ll<<i)&ans))&&tm[i])
ans^=tm[i];
}
return ans;
}
int main(){
memset(edge,0,sizeof(edge));
memset(fst,0,sizeof(fst));
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
memset(tm,0,sizeof(tm));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int a,b;
long long c;
scanf("%d%d%lld",&a,&b,&c);
addedge(a,b,c);
addedge(b,a,c);
}
bfs(1);
ans=dis[n];
//
cout<<ans<<endl;
cout<<max_xor(ans);
return 0;
}

=================================================================================================

啊对……还有一道题……然而并不是bzoj权限号只好自己用CV评测了一下【虽然题并没有过审233333】

粘上丑的一比的呆马【也是有高消的了23333

bitset大法好x

BZOJ 3690

题面：

棋盘(chess)

256MB 1s

【题目描述】

给定n*m的棋盘，每个格子是黑色或白色，初始全为白色。一个格子的势力范围是它自己以及能通过马一步走到的格子。按下一个格子后，它的势力范围的颜色将会反转。我们希望选中一个格子的集合，按下后可以使得棋盘变成全黑。问这样的集合共有多少种，答案对123456789取模。

【输入格式】

两行，每行一个正整数分别是n, m。

【输出格式】

仅一行，一个正整数，答案对1000000007取模的结果。

【输入样例】

2

3

【输出样例】

4

【数据规模与约定】

对于50%的数据，n, m<=10；

对于100%的数据，n, m<=150。

呆马：

复制代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<bitset>
#include<iostream>
using namespace std;	int m,n;
const int mod=123456789;
int cnt_wz=0;
int MN;
const int cx[8]={-2,-1,1,2,1,-1,-2,0};
const int cy[8]={-1,-2,-2,-1,2,2,1,0};
bitset<465> gs[505],f[200][200];	int cnt_gs=0;
int cnt_fr=0;
void gauss(){
for(int i=1;i<=cnt_wz;++i){
int flg=0;
for(int j=i;j<=cnt_gs;++j){
if(gs[j][i]){
swap(gs[j],gs[i]);
flg=1;
break;
}
}
if(!flg)	++cnt_fr;
else
for(int j=1;j<=cnt_gs;++j)
if(gs[j][i]&&j!=i)
gs[j]^=gs[i];
}
}
int pow(int d,int w){
long long tmp=1;
long long rec=d;
while(w){
if(w&1)
tmp*=rec,tmp%=mod;
w>>=1;
rec*=rec,rec%=mod;
}
return tmp;
}
int main(){
memset(f,0,sizeof(f));
memset(gs,0,sizeof(gs));
scanf("%d%d",&n,&m);
if(n<2||m<2){
printf("%dn",(n&m)!=0);
return 0;
}
for(int i=1;i<=2;++i)
for(int j=1;j<=m;++j)
f[i][j][++cnt_wz]=1;
for(int i=3;i<=n;++i)	f[i][1][++cnt_wz]=1;
MN=cnt_wz;
for(int i=3;i<=n;++i)
for(int j=2;j<=m;++j)
for(int dir=0;dir<8;++dir){
if(i-2+cx[dir]>0&&i-2+cx[dir]<=n&&j-1+cy[dir]>0&&j-1+cy[dir]<=m)
f[i][j]^=f[i-2+cx[dir]][j-1+cy[dir]];
}
//ÏÂÃæ¹òÁËorz
for(int i=n-1;i<=n;++i)
for(int j=1;j<=m;++j){
++cnt_gs;
for(int k=1;k<=MN;++k){
int tmp=0;
for(int dir=0;dir<8;++dir)
if(i+cx[dir]>0&&i+cx[dir]<=n&&j+cy[dir]>0&&j+cy[dir]<=m)
tmp^=f[i+cx[dir]][j+cy[dir]][k];
gs[cnt_gs][k]=tmp;
}
}
for(int i=1;i<=n-2;++i){
++cnt_gs;
for(int k=1;k<=MN;++k){
int tmp=0;
for(int dir=0;dir<8;++dir)
if(i+cx[dir]>0&&i+cx[dir]<=n&&m+cy[dir]>0&&m+cy[dir]<=m)
tmp^=f[i+cx[dir]][m+cy[dir]][k];
gs[cnt_gs][k]=tmp;
}
}
gauss();
printf("%d",pow(2,cnt_fr));
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<bitset>
#include<iostream>
using namespace std;	int m,n;
const int mod=123456789;
int cnt_wz=0;
int MN;
const int cx[8]={-2,-1,1,2,1,-1,-2,0};
const int cy[8]={-1,-2,-2,-1,2,2,1,0};
bitset<465> gs[505],f[200][200];	int cnt_gs=0;
int cnt_fr=0;
void gauss(){
for(int i=1;i<=cnt_wz;++i){
int flg=0;
for(int j=i;j<=cnt_gs;++j){
if(gs[j][i]){
swap(gs[j],gs[i]);
flg=1;
break;
}
}
if(!flg)	++cnt_fr;
else
for(int j=1;j<=cnt_gs;++j)
if(gs[j][i]&&j!=i)
gs[j]^=gs[i];
}
}
int pow(int d,int w){
long long tmp=1;
long long rec=d;
while(w){
if(w&1)
tmp*=rec,tmp%=mod;
w>>=1;
rec*=rec,rec%=mod;
}
return tmp;
}
int main(){
memset(f,0,sizeof(f));
memset(gs,0,sizeof(gs));
scanf("%d%d",&n,&m);
if(n<2||m<2){
printf("%dn",(n&m)!=0);
return 0;
}
for(int i=1;i<=2;++i)
for(int j=1;j<=m;++j)
f[i][j][++cnt_wz]=1;
for(int i=3;i<=n;++i)	f[i][1][++cnt_wz]=1;
MN=cnt_wz;
for(int i=3;i<=n;++i)
for(int j=2;j<=m;++j)
for(int dir=0;dir<8;++dir){
if(i-2+cx[dir]>0&&i-2+cx[dir]<=n&&j-1+cy[dir]>0&&j-1+cy[dir]<=m)
f[i][j]^=f[i-2+cx[dir]][j-1+cy[dir]];
}
//ÏÂÃæ¹òÁËorz
for(int i=n-1;i<=n;++i)
for(int j=1;j<=m;++j){
++cnt_gs;
for(int k=1;k<=MN;++k){
int tmp=0;
for(int dir=0;dir<8;++dir)
if(i+cx[dir]>0&&i+cx[dir]<=n&&j+cy[dir]>0&&j+cy[dir]<=m)
tmp^=f[i+cx[dir]][j+cy[dir]][k];
gs[cnt_gs][k]=tmp;
}
}
for(int i=1;i<=n-2;++i){
++cnt_gs;
for(int k=1;k<=MN;++k){
int tmp=0;
for(int dir=0;dir<8;++dir)
if(i+cx[dir]>0&&i+cx[dir]<=n&&m+cy[dir]>0&&m+cy[dir]<=m)
tmp^=f[i+cx[dir]][m+cy[dir]][k];
gs[cnt_gs][k]=tmp;
}
}
gauss();
printf("%d",pow(2,cnt_fr));
return 0;
}

***********************************************************************************************************************************************************

嗯最后，看隔壁的lk姐姐都写得那么文艺，文笔连小学生都不如的某Flaze表示还是写一写情感专栏orz

·昨天晚上的谁是卧底真是“惊险刺激”（commented by YJQ），某TPZ的词库简直够了，污似我都表示根本下不去口【顺便玩着玩着忽然扔进来的小卡片真是Interesting，我才没有收集（也没有收藏）呢哼唧】嗯……然后狼人游戏啥的YJQ这种生物简直就是游戏败类万恶之源x神tm智商【YJQ太神辣QuQ】

·嗯顺便就写一写前几天的ACM，表示某磨子桥技工学校的女队【除了我】真是太神辣！！！lk姐姐的微积分简直吓飞我了QuQ！！！A题的感觉真的好爽啊【罚时是什么我怎么没有听说过【望天

·据说某grh被妹子表白了嘿嘿嘿然而太年轻了啊嘿嘿嘿一颗赛艇233333

·总觉得FTC应该和lxl在一起_(:зゝ∠)_【大小写是什么我才不知道呢

·还有FTC好可怕QuQ

·今天晚上UESTC附中的511机房被磨子桥技工学校占领啦【才没有颓HSOJ也没有刷Iwanna题库呢哼唧

·嗯我就是过来划水的并不打算d任何人【喂