AtCoder ABC 129 E - Sum Equals Xor(Python) - あるエンジニアのAtCoder奮闘記

irisruneです。最近AtCoder ProblemsのRecommendationsがスパルタに感じてきました。

問題

桁DPというヒントを見てしまいましたがほぼ自力です、多分。6/10の記事で実装が重いかと予想していましたが全然重くありませんでした。

import sys
import numpy as np
MOD = 1000000007


def main():
    bits = input()
    ans = 1
    pow3 = 1
    for i, b in enumerate(reversed(bits)):
        if b == '1':
            ans = ((ans * 2 % MOD) + pow3) % MOD
        pow3 = (pow3 * 3) % MOD
    print(ans)


main()

アルゴリズムの説明の前に今回使うXORの性質について、 $A+B=A xor B$ となるのはAとB両方が1である（ビット）桁が1つもない場合となります。例えば、 $A=1,B=2$ の場合は $A+B=A xor B=3$ と一致しますが $A=1,B=3$ の場合は $A+B=4,A xor B=2$ と一致しません。

逆に言えば今回使うXORの性質はこれ以外ないので、これさえ気付いてしまえばアルゴリズムを考えるのはそう難しくありません。具体的には、

0桁の $L'$ については答えを1通り（ $A=B=0$ ）とおく。
$L'$ に対し与えられた $L$ を一番右の桁から順番に追加する。
追加する桁の数字が0ならば、答えは変わらない。
追加する桁の数字が1ならば、答えを2倍し、 $3^\text{(追加する前の桁数)}$ を足す。

という方針で、ほとんど帰納法と言うべきアルゴリズムとなっています。

4.について補足をすると、 $1xxxxx_{(2)}\gt011111_{(2)}$ であることから $L'=xxxxx_{(2)},11111_{(2)}$ それぞれについて $A',B'$ が取り得る組み合わせ数を用いて $L=1xxxxx_{(2)}$ について $A,B$ が取り得る値の組み合わせ数を計算できます。