2721. 【SDOI2010】外星千足虫 题解

题目描述

题目描述

公元2089年6月4日，在经历了17年零3个月的漫长旅行后，“格纳格鲁一号”载人火箭返回舱终于安全着陆。此枚火箭由美国国家航空航天局（NASA）研制发射，行经火星、金星、土卫六、木卫二、谷神星、“张衡星”等23颗太阳系星球，并最终在小行星“杰森星”探寻到了地外生命。宇航员在“杰森星”地表岩层下45.70米位置发现一批珍贵的活体生命样本，并将其带回检测。在带回的活体样本中，最吸引人的当属这些来自外星的千足虫了。这些虫子身躯纤长，身体分为若干节。受到触碰时，会将身体卷曲成圆环形，间隔一段时间后才会复原活动。
　　有趣的还不止如此。研究人员发现，这些虫子的足并不像地球千足虫成对出现、总共偶数条——它们每节身体下方都有着不定数量的足，但足的总数一定是奇数条！虽然从外观难以区分二者，但通过统计足的数目，科学家们就能根据奇偶性判断出千足虫所属的星球。

作为J国派去NASA的秘密间谍，你希望参加这次研究活动以掌握进一步的情报，而NASA选拔的研究人员都是最优秀的科学家。于是NASA局长Charles Bolden出了一道难题来检测你的实力：
　　现在你面前摆有1…N编号的N只千足虫，你的任务是鉴定每只虫子所属的星球，但不允许亲自去数它们的足。Charles每次会在这N只千足虫中选定若干只放入“昆虫点足机”（the Insect Feet Counter, IFC）中，“点足机”会自动统计出其内所有昆虫足数之和。　　Charles会将这个和数mod 2的结果反馈给你，同时告诉你一开始放入机器中的是哪几只虫子。他的这种统计操作总共进行M次，而你应当尽早得出鉴定结果。

假如在第K次统计结束后，现有数据就足以确定每只虫子的身份，你就还应将这个K反馈给Charles，此时若K<M，则表明那后M－K次统计并非必须的。
　　如果根据所有M次统计数据还是无法确定每只虫子身份，你也要跟Charles讲明：就目前数据会存在多个解。

输入

输入文件insect.in第一行是两个正整数N, M。
　　接下来M行，按顺序给出Charles这M次使用“点足机”的统计结果。每行包含一个“01”串和一个数字，用一个空格隔开。“01”串按位依次表示每只虫子是否被放入机器：如果第i个字符是“0”则代表编号为i的虫子未被放入，“1”则代表已被放入。后面跟的数字是统计的昆虫足数mod 2的结果。
　　由于NASA的实验机器精确无误，保证前后数据不会自相矛盾。即给定数据一定有解。

输出

输出文件insect.out在给定数据存在唯一解时有N＋1行，第一行输出一个不超过M的正整数K，表明在第K次统计结束后就可以确定唯一解；接下来N行依次回答每只千足虫的身份，若是奇数条足则输出“?y7M#”（火星文），偶数条足输出“Earth”。如果输入数据存在多解，输出“Cannot Determine”。
　　所有输出均不含引号，输出时请注意大小写。

样例输入

输入1：

3 5
011 1
110 1
101 0
111 1
010 1

输出1：

4
Earth
?y7M#
Earth

输入2：

5 7
01100 1
11000 1
10100 0
11100 1
00011 1
00000 0
11111 0

输出2：

Cannot Determine

提示

【数据规模和约定】
　　对于20%的数据，满足N＝M≤20；
　　对于40%的数据，满足N＝M≤500；
　　对于70%的数据，满足N≤500，M≤1,000；
　　对于100%的数据，满足N≤1,000，M≤2,000。

前置知识：

高斯消元法解异或方程组
bitset 优化

1. 高斯消元法求解异或方程组

这个 oi-wiki 上面有，我就不详细介绍了

2. bitset 优化

bitset 实际上就是一个位压的 bool 数组，将很多的 0/1 压缩到一个 int / long long 里面，就像高精度乘法一样，比起普通的 bool 数组，这个快大约 $32$ 倍。

标准库的 bitset

详见 oi-wiki 的说明

手写 bitset

因为有时候因为各种原因无法调用标准库时，我们可以手写 bitset, 当然，使用普通的 bool 数组也可以
作者很慢的手写 bitset 代码

struct bitset {private:typedef long long Node_t;Node_t num[maxsize / (sizeof(Node_t) * 8 )];public:bitset() {memset(num, 0, sizeof(num));}bool operator[] (int x) {int id1 = x / (sizeof(Node_t) * 8);int id2 = x % (sizeof(Node_t) * 8);return (num[id1] & (1 << id2)) != 0; }void set(int pos, bool val = true) {int id1 = pos / (sizeof(Node_t) * 8); int id2 = pos % (sizeof(Node_t) * 8); if (val) num[id1] |= (1 << id2);else  num[id1] &= ~(1 << id2);}bool test(int x) {int id1 = x / (sizeof(Node_t) * 8);int id2 = x % (sizeof(Node_t) * 8); return (num[id1] & (1 << id2)) != 0; }int size() {return maxsize;}bitset<maxsize> operator ^ (const bitset<maxsize>& _p) {bitset<maxsize> ret;for (int i = 0; i < maxsize; ++i) ret.set(i, (*this)[i] ^ _p[i]);return ret;}bitset<maxsize> operator ^= (bitset<maxsize> _p) {for (int i = 0; i < maxsize; ++i) set(i, (*this)[i] ^ _p[i]);return *this;}
};

