题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1923

题意:


高斯消元解异或方程组

传统的高斯消元是长这个样子的(以一行为例

$$a_1x_1+a_2x_2+...+a_nx_n=b$$

异或方程组是长这个样子的

$$a_1x_1\wedge a_2x_2\wedge...\wedge a_nx_n=b$$

其中 a,x,b 的取值均为 1 或 0,和传统高斯消元没什么区别,只不过过程和结果都模了 2,那么加减消元改为异或消元就好了,还不用考虑精度,岂不美哉

此题的特点是方程组不是 n 个... 是 m 个... 所以如果消元过程中出现无解/多解情况(选定的 a[i][i] 为 0),可以找到下面一个该项不为 0 的方程,换上来继续解

在具体的实现中,由于需要多次整体异或什么的,可以用 bitset 实现,跑的飞快 qwq

 


一个非常弱的准退役OIER