Luogu2447 [SDOI2010]外星千足虫

tony102

2021 年 04 月 07 日

1885 次浏览

暂无评论

397字数

题解

[Link](https://www.luogu.com.cn/problem/P2447)

## Sol

bitset 优化高斯消元，是用来解异或方程组的。高斯消元需要钦定一个主元，然后逐一消去其他方程在该项，这样是 $O(n^3)$ 的，但是异或方程组直接异或把你选定的那个主元方程给它异或上去就可以了。其他的跟高斯消元一模一样

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 2e3 + 5;

int n, m;
std::bitset < SIZE > a[SIZE];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
	inline int readChar() {
		int c = fetch();
		while (c < '0' || c > '9') c = fetch();
		return c - 48;
	}
} using GTR::read; using GTR::readChar;

int main() {
	n = read() + 1, m = read();
	for (int i = 1; i <= m; ++ i) {
		for (int j = 1; j <= n; ++ j) a[i][j] = readChar();
	}
	int ans = 0;
	for (int i = 1, cur; i < n; ++ i) {
		cur = i;
		while (!a[cur][i] && cur <= m) ++ cur;
		ans = std::max(ans, cur);
		if (cur == m + 1) { puts("Cannot Determine"); return 0; }
		if (cur != i) std::swap(a[i], a[cur]);
		for (int j = 1; j <= m; ++ j) {
			if (i == j || !a[j][i]) continue;
			a[j] ^= a[i];
		}
	}
	printf("%d\n", ans);
	for (int i = 1; i < n; ++ i) puts(a[i][n] ? "?y7M#" : "Earth");
	return 0;
}
```

最后修改：2021 年 09 月 04 日