yukicoder : No.911 ラッキーソート

まぁこれはすんなりかな。
https://yukicoder.me/problems/no/911

問題

N要素のdistinctな整数列Aが与えられる。
L以上R以下の整数xのうち、Aの各要素とxor xを取って得られる数列が、単調増加になるものは何通りか。

解法

f(x) := x以下の正整数のうち、Aの各要素とxor xを取って得られる数列が、単調増加になるものの組み合わせ
とすると、求めたいのはf(R)-f(L-1)である。あとはf(x)を考えよう。

単調増加の条件から、A[i] xor x ＜ A[i+1] xor xでなければならない。
よって、A[i]とA[i+1]の2進数表記を上から見比べた場合、初めて差異があるbitを2^pとすると、xにおいて2^pの桁が0か1かどちらでないといけないかが確定する。
これを隣接要素において行うと、xの各桁について

• 0でなければならない
• 1でなければならない
• 0でも1でもどちらでもよい

のいずれかになる。(前者2パターンが両方現れる場合があるが、この場合f(x)=0となる）。

あとはx以下で上記条件を満たすものを数え上げればf(x)が求まるが、これは単純な桁DPである。
「今より下位の桁に確定済み桁が何個あるか」を持って上の桁から0,1定めていけばよい。

int N;
ll L,R;
ll A[202020];
int mask[62];

ll hoge(ll v,int d,int fix) {
	if(d<0) return 1;
	
	ll ret=0;
	if(mask[d]==0) {
		
		if(v&(1LL<<d)) {
			ret+=1LL<<(d-fix);
			v ^= 1LL<<d;
		}
		ret+=hoge(v,d-1,fix);
	}
	else if(mask[d]==1) {
		fix--;
		if(v&(1LL<<d)) {
			ret+=1LL<<(d-fix);
		}
		else {
			ret+=hoge(v,d-1,fix);
		}
	}
	else if(mask[d]==2) {
		fix--;
		if(v&(1LL<<d)) {
			v ^= 1LL<<d;
			ret+=hoge(v,d-1,fix);
		}
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L>>R;
	FOR(i,N) cin>>A[i];
	FOR(i,N-1) {
		for(j=61;j>=0;j--) {
			if((A[i]&(1LL<<j)) && (A[i+1]&(1LL<<j))==0) {
				mask[j] |= 2;
				break;
			}
			if((A[i]&(1LL<<j))==0 && (A[i+1]&(1LL<<j))) {
				mask[j] |= 1;
				break;
			}
		}
	}
	int fix=0;
	FOR(j,62) {
		if(mask[j]==3) return _P("0\n");
		if(mask[j]) fix++;
	}
	cout<<hoge(R,61,fix)-(L?hoge(L-1,61,fix):0)<<endl;
	
}

まとめ

ちょっとややこしい桁DPだけど、問題設定がシンプルなのは良いね。