SRM543 div.1 250 EllysXors
練習会に参加して、easyを100点くらいで通した。
問題
L, Rが与えられるので、L^(L+1)^...^(R-1)^R を求めよ。
制約
1 <= L <= R <= 4*10^9
解法
XORの性質より、二進表記でi桁目が1になるかどうかは、LからRの間の数で、i桁目が1となる数の個数の偶奇で決まる(偶数個の場合0で奇数個の場合1)。よって、各桁について、1が立っている数の個数が計算できればよい。
ここで、1からNまでで各桁について合計何個1が立っているかを考える。このとき、2^i-1となる数は、各桁で1が立っている数の個数はそれぞれ2^(i-1)個であることを考えると、2^i+jは最上位桁は1がj+1個で、それ以外の桁は、2^i-1の個数とjの個数の和となることがわかる。よって再帰的に個数を計算できる。
1からNまで求められれば、1からRまでを求め、1からL-1のときを引いて、各桁の1の個数の偶奇から答えを求めればよい。
計算量
O(log^2 R)
コード
別解法
4n^(4n+1)^(4n+2)^(4n+3)=0を利用する(4nが、nを2ビット左シフトした数だということを考えればわかる)。
f(N)=1^2^...^Nとすると、上式より、N=4k+mとすると、
m=0のときf(N)=(1^2^3)^(4^5^6^7)^...^4k=0^0^..^4k=4k=N
m=1のときf(N)=4k^(4k+1)=1
m=2のときf(N)=4k^(4k+1)^(4k+2)=4k+3=N+1
m=3のときf(N)=4k^(4k+1)^(4k+2)^(4k+3)=0
となり、あとはR^(R+1)^...^L=f(L)^f(R-1)を利用して求めればよい。
感想
- 練習会中はなぜか上で書いたビットを数える関数が上手く書けず、実験したら別解法の法則をたまたま見つけたのでそれで書いた
- 後者は頭の良い解法だが、前者はandやorの場合にも応用できるので、さっと書けるようにしておきたい
各ビットごとに何個1があるかを数える関数が書けなかったのは思考力足りてないし、その方針で上手く書けなかった時点で実験やらなかったのは判断力不足だし、まだまだ黄色に上がるのは先かなあという感じ
— くぬう (@n_knuu6) 2016年4月22日