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}\) 。如何统计自由元？与线性方程组这题思路一致，只要找有多少个主元会导致无穷解（或者说不能唯一确定）即可，不再赘述。可以参考代码。
代码

如下：
[code]#include#include#include#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);#define MIKU 0using namespace std;int k, n, x, y, idx = 1;bitset a[35];int Gauss() {        for(int i=1; i>x>>y && (x || y)) a[y][x] = 1;                int ans = Gauss();                !ans ? cout

用心讨论，共获提升！

懂技术并乐意极积无私分享的人越来越少。珍惜

用心讨论，共获提升！