phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

ARC066 D. Xor Sum

問題

正の整数Nが与えられる。
ここで、2つの整数0 <= u, v <= Nであって、ある非負整数a,bが存在して、a ^ b = u, a + b = vとなるものが何通りあるか求めよ。
答えは1,000,000,007のあまりを答えよ。
上記の^はビットごとの排他的論理和を表す。

制約

  • 1 <= N <= 10^18

解法

まだイマイチ理解できていないところが残っているけど、とりあえずまとめ。
制約が非常に大きく、xorがビットごとの計算でもあるので、ビットの桁DPを考える。
以下、解説放送から。(下から桁DP)


問題がやや扱いにくいので、言い換えを考える。
a,bを用いた制約があるので、結局「(a xor b, a+b)が何通りあるか?」という話でであるが、aとbが入れ替わったものを重複しないように数え上げる必要がある。
重複する部分は、各bitがa側とb側で入れ替わったとしても最終的な結果には変わらない部分のことで、「a側が1、b側が0」の場合と「a側が0、b側が1」の場合、2重カウントしてしまう。
これを片方だけカウントするようにするため、「(a xor b, a+b)が何通りあるか?ただし、各ビットについて、(a側のビット,b側のビット)=(0,0)(1,0)(1,1)のものだけ考える」という問題に言い換える。


func(S,X):=「a+b<=S」「a^b<=X」のとき、各ビットが(0,0)(1,0)(1,1)のものだけ考えた場合の、答えの通り数」
と考えると、aとbの一番右側のビットについて、上記の3パターンで場合分けをする。
(1) aとbの一番右側のビットが(0,0)の場合
a=2a', b=2b'と表現できるので、これで考えると、
a'+b' <= S/2
a' ^ b' <= X/2
なので、func(S/2, X/2)

(2) aとbの一番右側のビットが(1,0)の場合
a=2a'+1, b=2b'と表現できるので、これで考えると、
a'+b' <= (S-1)/2
a' ^ b' <= (X-1)/2
なので、func((S-1)/2, (X-1)/2)

(3) aとbの一番右側のビットが(1,1)の場合
a=2a'+1, b=2b'+1と表現できるので、これで考えると、
a'+b' <= (S-2)/2
a' ^ b' <= X/2
なので、func((S-2)/2, X/2)

となる。したがって、
func(S, X) = func(S/2, X/2) + func((S-1)/2, (X-1)/2) + func((S-2)/2, X/2)
となる。
SやXが0や1のときは1通り、0未満のときは0通りになることを注意してメモ化再帰を実装すればO(log N)程度で解ける。

解法2

解説PDFから。(上から桁DP)


まず、xorというのは「桁上りのない加算」といえるところから、a ^ bとa + bを比べた場合、
a + b = a ^ b + (1 << (a & b))
という条件から、a ^ b <= a + bなので、「vがN以下かどうか」だけを考えれば良いことがわかる。
したがって、この単純に制約をそのままDPを考えると、
dp[i][j] := 上からiビットまで決まっているとき、j=vとなる通り数
が考えられる。


このままだと、jの部分がNまで考える必要があり、N<=10^18なので、メモリが足りない。
ここで、jを「上からiビットまでの部分だけ」で考える。
jの条件をNについてひっくり返して、
dp[i][j] := 上からiビットまで決まっているとき、N-j=vとなる通り数
にすると、jは0以上かどうかを考えればよく、さらに上からiビットまでで考えるために、
dp[i][j] := 上からiビットまで決まっているとき、(N>>i)-j=(v>>i)となる通り数
というのを考える。


このdpは、上からi-1(dp[i+1][*])ビットまでがわかっていて、iビット目を考えるとき、dp[i+1][j]でのjはiビット目で考える場合は2倍になることに注意すると、
(1) Nの上からiビット目が0の場合
j=0は、
(aのiビット目,bのiビット目)=(0,0)のとき、dp[i+1][0]
(aのiビット目,bのiビット目)=(1,0)のとき、なし
(aのiビット目,bのiビット目)=(1,1)のとき、dp[i+1][1]
j=1は、
(aのiビット目,bのiビット目)=(0,0)のとき、なし
(aのiビット目,bのiビット目)=(1,0)のとき、dp[i+1][1]
(aのiビット目,bのiビット目)=(1,1)のとき、なし
j=2は、
(aのiビット目,bのiビット目)=(0,0)のとき、dp[i+1][1]
(aのiビット目,bのiビット目)=(1,0)のとき、なし
(aのiビット目,bのiビット目)=(1,1)のとき、dp[i+1][2]
j=3は、
(aのiビット目,bのiビット目)=(0,0)のとき、なし
(aのiビット目,bのiビット目)=(1,0)のとき、dp[i+1][2]
(aのiビット目,bのiビット目)=(1,1)のとき、なし
j=4は、
・・・

(2) Nの上からiビット目が1の場合
j=0は、
(aのiビット目,bのiビット目)=(0,0)のとき、なし
(aのiビット目,bのiビット目)=(1,0)のとき、dp[i+1][0]
(aのiビット目,bのiビット目)=(1,1)のとき、なし
j=1は、
(aのiビット目,bのiビット目)=(0,0)のとき、dp[i+1][0]
(aのiビット目,bのiビット目)=(1,0)のとき、なし
(aのiビット目,bのiビット目)=(1,1)のとき、dp[i+1][1]
j=2は、
(aのiビット目,bのiビット目)=(0,0)のとき、なし
(aのiビット目,bのiビット目)=(1,0)のとき、dp[i+1][1]
(aのiビット目,bのiビット目)=(1,1)のとき、なし
j=3は、
(aのiビット目,bのiビット目)=(0,0)のとき、dp[i+1][1]
(aのiビット目,bのiビット目)=(1,0)のとき、なし
(aのiビット目,bのiビット目)=(1,1)のとき、dp[i+1][2]
j=4は、
・・・

のような遷移になる。
上記の遷移は周期性があり、j=2以上のときは、j=2以上のところにしか遷移しないため、「2以上」というふうにまとめ上げて計算してもよい。
すると、j=0,1,2以上の3パターンだけ考えれば良く、上記の遷移をまとめあげると、
(1) Nの上からiビット目が0の場合
j=0は、dp[i][0] = dp[i+1][0] + dp[i+1][1]
j=1は、dp[i][1] = dp[i+1][1]
j=2以上は、dp[i][2以上] = dp[i+1][1] + dp[i+1][2以上] * 3

(2) Nの上からiビット目が1の場合
j=0は、dp[i][0] = dp[i+1][0]
j=1は、dp[i][1] = dp[i+1][0] + dp[i+1][1]
j=2以上は、dp[i][2以上] = dp[i+1][1] * 2 + dp[i+1][2以上] * 3

とすることができる。
答えはΣ_{j=0,1,2以上} dp[0][j]になる。
上記の計算をするだけなので、O(log N)程度で解ける。(MODを取るのを忘れずに)