Codeforces #285 Div1 D. Misha and XOR

これは本番評判悪かったな…。
http://codeforces.com/contest/504/problem/D

問題

M個の整数V[i]が順に与えられる。
V[i]がV[0]～V[i-1]のうち任意個のxorを取った値で表現できるか答えよ。

なお、V[i]は10^600未満である。

解法

10^600≒2^2000なので、V[i]は２進数で2000桁以内である。(D=2000とする)
よって各V[i]をD次元のGF(2)からなるべクトルと考え、V[i]がV[0]～V[i-1]の線形結合で表現できるか計算すればよい。
これは単に掃出し法で行うことができる。

このままだとO(M^2*D)かかりTLEするが、数十個分のベクトルを1つの64bit値でまとめて処理すれば間に合う。

int N;
ll V[2001][70];
ll sel[2001][70];
int bm[2002];

void conv(int cur,string s) {
	int i,j;
	ll v[105]={};
	FOR(i,100) {
		v[i]+=(s[i*6+5]-'0')*100000;
		v[i]+=(s[i*6+4]-'0')*10000;
		v[i]+=(s[i*6+3]-'0')*1000;
		v[i]+=(s[i*6+2]-'0')*100;
		v[i]+=(s[i*6+1]-'0')*10;
		v[i]+=(s[i*6+0]-'0')*1;
	}
	FOR(i,2000) {
		V[cur][i/32] |= (v[0]&1)<<(i%32);
		FOR(j,100) v[j]=(v[j]>>1) + ((v[j+1]&1)*500000);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(bm);
	
	cin>>N;
	FOR(i,N) {
		cin>>s;
		
		reverse(s.begin(),s.end());
		s=s+string(601,'0');
		conv(i,s.substr(0,600));
		sel[i][i/32]=1LL<<(i%32);
		
		for(j=1999;j>=0;j--) if(V[i][j/32]&(1LL<<(j%32))) {
			if(bm[j]>=0) {
				FOR(x,70) V[i][x] ^= V[bm[j]][x];
				FOR(x,70) sel[i][x] ^= sel[bm[j]][x];
			}
			else {
				_P("0\n");
				bm[j]=i;
				break;
			}
		}
		
		if(j==-1) {
			y=0;
			FOR(x,70) y+=__builtin_popcountll(sel[i][x]);
			_P("%d",y-1);
			FOR(x,i) if(sel[i][x/32]&(1LL<<(x%32))) _P(" %d",x);
			_P("\n");
		}
	}
	
}

まとめ

本番「O(M^2*D)は多少パッキングして30倍速くしても間に合わないだろう」と思って実行しなかったが、それ想定解だったのか…。