AtCoder ABC #129 : E - Sum Equals Xor

ちょっと考慮漏れしてタイムロスした。
https://atcoder.jp/contests/abc129/tasks/abc129_e

問題

ある大きな2進数Lが与えられる。
A + B ≦ LかつA xor B = A + BとなるA,Bの対は何通りか。

解法

A+B=A xor Bより、2進数表記のどこかの桁でA,Bともに1となるようなことはない。

A+BとLを2進数で上の桁から見ていって、ある桁(下から0-indexでd桁目)でLの方が大きくなるケースを考えよう。
d桁目より上は、A+BとLは一致するので、d桁目より上にp個1があった場合、AとBどちらがその桁に1が立つので、組み合わせは2^p通り。
逆にd桁目より下はA+Bは0でも1でもいいので、各桁A,Bの組み合わせは(0,0),(1,0),(0,1)の3通りある。
よって(2^p)*(3^q)を通り。
dを端から舐めながらp,qを更新していけばよい。
また、A+B=Lのケースも忘れないようにする。

string L;
int N;
ll mo=1000000007;
ll S[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L;
	L="0"+L;
	N=L.size();
	ll ret=0;
	ll v=1,a=1;
	
	int c=1;
	S[0]=1;
	FOR(i,N) {
		S[i+1]=S[i];
		if(L[i]=='1') S[i+1]=S[i+1]*2%mo;
	}
	
	for(i=N-1;i>=1;i--) {
		if(L[i]=='1') {
			v=v*2%mo;
			ret+=a*S[i]%mo;
		}
		a=a*3%mo;
	}
	ret+=v;
	cout<<(ret%mo)<<endl;
}

まとめ

先にd桁より下に意識が行き過ぎて、上を処理するの忘れた。