Codeforces Global Round 11 : E. Xum

あまり自信がないまま通してしまった。
https://codeforces.com/contest/1427/problem/E

問題

正の奇数Nに対し、初期状態として集合S={N}が与えられる。
Sの2要素x,yを取り出し(x=yでもよい)、(x+y)か(x^y)をSに加えることを繰り返す。
Sに1を含めるための構築順を1つ示せ。

解法

以下は確証がなく行っている。
Nに対し、Nの倍数とNの2の累乗を適当にSに追加し、掃き出し法の要領で基底bitvectorを求め、1が作れるか判定する。
もし作れない場合、Nに最小の基底を加算することでNをちょっと大きくして、同じことを繰り返したら通った。

vector<vector<ll>> X;
set<ll> S;

vector<ll> add(vector<ll> T,ll v) {
	S.insert(v);
	FORR(t,T) {
		if((t^v)<v) {
			if(S.count(t^v)==0) {
				X.push_back({t,v,1});
				S.insert(t^v);
			}
			v^=t;
		}
	}
	if(v) {
		ll msb=1;
		while(msb<<1 <= v) msb<<=1;
		FORR(t,T) if(t&msb) {
			if(S.count(t^v)==0) {
				X.push_back({t,v,1});
				S.insert(t^v);
			}
			t^=v;
		}
		T.push_back(v);
		sort(ALL(T));reverse(ALL(T));
	}
	return T;
}

ll N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	vector<ll> V;
	
	while(S.count(1)==0) {
		for(i=1;i<=100;i++) {
			V.push_back(N*i);
			if(i>1 && S.count(N*i)==0) X.push_back({N*(i-1),N,0});
			S.insert(N*i);
		}
		if((N&(N+1))==0) {
			V.push_back(N^(2*N));
			S.insert(N^(2*N));
			X.push_back({N,2*N,1});
			N+=2;
			continue;
		}
		for(i=1;i<=20;i++) {
			V.push_back(N<<(i-1));
			if(i>1 && S.count(N<<(i-1))==0) X.push_back({N<<(i-2),N<<(i-2),0});
			S.insert(N<<(i-1));
			V.push_back(N+(N<<(i-1)));
			S.insert(N+(N<<(i-1)));
			X.push_back({N<<(i-1),N,0});
		}
		vector<ll> T;
		sort(ALL(V));
		reverse(ALL(V));
		FORR(v,V) T=add(T,v);
		V=T;
		sort(ALL(V));
		if(count(ALL(V),1)) {
			break;
		}
		if(S.count(N+V[0])==0) {
			X.push_back({N,V[0],0LL});
			S.insert(N+V[0]);
		}
		N+=V[0];
		while(N%2==0) {
			if(S.count(N+V[0])==0) {
				X.push_back({N,V[0],0LL});
				S.insert(N+V[0]);
			}
			N+=V[0];
		}
		
		
	}
	//return;
	assert(S.count(1));
	cout<<X.size()<<endl;
	FORR(a,X) {
		if(a[2]==0) cout<<a[0]<<" + "<<a[1]<<endl;
		if(a[2]==1) cout<<a[0]<<" ^ "<<a[1]<<endl;
	}
}

まとめ

まぁ本番は一応Nを全通りチェックしたので、通ること自体は自信があったけども、この方式が適切かは自信がなかった。