日々drdrする人のメモ

今日もdrdr、明日もdrdr

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

総和の計算

 {\displaystyle 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)