yukicoder : No.2483 Yet Another Increasing XOR Problem

方針立ってもきれいに書くの難しいな。
https://yukicoder.me/problems/no/2483

問題

整数Mが与えられる。
M未満の非負整数Aの数列を考えたとき、xorに関するprefix sumを取った数列Bが真に単調増加となるのは何通りか。

解法

(M-1)の最上位桁を2^Dの桁とする。

下記2パターンは容易に計算できる。

• Bがすべて2^D未満の場合、Bは0～(2^D-1)の任意の値を昇順に並べた数列を取れる。
• Bがすべて2^D以上(2^(D+1)未満)の場合、Bは初項は2^D以上M未満で、以降2^(D+1)未満の値を任意に昇順に並べた値を取れる。

残るパターンBが、2^D未満の値t,uを用いて、t→(u xor 2^D)に遷移することを考える。
t以前の値はt未満の値を任意にとれるし、(u xor 2^D)以降の値は、2^(D+1)未満の値を任意にとれる。
すなわち(t,u)の対に対し2^*1の総和を取ったものを数え上げればよい。
uはM-(2^D)未満でないといけない。
上の桁から、uを0/1それぞれ取ったときのパターンを数え上げて行こう。

ll M;
const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M;
	M--;
	
	if(M==0) {
		cout<<1<<endl;
		return;
	}
	
	int D=0;
	while(1LL<<(D+1)<=M) D++;
	ll ret=0;
	
	// D bitが立たない
	ret+=modpow(2,1LL<<D)-1;
	// D bitが立つ
	ret+=modpow(2,1LL<<D)-modpow(2,(2LL<<D)-M-1)+mo;
	ret%=mo;
	ll sum=modpow(2,(1LL<<D)-1);
	for(i=D-1;i>=0;i--) {
		if(M&(1LL<<i)) {
			
			(ret+=sum*2*(modpow(2,1LL<<i)-1)%mo*(modpow(2,1LL<<i)-1)%mo*modpow(modpow(2,(1LL<<i)-1)))%=mo;
			sum=sum*(modpow(2,1LL<<i)+modpow(modpow(2,1LL<<i)))%mo;
		}
		else {
			sum=sum*2%mo;
		}
	}
	ret+=sum;
	cout<<ret%mo<<endl;
	
}

まとめ

結果的にコードは余り長くないけど、うまく(t,u)のパターンを数え上げるのにちょっと頭使った。

*1:2^D)-1+t-(t xor u