yukicoder : No.2061 XOR Sort

コードは短め。
https://yukicoder.me/problems/no/2061

問題

整数列Aが与えられる。

これらを以下の手順を繰り返してソートすることを考える。

• 非負整数Xを選ぶ。
• Aの各要素を、A[i]=A[i] xor Xで上書きする
• Aをソートする
• Aの各要素を、A[i]=A[i] xor Xで上書きする

これで構成できるAは何通りか。

解法

X=0とすると普通のソートができるので、まず普通のソートを行う。
以後、隣接要素A[i],A[i+1]同士の大小関係が反転する条件は、A[i]とA[i+1]の2進数表記で、値が異なるbitが1であるようなXを選択した場合である。
隣接要素毎に、そのような最小のbitを求め、それらのbitwise-orを取りその値をYとする。

それらのbitをXに入れるかどうかで、ある隣接要素の大小関係が新規に反転する。
よって、2^bitcount(Y)が解。

int N;
ll A[202020];
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
	}
	sort(A,A+N);
	ll a=0;
	FOR(i,N-1) {
		for(j=30;j>=0;j--) {
			if((A[i]&(1<<j))!=(A[i+1]&(1<<j))) {
				a|=1<<j;
				break;
			}
		}
	}
	
	ll ret=1;
	FOR(i,30) if(a&(1<<i)) ret=ret*2%mo;
	cout<<ret<<endl;
	
}

まとめ

こういうの本番思いついてさっと解けるか、変にはまって手間取るか、考察時間が読めないな・・。