ABC129 E - Sum Equals Xor - ツバサの備忘録

解法

制約を見ると明らかに桁DPのような匂いがするので桁DPをしました。
$a,b$ の上から $i$ 桁目を $a_{i},b_{i}$ とします。
$(a_{i},b_{i}) = (1,1)$ となる $i$ が存在した場合、 $a+b$ をすると繰り上がりが発生するので、 $a+b \neq a \ xor \ b$ となります。逆に、それ以外の $(0,0), (0,1), (1,0)$ はどれを使用してても問題の条件を満たします。
ということで、 $(0,0), (0,1), (1,0)$ のみを選択して $a+ b \leqq L$ となる $(a,b)$ のペアの個数を求めることができればよいです。
$dp[i][j]$ という配列を用意します。添え字はそれぞれ次のことを表します。

$i:$ 今上から何桁目までの数字を決めたか
$j$ : $a+b$ が $L$ 未満の数字であることが確定しているかどうか

つまり、
$dp[i][1]$ は、上から $i$ 桁だけ数字を決めて、 $a,b$ どちらも $L$ 未満であるようなペア $(a,b)$ の個数
$dp[i][0]$ は、上から $i$ 桁だけ数字を決めて、 $a+b=L$ となっているようなペア $(a,b)$ の個数
となります。
このようなことができるのは、上から数字を決めていったときに、その時点で $a+b \lt L$ が確定していれば、それより下の桁をいかなる数字にしても、 $a+b \lt L$ であることが決まっているからです。 $L$ の上から $i$ 桁目を $L_{i}$ として、 $L_{i}$ について場合分けをしつつ遷移を見ていきます。

$L_{i}$ が1のとき
$dp[i-1][j]$ からの遷移を考えます。
$j=0$ のときに、 $i$ 桁目で $(0,0), (0,1), (1,0)$ をそれぞれ選んだ場合どうなるか、を考えると、
$(0,0)$ を選んだ際は $a+b \lt L$ が確定します。
逆に、 $(0,1), (1,0)$ を選んだ際は、 $a+b = L$ となります。
ということで、まず
$dp[i][1] += dp[i-1][0]$
$dp[i][0] += dp[i-1][0] \times 2$
が決まります。
$j=1$ のときに、 $i$ 桁目で $(0,0), (0,1), (1,0)$ をそれぞれ選んだ場合どうなるか、を考えると、
$(0,0), (0,1), (1,0)$ どれを選んでも $a+b \lt L$ が確定しています。
よって、
$dp[i][1] += dp[i-1][1] \times 3$
となります。
遷移元がこれで全部になるので、結局遷移は
$dp[i][1] = dp[i-1][1] \times 3 + dp[i-1][0]$
$dp[i][0] = dp[i-1][0] \times 2$
となります。
$L_{i}$ が0のとき
同様にして $dp[i-1][j]$ からの遷移を考えます。
$j=0$ のときに、 $i$ 桁目で $(0,0), (0,1), (1,0)$ をそれぞれ選んだ場合どうなるか、を考えると、
$(0,0)$ を選んだ際でも、 $a+b = L$ となります。
$(0,1), (1,0)$ を選ぶことはできません。 $L$ を超えてしまいます。
ということで、まず遷移は
$dp[i][0] += dp[i-1][0]$
となります。 $j=1$ のときはというと、
$(0,0), (0,1), (1,0)$ どれを選んでも $a+b \lt L$ が確定しています。
ということで、
$dp[i][1] += dp[i-1][1] \times 3$
となります。
よって、
$dp[i][0] = dp[i-1][0]$
$dp[i][1] = dp[i-1][1] \times 3$
となります。

あとは、この場合分けをもとに遷移を行っていけばよいです。
初期状態ですが、
$(何も見ていない) = (0桁目までを見終えた)$ 、とみなすことができ、 $L$ 未満であることはもちろん確定していないので、 $dp[0][0] = 1$ となります。
答えは、 $dp[n][0] + dp[n][1]$ となります。

感想

逆に、DPでない方法を考えることができませんでした。
いろいろな方法を思いつけるようになりたいですね。