n-knuu's logs

憧れ駆動。だいたい競プロ

SRM543 div.1 250 EllysXors

topcoder

練習会に参加して、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の場合にも応用できるので、さっと書けるようにしておきたい