TopCoder SRM 590 Div1 Medium XorCards

本番に詰め切れなかった問題。
本番は「連立方程式を何度も解けばよさそう。久々にガウスの掃出し法とか使うのかな。でも解が１個じゃないよな、どーすんだ…」で時間切れ。
http://community.topcoder.com/stat?c=problem_statement&pm=12079

問題

N個の非負整数が与えられる。
これらのうちいくつかを選んでxorをとったとき、その値がLimit以下になる選び方は何通りあるか答えよ。

解法

Limitを２進数表記して1101000の時、xorをとった答えがたとえば1100xxxのように途中まではLimitと同じbitが立っていて、途中で1→0となる場合、より下の桁の数値が何であれLimitを下回る。

この事実より、Limitのi bit目が1だったとき、(i+1)bit目以上がLimitと一致ち、i bit目が0になるような組み合わせの数を各iについて加算すればよいことがわかる。
(あとxorが0になる場合も忘れずに)

i bit目以上の各bitについて、各数値を採用するかどうかで連立方程式が立てられる。
A[j][i] = j番目の数値のi bit目の値、X[j] = j番目の数値を選択するかどうか、L[i] = Limitのi bit目の値、とすると各i bit目について
A[0][i]*X[0] xor A[1][i]*X[1] xor ... xor A[N-1][i]*X[N-1] = L[i]
という連立方程式が立つ。

あとはこの連立方程式の解があり、かつその組み合わせ数を求めればよい。
結論から言うと、この方程式の解があれば、解空間が(N-rank(A) )次なので組み合わせ数はとなる。
rankはガウスの掃出し法で求めればよい。途中で左辺の変数が全部消えても右辺が1になったら、その方程式は解なしといえる。

以下のコードでは、A,X,Lはそれぞれ0か1なので、bitmapにして簡単に計算している。

ll mask[61],mask2[61];

ll gause(int R) {
	int rank=0,i,x;
	ll mb;
	
	while(R>0) {
		sort(mask2,mask2+R);
		if(mask2[R-1]==0) break;
		if(mask2[R-1]==1) return -1;
		//_P("%d %d\n",R,rank);
		rank++;
		mb=1LL<<63;
		while((mask2[R-1] & mb)==0) mb>>=1;
		
		FOR(i,R-1) if(mask2[i]&mb) mask2[i] ^= mask2[R-1];
		R--;
	}
	return rank;
	
}

class XorCards {
	int N;
	public:
	long long numberOfWays(vector<long long> number, long long limit) {
		int i,j,bi;
		ll mask[60];
		N=number.size();
		sort(number.begin(),number.end());
		ll ret=0;
		
		ZERO(mask);
		FOR(i,N) FOR(bi,60) if(number[i] & (1LL<<bi)) mask[59-bi] |= 1LL<<(i+1);
		FOR(bi,60) if(limit & (1LL<<bi)) mask[59-bi] |= 1;
		
		FOR(bi,60) {
			if(mask[bi]&1) {
				FOR(i,60) mask2[i]=mask[i];
				mask2[bi]^=1;
				i = gause(bi+1);
				if(i>=0) ret += 1LL<<(N-i);
			}
		}
		FOR(i,60) mask2[i]=mask[i];
		i = gause(60);
		if(i>=0) ret += 1LL<<(N-i);
		
		return ret;
	}
};

まとめ

連立方程式を解け、という問題は割と珍しいようだ。
今回は係数が0か1なので簡単だけどね。

本番そこまではよかったし、解の数を求めるのにRankとか使うのかな？までは思いついたけど、そこから通りと出す部分ができなかった。
うーん、もう少し。