ようやく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; }
まとめ
若干状態遷移がややこしいけど、まぁ普通に解けてよかった。