ARC066/ABC050 D: Xor Sum - OEISからの解法

コンテスト中に解けませんでした。

問題

D: Xor Sum - AtCoder Regular Contest 066 | AtCoder

解法

小さい $N$ に対して実験してOEISで検索します。
2,4,5,8,10,13,14,18,21,26,28,33,36,40,41 - OEIS

A007729が答えになりそうですが、残念ながらいい感じに求める式は見つかりません。
しかし、この数列はA002487の部分和で表されることが分かります。

A002487の一般項は次にように表せます。
$\begin{eqnarray} s(n) = \begin{cases} n & (0 \leq n \leq 1) \\ s(n/2) & (n \geq 2, nが偶数) \\ s((n-1)/2) + s((n+1)/2) & (n \geq 2, nが奇数) \\ \end{cases} \end{eqnarray}$

これの部分和 $f(n)=\sum_{i=0}^n s(i)$ を頑張って式変形します。

$n \geq 3$ のとき、
$s(0)=0$ であることを用いて、
$\begin{eqnarray} f(n) & = & \sum_{i=0}^n s(i) \\ & = & s(0) + s(1) + \sum_{i=1}^{\lfloor n/2 \rfloor} s(2i) + \sum_{i=1}^{\lfloor (n-1)/2 \rfloor} s(2i+1) \\ & = & s(0) + s(1) + \sum_{i=1}^{\lfloor n/2 \rfloor} s(i) + \sum_{i=1}^{\lfloor (n-1)/2 \rfloor} \{s(i) + s(i+1)\} \\ & = & \sum_{i=0}^{\lfloor n/2 \rfloor} s(i) + \sum_{i=0}^{\lfloor (n-1)/2 \rfloor} s(i) + \sum_{i=0}^{\lfloor (n-1)/2 \rfloor +1} s(i) \\ & = & f(\lfloor n / 2 \rfloor) + f(\lfloor (n-1) / 2 \rfloor) + f(\lfloor (n+1) / 2 \rfloor) \end{eqnarray}$

これであとはメモ化再帰で $f(N+1)$ を出力すると解けます。

ソースコード

import java.util.HashMap;
import java.util.Scanner;

public class Main {
	public static long MOD = 1000000007;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		System.out.println(f(n+1));
	}
	static HashMap<Long, Long> hm = new HashMap<>();
	public static long f(long n) {
		Long memo = hm.get(n);
		if (memo != null) return memo;
		if (n <= 2) {
			return n;
		}
		long res = f(n/2) + f((n-1)/2) + f((n+1)/2);
		res %= MOD;
		hm.put(n, res);
		return res;
	}
}

計算量

メモ化再帰の遷移に注目すると、三つ又に分かれているように見えます。
$n$ を $2$ で割っていっているのでいつかは $n$ が小さい値になることは分かりますが、途中で状態数が爆発しないのでしょうか？
実はこの遷移では大丈夫です。

ある呼び出しの深さにおいて、引数 $n$ の取りうる値が $x$ 以上 $x+a$ 未満だったとします。
次の深さにおいて、引数 $n$ の取りうる値は $\lfloor (x-1)/2 \rfloor$ 以上 $\lfloor (x+a+1)/2 \rfloor$ 未満になります。
この幅はfloorを無視して $(a+2)/2$ 程度になるので、引数の取り得る値の幅は結局定数になります。

したがって計算量は再帰の深さと同じ $O(\log N)$ です。
再帰の形が $f((n+a)/b)$ (ただし $b(>1),a$ は定数)の形の時は安心してよさそうです。