### Andrew Stankevich’s Contest #9解题报告 » ZOJ2700

ZOJ2700.cpp

```#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 150;	// !!128!!WA!!

struct BPolynomial : vector<bool> {
bool read(FILE* fp = stdin) {
int n;
if (fscanf(fp, "%d", &n) == EOF) {
return false;
}
resize(n + 1);
for (BPolynomial::reverse_iterator i = rbegin(); i != rend(); ++i) {
fscanf(fp, "%d", &n);
*i = (n != 0);
}
return true;
}

void write(FILE* fp = stdout) const {
if (empty()) {
fputs("-1", fp);
} else {
fprintf(fp, "%d ", (int)size() - 1);
for (BPolynomial::const_reverse_iterator i = rbegin(); i != rend(); ++i) {
fputs(*i ? " 1" : " 0", fp);
}
fputc('\n', fp);
}
}

bool operator[](int i) const {
return 0 <= i && i < (int)size() ? vector<bool>::operator[](i) : false;
}

void trim() {
while (!(empty() || back())) {
pop_back();
}
}
};

bool solve(int m, int n, bool a[MAXN * 3][MAXN], bool b[MAXN * 3], bool y[MAXN]) {
static int p[MAXN * 3];
int r = 0, c = 0;
/*
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
putchar('0' + a[i][j]);
}
putchar('=');
putchar('0' + b[i]);
puts("");
}
puts("=");
*/
while (r < m && c < n) {
int rr = -1;
for (int i = r; i < m; ++i) {
if (a[i]1) {
rr = i;
break;
}
}
if (rr != -1) {
for (int j = c; j < n; ++j) {
swap(a[r][j], a[rr][j]);
}
swap(b[r], b[rr]);
for (int i = r + 1; i < m; ++i) {
if (a[i]1) {
a[i]1 = false;
for (int j = c + 1; j < n; ++j) {
if (a[r][j]) {
a[i][j] = !a[i][j];
}
}
if (b[r]) {
b[i] = !b[i];
}
}
}
p[r] = c;
++r;
}
++c;
}

/*
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
putchar('0' + a[i][j]);
}
putchar('=');
putchar('0' + b[i]);
puts("");
}
puts("=");
*/
for (int i = r; i < m; ++i) {
if (b[i]) {
return false;
}
}

c = n - 1;
for (int i = r - 1; i >= 0; --i) {
while (c > p[i]) {
y1 = false;
}
y1 = b[i];
for (int j = n - 1; j > c; --j) {
y1 ^= a[i][j] && y[j];
}
--c;
}
while (c >= 0) {
y1 = false;
}
return true;
}

int main() {
BPolynomial a, b, c;
bool x[MAXN * 3][MAXN], y[MAXN * 3], z[MAXN];
int m, n;

n = max(a.size(), max(b.size(), c.size()));
m = 3 * n;
for (int i = 0; i <= m; ++i) {
for (int j = 0; j <= n; ++j) {
x[i][j] = a[i - 2 * j] ^ b[i - j];
}
y[i] = c[i];
}

if (solve(m + 1, n + 1, x, y, z)) {
BPolynomial ans;
ans.insert(ans.end(), z, z + n + 1);
ans.trim();
ans.write();
} else {
puts("no solution");
}
puts("");
}
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name
//2176431 	2010-04-25 14:56:48 	Accepted 	2700 	C++ 	40 	180 	watashi@Zodiac
```