P2447 [SDOI2010]外星千足虫 (高斯消元)

时间:2021-10-08 07:04:00

题目

P2447 [SDOI2010]外星千足虫

解析

sol写到自闭,用文字描述描述了半个小时没描述出来,果然还是要好好学语文

用高斯消元求解异或方程组。

因为

  • \(奇数\bigoplus奇数=偶数\)
  • \(偶数\bigoplus偶数=偶数\)
  • \(奇数\bigoplus偶数=奇数\)

\(0\)为偶数,\(1\)为奇数,

  • \((奇数+奇数)\mod 2=0\)
  • \((偶数+偶数)\mod 2=0\)
  • \((奇数+偶数)\mod 2=1\)

若把第一个里面的奇偶数分别换成\(1\)和\(0\),则对于\((x_1+x_2)\bmod 2\)的操作,可以看做异或操作(\(x_1\bigoplus x_2\))。

易证,\((x_1+x_2+x_3+···+x_n)\mod 2 = x_1\bigoplus x_2\bigoplus x_3 \bigoplus ···\bigoplus x_n\)。

对于主元所在的列,我们只让主元行上的数为\(1\),其余的为\(0\),于是我们让每一行与当前主元行比较,若某一行的这个数为\(1\),就让这一行异或主元行。

因为我们之前处理当前主元行以上的内容时,把除了当时主元行上的所有当时主元所在列上的数都异或成了\(0\),所以我们当前主元行主元之前的数都为0,根据异或的性质,发现当前主元行前面的\(0\)对之前处理的行没有影响,这样更新到最后,我们会得到一个单位矩阵,

其实手动一模拟就出来了。。

如$$\begin{bmatrix}

0&1&1&\mid&1\

1&0&1&\mid&0\

0&0&1&\mid&1

\end{bmatrix}

\to\begin{bmatrix}

1&0&1&\mid&0\

0&1&1&\mid&1\

0&0&1&\mid&1

\end{bmatrix}

\to\begin{bmatrix}

1&0&0&\mid&1\

0&1&0&\mid&0\

0&0&1&\mid&1

\end{bmatrix}\$$

于是就得到了答案。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
bitset<N> a[N];
char s[N];
int n, m, ans; template<class T>inline void read(T &x) {
x = 0;int f = 0;char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'),ch = getchar();
while(isdigit(ch)) x = x * 10 + ch -'0',ch = getchar();
x = f ? -x : x;
return ;
} void Gauss() {
for (int i = 1; i <= n; ++i) {
int k = i;
while (!a[k][i] && k <= m) k++;
if (k == m + 1) {
ans = -1;
return;
}
ans = max(ans, k);
if (k != i) swap(a[k], a[i]);
for (int j = 1; j <= m; ++j)
if (j != i && a[j][i]) a[j] ^= a[i];
}
return;
} int main() {
read(n), read(m);
for (int i = 1, x; i <= m; ++i) {
scanf("%s", s);
for (int j = 0; j < n; ++j) a[i][j + 1] = s[j] - '0';
read(x);
a[i][n + 1] = x;
}
Gauss();
if (ans == -1) printf("Cannot Determine\n");
else {
printf("%d\n", ans);
for (int i = 1; i <= n; ++i)
printf(a[i][n + 1] == 1 ? "?y7M#\n" : "Earth\n");
}
return 0;
}