2019年3月9日土曜日

ABC 121 D - XOR World

ABC 121 D - XOR World

各桁の11の数を数えればO(logn){\mathcal O}(\log n)で解ける。この際、g(x)=f(0,x)g(x) = f(0, x)が求まればf(x,y)=g(y)g(x1)f(x, y) = g(y) \oplus g(x-1)と書けるので、各桁ごとの偶奇の判定がだいぶ簡単になる。

任意のn2Nn \in 2{\mathbb N}についてn(n+1)=1n \oplus (n+1) = 1となるのはまったく頭になかった。なるほど……