ARC066, ABC050 - D問題: Xor Sum - 日々ｄｒｄｒする人のメモ

コンテスト中に解けなかったけど、解説に載ってた解法以外で解けたのでメモ

D: Xor Sum - AtCoder Regular Contest 066 | AtCoder

この問題は0からvまでの通り数の総和をメモ化したDFSで解けた。

解法

まず、 ${0 \le u = a \text{ xor } b \le v = a + b \le N}$ であることがわかる。

ここで、 ${v = k}$ とした時に考えられる ${u}$ の値の通り数を ${f(k)}$ とする。

このとき、 ${b = k - a}$ なので、 ${u = a \text{ xor } (k - a)\hspace{5mm}(0 \le a \le k)}$ が成り立つ。

また、 ${f(0) = f(1) = 1}$ である。

${f(k)}$ の漸化式

ここで、 ${v = k}$ の時の ${a \text{ xor } (k - a)}$ の値を ${a}$ を0からkまで動かして計算してみる。

n = input()
for i in xrange(n+1):
    r = i^(n-i)
    print "%3d xor %3d => %3d (= %3d<<1)" % (i, n-i, r, r>>1)

この時、 ${u}$ の値とその値から下位1ビットを除いた値を眺めていると、
${f(2n) = f(n) + f(n-1) \\ f(2n-1) = f(n-1)}$
という関係が成り立つことに気づく。

例えば、 ${k = 6}$ の時、 ${u}$ の値は ${a}$ が0の時から順番に 6,4,6,0,6,4,6 と出現するが、
${k=3}$ の時は 3,3,3,3 、 ${k=2}$ の時は 2,0,2 と出現しており、 ${k = 6}$ にはそれらを2倍した値が交互に出現してることがわかる。
また、 ${k = 5}$ の時、uの値は 5,5,1,1,5,5 となるが、 ${k = 2}$ の時の 2,0,2 と比較すると、 ${k = 5}$ の場合では ${k = 2}$ の場合の値を2倍して1足した値が2個ずつ出現していることがわかる。

これを一般化して考える。

まず、奇数の場合の ${k = 2n-1}$ を考える。
${a = 2m}$ の時、
${ \begin{align} u & = & 2m \text{ xor } (2n-1-2m) \\ & = & 2m \text{ xor } 2(n-1-m) \text{ xor } 1 \\ & = & 2(m \text{ xor } (n-1-m)) \text{ xor } 1 \\ & = & 2(m \text{ xor } (n-1-m)) + 1 \end{align} }$
と変形でき、
${a = 2m+1}$ の時、
${ \begin{align} u & = & (2m+1) \text{ xor } (2n-1-2m-1) \\ & = & 2m \text{ xor } 2(n-1-m) \text{ xor } 1 \\ & = & 2(m \text{ xor } (n-1-m) ) \text{ xor } 1 \\ & = & 2(m \text{ xor } (n-1-m) ) + 1 \end{align} }$
と変形できる。
この式から、 ${k = n-1}$ の場合に出現するuの値を2倍して1足した値が出現することがわかり、 ${k = 2n-1}$ の時に出現するuの値の通り数と ${k = n-1}$ の時に出現する値の通り数は同じであることがわかる。

次に、偶数の場合の ${k = 2n}$ を考える。
${a = 2m}$ の時、
${ \begin{align} u & = & 2m \text{ xor } (2n - 2m) \\ & = & 2(m \text{ xor } (n - m) ) \end{align} }$
と変形でき、
${a = 2m+1}$ の時、
${ \begin{align} u & = & (2m+1) \text{ xor } (2n - 2m - 1) \\ & = & (2m+1) \text{ xor } (2(n-1) - 2m + 1) \\ & = & 2m \text{ xor } (2(n-1) - 2m) \\ & = & 2(m \text{ xor } ( (n-1) - m) ) \end{align} }$
と変形できることがわかる。
この式から、aが偶数の時には ${k = n}$ の時のuの値を2倍した値、aが奇数の時には ${k = n-1}$ の場合のuの値を2倍した値が出現することがわかる。

この時、 ${u}$ の値は、 ${k}$ が奇数の場合はすべて奇数となり、 ${k}$ が偶数の場合はすべて偶数となる。よって、 ${k}$ が偶数の場合と奇数の場合では同じ値は出現しないことがわかり、 ${k = 2n}$ の時の通り数はそのまま ${k = n-1}$ と ${k = n}$ の通り数の和になることがわかる。

おまけに、この漸化式の数列はこれっぽい。
https://oeis.org/A002487

総和の計算

$S_n = \sum_{i=0}^nf(i)$ とする。この時、求めたい値は ${S_N}$ である。

ここで、 ${S_{2n}}$ について考える。

すると、さっき求めた漸化式を元に以下のように変形できる。

${\displaystyle \begin{align} S_{2n} & = & \sum_{i=0}^{2n}f(i) \\ & = & \sum_{i=1}^{n}(f(2i) + f(2i-1)) + f(0) \\ & = & \sum_{i=1}^{n}(f(i) + 2f(i-1)) + f(0) \\ & = & \sum_{i=0}^{n}f(i) + 2\sum_{i=0}^{n-1}f(i) \\ & = & S_n + 2S_{n-1} \end{align} }$

また、 ${S_{2n+1}}$ の場合については以下のように変形できる。

${\displaystyle \begin{align} S_{2n+1} & = & f(2n+1) + S_{2n} \\ & = & f(n) + S_{n} + 2S_{n-1} \\ & = & 2S_{n} + S_{n-1} \end{align} }$

そして、 ${S_0 = 1, S_1 = 2}$ であるため、これで求めたい ${S_N}$ を計算することができる。
mapなどでメモ化DFSすれば計算量は ${\mathrm{O}(\log N)}$

こんな感じで書ける。
http://arc066.contest.atcoder.jp/submissions/1033199

N = input()
MOD = 10**9+7
 
memo = {0: 1, 1: 2}
def S(k):
    if k in memo:
        return memo[k]
    if k % 2 == 1:
        result = (2*S(k/2) + S(k/2-1)) % MOD
    else:
        result = (S(k/2) + 2*S(k/2-1)) % MOD
    memo[k] = result
    return result
print S(N)