1315.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1315 on 2006-02-02 at 12:57:49 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 256;

class BitVector {
public:
	int bit[MAX], msb;
	void clear();
	void set(const int);
	int elementAt(const int) const;
	void operator -=(const BitVector&);
};
void BitVector::clear() {
	memset(bit, 0, sizeof(bit));
}
void BitVector::set(const int index) {
	bit[index>>3] ^= 1 << (index&7);
}
int BitVector::elementAt(const int index) const {
	return (bit[index>>3]>>(index&7))&1;
}
void BitVector::operator -=(const BitVector& bv) {
	int i;
	for(i = bv.msb; i >= 0; i--)
		if(bv.elementAt(i) != 0) set(i+msb-bv.msb);
	while(msb >= 0 && elementAt(msb) == 0) msb--;
}

int main()
{
	BitVector fg, h;
	int t, T, i, j;
	int d[3], coe[3][1024];
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		fg.clear(); h.clear();
		for(i = 0; i < 3; i++) {
			scanf("%d", &d[i]);
			for(j = 0; j < d[i]; j++) scanf("%d", &coe[i][j]);
		}
		fg.msb = d[0] + d[1] - 2; h.msb = d[2] - 1;
		for(i = 0; i < d[0]; i++)
			for(j = 0; j < d[1]; j++)
				if(coe[0][i]*coe[1][j] != 0) fg.set(fg.msb-i-j);
		for(i = 0; i < d[2]; i++)
			if(coe[2][i] != 0) h.set(h.msb-i);
		while(fg.msb >= h.msb) fg -= h;
		printf("%d", fg.msb+1);
		for(i = fg.msb; i >= 0; i--) printf(" %d", fg.elementAt(i));
		putchar('\n');
	}
	
	return 0;
}