AtCoder Beginner Contest 129 E - Sum Equals Xor

解法

※ $a$ と $b$ のXOR演算を、 $a \oplus b$ という記号で表すことにします。

まず注目すべきは $a+b = a \oplus b$ という条件です。これは知識として覚えておくと得な性質なのですが、XOR演算は繰り上がりのない足し算と思うことができます。

このことを確かめるために、 $a, b$ のある桁のビットとして考えられるパターンを列挙してみましょう。

$a, b$ の $d$ ビット目	$a \oplus b$ への影響	$a + b$ への影響
$0, 0$	$d$ ビット目が0になる	$d$ ビット目が0になる
$0, 1$ または $1, 0$	$d$ ビット目が1になる	$d$ ビット目が1になる
$1, 1$	$d$ ビット目が0になる	$d$ ビット目が0になり、1つ上のビットに1繰り上がる

繰り上がりが生じる $(1, 1)$ の場合を除いて両者は一致していることが分かります。そして繰り上がりのあるところでは $a+b$ のほうが大きくなります。

このことから $a+b = a \oplus b$ という条件は、ビットで考えた足し算において繰り上がりが1回もない、つまりどの桁のビットも $(1, 1)$ でないことと同値であると分かります。

そのため $a, b$ の各ビットの選び方は $(0, 0), (0, 1), (1, 0)$ の3通りの選び方があります。これで $a+b = a \oplus b$ という条件はクリアです。

次に $a+b \le L$ という条件を考えます。ここで、

ある上限値以下で条件を満たす値の個数を求める問題である
上限値 $L$ が非常に大きい
桁（ここではビット）に関する条件が存在する

という性質があるときには、桁DPで解ける可能性が非常に高いです。

ということでDPを組みましょう。桁DPの基本は、状態を以下のような形で持つことです。

$dp\lbrack (どの桁まで見て) \rbrack\lbrack (これまでの状態が○○で) \rbrack \lbrack (上限より小さいことが確定している・いない)\rbrack$

真ん中に入るのは桁にまたがるような条件です。例えば「桁和が $M$ の倍数であるもの」を数える場合には、真ん中には「これまでの桁和を $M$ で割った余り」などが入りますね。今回はそのような条件が特にないので不要です。そのため

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 上から $i$ 桁目までを決めて、その桁までが $(0, 0), (0, 1), (1, 0)$ の3通りから選ばれていて、 $a+b$ が $L$ より小さいことが確定している $(j=1)$ /いない $(j=0)$ ような選び方の個数

とすることができます。（この記事においては、一番上の桁を1桁目としておきます）

遷移を考えましょう。上の桁から順番に考えていく時には、桁DPの遷移は以下のように考えることができます。

からの遷移（より小さいことが確定している）
- このとき $i$ 桁目の値はどのように選んでもよい。 $L$ より小さいことが確定済みなので、 $dp\lbrack i \rbrack\lbrack 1 \rbrack$ に遷移する。
からの遷移（より小さいことが確定していない）
- このときの桁目の値を、の桁目の値をとして、
  - $d_{i} \gt l_{i}$ のとき、 $a+b$ が $L$ を超えてしまうのでアウト。ここには遷移できない。
  - $d_{i} = l_{i}$ のとき、変わらず $dp\lbrack i \rbrack\lbrack 0 \rbrack$ に遷移する。
  - $d_{i} \lt l_{i}$ のとき、 $a+b$ が $L$ より小さいことが確定するので $dp\lbrack i \rbrack\lbrack 1 \rbrack$ に遷移する。