Codeforces 388(#228 Div1) D. Fox and Perfect Sets

問題

集合Sがperfectであるとは、任意の（同一でもよい）a, b∈Sについて、
(a xor b)∈Sとなることを言うものとする。

全ての要素がk以下であるようなSの選び方は何通りあるか、
mod 10^9 + 7で求めよ。

制約条件

k≦10^9

方針

editorialみた。

Sに要素を追加していくことを考えるとき、
今までのSの要素のどれでもないものをc入れれば、
a, b∈Sでa xor c = bとなるものは絶対にない。あったらa xor b = cとなってしまうから。

この新たに追加する要素というのはSの基底であると考えることができる。
ので、一つのSには一つの線形空間が一対一で対応していると言える。

Sに（上位ビットから順に考えて）基底を追加していくことを考える。
今までj本の基底を入れたとする。
i番目のビットを最上位ビットとする基底を入れるとき、
その基底のi番目のビットは1で、ほかの基底のi番目のビットは0にする。
基底を入れないとき、他の基底のi番目のビットは自由に選んでよいので2^j通り。

基底を決めたときにできる最大のベクトルを求めるのは簡単で、
i番目のビットが最上位ビットである基底があったらそのビットは1
なかったら、2^j / 2通りがそのビットを1にする基底で、2^j / 2通りがそのビットを0にする基底。

以上を元に桁DPをすればいい。
j = 0の場合だけは例外で、そのビットを1にする基底は存在しない。

ソースコード

const int mod = (int)1e9 + 7;
ll k, dp[40][40][2];

int main(){
	cin >> k;
	dp[39][0][0] = 1;
	
	for(int i = 38; i >= 0; i--) rep(j, 40) rep(s, 2){
		
		ll cur = dp[i + 1][j][s];
		if(!cur) continue;
		
		if(s || (k >> i & 1)) (dp[i][j + 1][s] += cur) %= mod;
		if(j == 0){
			dp[i][j][s || (k >> i & 1)] += cur;
			dp[i][j][s || (k >> i & 1)] %= mod;
			continue;
		}
		rep(l, 2){
			if(!s && (k >> i & 1) < l) continue;
			int ns = s || (k >> i & 1) > l;
			dp[i][j][ns] += cur * (1 << j - 1) % mod;
			dp[i][j][ns] %= mod;
		}
	}
	ll ans = 0;
	rep(i, 40) ans += dp[0][i][0] + dp[0][i][1];
	cout << ans % mod << endl;
	return 0;
}