TopCoder SRM 564 Div1 Hard DefectiveAddition

SRM564はDiv1 Hardだけど850ptと割と低めなのでチャレンジしてみた。
http://community.topcoder.com/stat?c=problem_statement&pm=12346

問題

整数値の配列が与えられる。
この配列の各要素に対し、0～要素の間で整数値を選んで全要素分XORを取ったとき、その値がNになる組み合わせ数を返す。

解法

まず配列をソートしておき、最大値の最上位ビットMを計算しておく。
本番に思ったのは、「Nがこの(1<

ll MO=1000000007;

class DefectiveAddition {
	int msb;
	public:
	
	int count(vector <int> cards, int n) {
		int i,msb=0;
		int N=cards.size();
		vector <int> C=cards;
		
		sort(C.begin(),C.end());
		while(1<<(msb+1)<=C[N-1]) msb++;
		
		if(n>=1<<(msb+1)) return 0;
		
		// N-1個で1<<msb以上を作るパターン
		ll DP[52][2];
		ZERO(DP);
		DP[0][0]=1;
		FOR(i,N-1) {
			if(C[i]>=1<<msb) {
				DP[i+1][0]=(DP[i][1]*(C[i]+1-(1<<msb)) + DP[i][0]*(1<<msb)) % MO;
				DP[i+1][1]=(DP[i][0]*(C[i]+1-(1<<msb)) + DP[i][1]*(1<<msb)) % MO;
			}
			else {
				DP[i+1][0]=(DP[i][0]*(C[i]+1)) % MO;
				DP[i+1][1]=(DP[i][1]*(C[i]+1)) % MO;
			}
		}
		ll res = DP[N-1][n>=(1<<msb)];
		if(C[N-1]>=1<<msb) {
			C[N-1] -= 1<<msb;
			res = (res + count(C,n^(1<<msb))) % MO;
		}
		
		return res;
	}

};

まとめ

出だしの「最後の数でいかようにも調節できる」まで思いついたは良かったけど、再帰で処理する部分が思いつかなかった。
この問題は別の場所で出たことあるらしいけど、面白い問題だね。