Codeforces #228 Div1. D. Fox and Perfect Sets

これは考察が難しいのか正答者少ないけど、コードは短いのよね。
http://codeforces.com/contest/388/problem/D

問題

非負整数からなる非零集合Sがperfectであるとは、a,b∈Sであるa,bに対し(a xor b)∈Sである事と定義する。
k以下の整数だけからなるperfectな集合はいくつあるか。

解法

この問題は整数をbit vectorで表現するとき、複数のベクトルをxorで結合してもk以下に収まるような基底ベクトル群を何通りとれるか、という問題に置き換えられる。
dp[残り桁数][vector数][0,1任意に取れるか] := 条件を満たす組み合わせ数
として、上のbitから順に、新規vectorの最上位bitにするか、もしくは既存のvectorのいくつかに組み込むかをDFSでメモ化再帰していく。

既存のvectorのいくつかに組み込むかについて、このbitがvectorの結合で1になってよいなら、2^(vector数)通り選択できるが、1になっては困る(結合後kを超える可能性がある)なら2^(vector数-1)通りしか選択できない。

ll N;
ll mo=1000000007;
ll memo[32][32][3];

ll dfs(int dig,int vec,int any) {
	if(dig<0) return 1;
	ll& ret=memo[dig][vec][any];
	if(ret>=0) return ret;
	bool any2=(N&(1LL<<dig))!=0;
	ret = 0;
	// new vector
	if(any||any2) ret += dfs(dig-1,vec+1,any);
	
	if(vec==0) {
		ret += dfs(dig-1,vec,any||any2);
	}
	else {
		// not take
		ret += dfs(dig-1,vec,any || any2) * (1LL<<(vec-1));
		if(any||any2) ret += dfs(dig-1,vec,any) * (1LL<<(vec-1));
	}
	return ret%=mo;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	MINUS(memo);
	cout<<dfs(30,0,0)%mo<<endl;
}

まとめ

この回はBもCも落としてるので、そもそもDに挑む以前の問題。