怠惰の累積和

技術/競プロ/怪文書/虚無

AtCoder Beginner Contest 129 E - Sum Equals Xor

問題概要

　正整数 $L$ に対し、 $a+b≦L$ ∧ $a+b=a$ xor $b$ となる $(a,b)$ は何組存在するか。

解法

　 $L$ を上の桁から見て行って、 $n$ 桁目で $L$ よりも大きくなるとする(これは $n$ 桁目が'1'であることと一致する)。すると、それまでに出てきた'1'の個数を $p$ とすると、 $p$ について、 $a,b$ の中に'1'という文字は $p$ 個含まれる。よって、 $a,b$ の $x$ 桁目( $n≦x≦L.length()$ )において考えられる $(a,b)$ の桁の組み合わせは $(1,0),(0,1)$ の2通りの為、上 $n$ 桁目までで考えられる整数の通り数は $2^p$ 通り。

　反対に、 $n$ 桁目以降についてはどのように配置しても条件を満たすため、 $(0,0),(0,1),(1,0)$ の3通りが配置として考えられるため、 $q=L.length()-p$ とすると、 $3^q$ 通りがあり得る。

　纏めると、 $n$ 桁目( $n$ 桁目は'1')において、考えられる整数は $2^p+3^q$ 通り。

　よって、 $L$ を前から見て行き、'1'という文字が出てくるたびに答えとなる変数に上記の数値を足していけばよい。これを実装して、AC。