Luogu P10499 开关问题 题解

前言

题目传送门 Luogu P10499 开关问题

经典的高斯消元解线性异或方程组例题。比普通的线性方程组好写，但需要在思维上转过弯来。

题意

有 \(N\) 各相同的开关，每操作一个开关都可能使一些其他的开关产生联动（即切换开关状态）。每个开关最多操作一次。给定这些开关的初始状态（一个 \(0,1\) 序列，\(0\) 代表关，\(1\) 代表开）和结束状态（同上），问有多少种方法可以实现。

思路

首先，我们应该得将题面抽象成一个方程组。怎么做呢？我们不妨设 \(a_{i,j}=1|0\) 表示第 \(j\) 盏灯 能 | 不能 带亮第 \(i\) 盏灯（注意这里顺序反了一下，原因后面会讲），设 \(x_{i}=1|0\) 表示第 \(i\) 盏灯 有 | 没有 被操作过，设 \(s_i = 1|0\) 表示第 \(i\) 盏灯的初始状态，设 \(t_i = 1|0\) 表示第 \(i\) 盏灯的最终状态。于是，我们可列出以下方程组：

\[\left\{ \begin{array}{c} a_{1,1}x_1\oplus a_{1,2}x_2\oplus \cdots \oplus a_{1,n}x_n = s_1\oplus t_1\\ a_{2,1}x_1\oplus a_{2,2}x_2\oplus \cdots \oplus a_{2,n}x_n = s_2\oplus t_2\\ \cdots\\\ a_{n,1}x_1\oplus a_{n,2}x_2\oplus\cdots \oplus a_{n,n}x_n = s_n\oplus t_n\\ \end{array} \right. \]

如果不能理解，我们以第一行第二项为例简单说明。当 \(a_{1,2}=1\) 且 \(x_2=1\) ，那么这一项就为 \(1\) ，意思是第 \(2\) 盏灯被操作了，同时第 \(2\) 盏灯被操作会引起第 \(1\) 盏灯被操作。于是第 \(1\) 盏灯的状态变化了一次。其他项同理。由于状态只能在 \(0,1\) 间变化，所以这些项之间用 \(\text{xor}\) 连接。第一行等号右边若为 \(1\) 表示第一盏灯的状态最终发生了变化，为 \(0\) 表示没有，其他行同理。

这也就是为什么上面 \(a_{i,j}\) 那里要反一下。同时也提醒我们一个细节：\(a_{i,i}\) 要初始化为 \(1\) 。

这是一个线性方程组，我们把它写成增广矩阵，如下：

\[\left[ \begin{array}{ccc|c} a_{1,1} & \cdots & a_{1,n} & s_1 \oplus t_1\\ \vdots & \ddots & \vdots & \vdots\\ a_{n,1} & \cdots & a_{n,n} & s_n \oplus t_n\\ \end{array} \right] \]

接下来，把他丢给高斯消元，我们就能解得每个 \(x_i\) 。

然后怎么做呢？我们再来分析题目。由 \(x_i\) 定义可得，对于每个确定的元，会贡献一种可能（被操作或没被操作是确定的）；对于每个自由元，会贡献两种可能（被操作过或没有都可以）。由乘法原理得，我们只需统计自由元的数量 \(cnt\) ，答案就是 \(2^{cnt}\) 。如何统计自由元？与线性方程组这题思路一致，只要找有多少个主元会导致无穷解（或者说不能唯一确定）即可，不再赘述。可以参考代码。

代码

如下：

#include<iostream>
#include<bitset>
#include<cmath>
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define MIKU 0
using namespace std;

int k, n, x, y, idx = 1;
bitset<35> a[35];

int Gauss() {
	for(int i=1; i<=n; i++) {
		int r = idx;
		for(int j=r+1; j<=n; j++) if(a[j][i]) {
			r = j;
			break;
		}
		if(!a[r][i]) continue;
		if(r != idx) swap(a[r], a[idx]);
		for(int j=idx+1; j<=n; j++) if(a[j][i]) a[j] ^= a[idx];
		idx ++;
	}
	for(int i=idx; i<=n; i++) if(a[i][n+1]) return 0;
	return 1<<(n-idx+1);
}

int main() {
	fastio;
	cin>>k;
	while(k--){
		idx = 1;
		cin>>n;
		for(int i=1; i<=n; i++) a[i].reset(), a[i][i] = 1;
		for(int i=1, x; i<=n; i++) cin>>x, a[i][n+1] = x;
		for(int i=1, x; i<=n; i++) cin>>x, a[i][n+1] = a[i][n+1] ^ x;
		while(cin>>x>>y && (x || y)) a[y][x] = 1;
		int ans = Gauss();
		!ans ? cout<<"Oh,it's impossible~!!\n" : cout<<ans<<'\n';
	}
	return MIKU;
}