読者です 読者をやめる 読者になる 読者になる

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

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

解法

小さい 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;
	}
}

計算量

メモ化再帰の遷移に注目すると、三つ又に分かれているように見えます。
n2で割っていっているのでいつかは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は定数)の形の時は安心してよさそうです。