AtCoder ARC #066 : D - Xor Sum

ようやくARCは全完に戻せた。あとはAGC…。
http://arc066.contest.atcoder.jp/tasks/arc066_b

問題

整数Nが与えられる。0≦u,v≦Nを満たす整数u,vで、非負整数a,bを用いてa xor b = u、a + b = vと表せるようなものの個数を求めよ。

解法

2進数表記で、上からu,vの各桁の0,1を決めていくメモ化再帰を行う。
f(d, xp, ap) := 下から(d+1)桁より上が決まっている状態で、残り下位d桁の決め方が何通りあるか。なおxp,apはそれぞれxorおよび加算において上位桁のあまりの有無を示す。
xpは0か1か、apは0か1か2かだけ考えればよい。

あとは、u,vのd桁目が(0,0)、(1,0)、(1,1)である場合を順次考えていけばよい。

ll N;
ll memo[77][5][5];
ll mo=1000000007;

ll dfs(int d,int xm,int am) {
	if(d<0) return 1;
	if(memo[d][xm][am]>=0) return memo[d][xm][am];
	
	ll ret=0;
	// 0 0
	if(N&(1LL<<d)) {
		ret += dfs(d-1,1,min(2,am*2+1));
	}
	else {
		ret += dfs(d-1,xm,min(2,am*2));
	}
	// 1 0
	if(N&(1LL<<d)) {
		ret += dfs(d-1,xm,min(2,am*2));
	}
	else {
		if(am && xm) ret += dfs(d-1,xm,min(2,am*2-1));
	}
	// 1 1
	if(am) {
		if(N&(1LL<<d)) {
			ret += dfs(d-1,1,min(2,am*2-1));
		}
		else {
			ret += dfs(d-1,xm,min(2,am*2-2));
		}
	}
	
	return memo[d][xm][am]=ret%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	MINUS(memo);
	cout<<dfs(60,0,0)<<endl;
	
	
}

まとめ

若干状態遷移がややこしいけど、まぁ普通に解けてよかった。