正题

我们设第 $i$ 次使用 “点足机” 时测量的足的的虫子编号为 $k_{i,1},k_{i,2},...,k_{i,q}$
再设地球的虫子的腿的个数为 $0$ 外星虫子的腿的个数为 $1$,
这是不影响后面的答案的，因为最后要$\mathrm{mod}2$

我们设 $x_i$ 为编号为 $i$ 的虫子的腿的个数，其中 $x\in [1,2]$

我们可以列出这样的一个方程组
$$\{\begin{array}{l}{\sum }_{i=1}^q{k}_{1,i}\times x_i=b_1(\mathrm{mod}2)(1)\\ \\ {\sum }_{i=2}^q{k}_{1,i}\times x_i=b_2(\mathrm{mod}2)(2)\\ \\ ...\\ {\sum }_{i=m}^{q}k+1,i\times x_i=b_3(\mathrm{mod}2)(m)\end{array}$$
现在我们的目标是求解这个模方程，但是我们使用 观察，注意，启示 大法后发现，题目中要我们使用高斯消元法求解这个问题，很明显，高斯消元法是无法求解模方程的，所以我们就要继续推理。

一个简单的例子
我们考虑模方程
$$\begin{gathered} a\times b=c(\mathrm{mod}2) \\ b\in 0,1 \end{gathered}$$
可以证明，再模 $2$ 意义下，我们发现了一个这样的等式
$a\times b=c$
和方程
$a⨁b=c$
的 $b$ 是同一个答案! （注 :$⨁$ 表示 C++ 中的异或，也就是 ‘^’）

所以我们就成功的将同余方程组改成了异或方程组，最后我们可以使用高斯消元法就可以求解了。

还有一个问题：
“第K次统计结束后就可以确定唯一解” 怎么处理呢?
我们可以使用一个 ans, 每次执行 ans = max(ans, cur) 即可！

完整代码(我手写的 bitset 超时了qwq)

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <algorithm>
#include <bitset>using namespace std;//namespace STL {
//	template <const int maxsize>
//	struct bitset {
//		private:
//			typedef int Node_t;
//			Node_t num[maxsize / (sizeof(Node_t) * 8 )];
//		public:
//			bitset() {memset(num, 0, sizeof(num));}
//			bool operator[] (int x) {
//				int id1 = x / (sizeof(Node_t) * 8);
//				int id2 = x % (sizeof(Node_t) * 8);
//				return (num[id1] & (1 << id2)) != 0; 
//			}
//			void set(int pos, bool val = true) {
//				int id1 = pos / (sizeof(Node_t) * 8); 
//				int id2 = pos % (sizeof(Node_t) * 8); 
//				if (val) num[id1] |= (1 << id2);
//				else  num[id1] &= ~(1 << id2);
//			}
//			bool test(int x) {
//				int id1 = x / (sizeof(Node_t) * 8);
//				int id2 = x % (sizeof(Node_t) * 8); 
//				return (num[id1] & (1 << id2)) != 0; 
//			}
//			int size() {return maxsize;}
//			bitset<maxsize> operator ^ (const bitset<maxsize>& _p) {
//				bitset<maxsize> ret;
//				for (int i = 0; i < maxsize; ++i) ret.set(i, (*this)[i] ^ _p[i]);
//				return ret;
//			}
//			bitset<maxsize> operator ^= (bitset<maxsize> _p) {
//				for (int i = 0; i < maxsize; ++i) set(i, (*this)[i] ^ _p[i]);
//				return *this;
//			}
//	};
//	template <class Tp> void swap(Tp& a, Tp& b) {Tp t = a;a = b;b = t;}
//	template <class Tp> Tp max(Tp a, Tp b) {return a > b ? a : b;}
//	template <class Tp> Tp min(Tp a, Tp b) {return a < b ? a : b;}
//}//using namespace STL;
const int N = 1024;
char buf[2048];bitset<N> jz[2048]; // 矩阵
int n, m;#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, a, b) for (int i = (a); i <= (b); i++)int ans = 0;
int guess(void) { // 高斯消元法REP(i, 1, n) { // n 个未知数个数int cur = i;while (cur <= m && !jz[cur].test(i)) cur++;if (cur > m) return false;ans = max(ans, cur);if (cur != i) swap(jz[cur], jz[i]);REP(j, 1, m) if (i != j && jz[j].test(i)) jz[j] ^= jz[i];}return true;
}
int main() {scanf("%d %d", &n, &m);REP(i, 1, m) {int x;scanf("%s %d", buf, &x);FOR(j, 0, n) jz[i].set(j + 1, (buf[j] == '1'));jz[i].set(0, x);}int ret = guess();if (!ret) return printf("Cannot Determine") & 0;printf("%d\n", ans);REP(i, 1, n) printf("%s\n", jz[i].test(0) ? "?y7M#": "Earth");
}

所以就写完了，qwq