开关问题

题目描述

有$N$个相同的开关,每个开关都与某些开关有着联系,每当你打开或者关闭某个开关的时候,其他的与此开关相关联的开关也会相应地发生变化,即这些相联系的开关的状态如果原来为开就变为关,如果为关就变为开。你的目标是经过若干次开关操作后使得最后$N$个开关达到一个特定的状态。对于任意一个开关,最多只能进行一次开关操作。你的任务是,计算有多少种可以达到指定状态的方法。(不计开关操作的顺序)

输入第一行有一个数K,表示以下有K组测试数据。
每组测试数据的格式如下:
第一行 一个数$N(0 < N < 29)$
第二行 $N$个$0$或者$1$的数,表示开始时$N$个开关状态。
第三行 $N$个$0$或者$1$的数,表示操作结束后$N$个开关的状态。
接下来 每行两个数$I J$,表示如果操作第$I$个开关,第$J$个开关的状态也会变化。每组数据以$0\ 0$结束。

如果有可行方法,输出总数,否则输出$“Oh,it’s \ impossible~!!”$ 不包括引号

代码

非常奇妙的做法?
反正我是肯定想不到这题要用高斯消元的

设$x[i]$表示第$i$个开关的操作情况$(1:$按了 $\ 0:$没按$)$
设$a[i][j]$表示第$i$个开关和第$j$个开关之间的联系
若按了$i$后$j$的状态会改变,则标记$a[j][i]=1$.
初始化$a[i][i] = 1$

定义开关$i$的初始状态为$pre[i]$,变换后的状态为$lat[i]$
对于任意一个开关$i$,我们有
$a[i][1]x[1] $ ^ $ a[i][2]x[2] $ ^ $… $ ^ $ a[i][n]x[n] = pre[i] $ ^ $ lat[i]$

异或其实就是不进位加法 —《算法竞赛进阶指南》

所以我们只要在高斯消元的过程中把加减法替换成^即可,并且不再需要计算乘法

如果存在$0=1$的方程,则无解
否则,因为自由元可以在${(0,1)}$中自由选择,所以选择的方案数即为 $1 $<<自由元的个数

普通版本
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
int main(){
t = read();
while(t --){
n = read();
memset(a, 0, sizeof(a));
for(int i = 1; i <= n; ++ i) a[i][n + 1] = read();
for(int i = 1; i <= n; ++ i){
a[i][n + 1] ^= read();
a[i][i] = 1;
}
while(1){
x = read(), y = read();
if(!x && !y) break;
a[y][x] = 1;
}
int ans = 0, m = 1;
//ans:自由元个数,m:已经使用(包括正在使用)的方程个数
//ans + m = i
for(int i = 1; i <= n; ++ i){
//处理i号开关
for(int j = m; j <= n; ++ j){
if(a[j][i]) {
if(m != j)
for(int k = 1; k <= n + 1; ++ k)
swap(a[m][k], a[j][k]);//*
break;
}
}
//因为只有0和1两种取值,所以寻找最大系数的操作弱化为寻找一个x[i]的系数不为0的方程
if(a[m][i] == 0){//不存在x[i]系数为1的方程,即x[i]为自由元
++ ans;
continue;//由于当前方程并没有使用,所以m不变化
}
for(int j = 1; j <= n; ++ j){
if(a[j][i] && j != m){//寻找与i开关相关联的开关,进行消元即异或操作
for(int k = 1; k <= n + 1; ++ k)
a[j][k] ^= a[m][k];
}
}
++ m;//标记方程已使用过
}
for(int i = m; i <= n; ++ i)
if(a[i][n + 1]) {
printf("Oh,it's impossible~!!\n");
m = -1;
break;
}
//[m,n]的方程各项系数皆为0,所以如果方程右侧不为0,则无解
if(m == -1) continue;
printf("%lld\n", (LL)1 << ans);
}
return 0;
}
状压优化版本

利用$x[i]$只能取$(0,1)$的特点把每个方程压缩成了一个$int$类型的整数

这样做从理性角度来说会快很多
但是$yaliOJ$上测出来都是$0ms$所以没法比…

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
//longlong最大可以存2^63-1
//int最大是2^32-1
int main(){
t = read();
while(t --){
n = read();
for(int i = 1; i <= n; ++ i) a[i] = read();//不用memset初始化
for(int i = 1, j; i <= n; ++ i) {
j = read();
a[i] ^= j;
a[i] |= 1 << i;
}
while(1){
x = read(), y = read();
if(!x && !y) break;
a[y] |= 1 << x;
}
int ans = 1;
for(int i = 1; i <= n; ++ i){
for(int j = i + 1; j <= n; ++ j)
if(a[j] > a[i]) swap(a[j], a[i]);
//这里也会简单很多,轻松找到所有方程中最靠前的不为0的系数
if(a[i] == 0) { ans = 1 << (n - i + 1); break;}
//余下的所有方程都是0=0了,即只确定了i-1个主元,有n-i+1个自由元
if(a[i] == 1) { ans = 0; break;}
//出现0=1的方程,无解
for(int k = n; k; -- k){
if(a[i] >> k & 1){
//找到最高的项.这里会比普通版本要麻烦一些但是因为是二进制运算所以很快
for(int j = 1; j <= n; ++ j){
if(i != j && (a[j] >> k & 1)) a[j] ^= a[i];
//这个异或操作也顶级方便啊啊啊啊
}
break;
}
}
}
if(ans == 0) printf("Oh,it's impossible~!!\n");
else printf("%d\n", ans);
}
return 0;
}
//总之是十分优秀的做法