各桁の111の数を数えればO(logn){\mathcal O}(\log n)O(logn)で解ける。この際、g(x)=f(0,x)g(x) = f(0, x)g(x)=f(0,x)が求まればf(x,y)=g(y)⊕g(x−1)f(x, y) = g(y) \oplus g(x-1)f(x,y)=g(y)⊕g(x−1)と書けるので、各桁ごとの偶奇の判定がだいぶ簡単になる。
任意のn∈2Nn \in 2{\mathbb N}n∈2Nについてn⊕(n+1)=1n \oplus (n+1) = 1n⊕(n+1)=1となるのはまったく頭になかった。なるほど……
