AtCoder Beginner Contest 138 F - Coincidence

解法

考察も実装もそこそこ重い問題です。順に考えていきましょう。

記法について

剰余演算を記号 $\%$ 、XOR演算を記号 $\oplus$ で表すことにします。

またこの記事では数え上げの対象である2数のペアを $(x, y)$ ではなく $(y, x)$ の順番で記載しています。

ビットだけの条件に置き換える

XORが絡む、制約が大きめ、与えられた下限/上限の間で条件を満たす値の数え上げ…ということで、帰着先として有力なのは2進数の桁DPです。しかしそのためには余りの条件をビットの条件に置き換えないといけません。

余りについての必要条件を導く時によく使うのは $y\% x \lt x$ という性質です。この性質と $y\% x = y\oplus x$ を見比べると、 $y$ と $x$ の2進数での桁数は同じである必要があることが分かります。もし $y$ のほうが桁数が大きい場合、 $y\oplus x$ に $y$ の最上位桁が残るので必ず $y\oplus x \gt x$ となってしまうからです。

そしてこの「2進数での桁数が同じ」という条件から、 $y$ を $x$ で割った商は必ず1であることが分かります。もし $y$ が $x$ の2倍以上だとすると、必ず2進数で $x$ より大きい桁数になってしまうからです。このことから $y\% x = y-x$ と置き換えることができます。 条件式は $y-x = y\oplus x$ と変形できて、剰余演算を消すことができました。

さらにXORと足し算/引き算は近い性質を持っていて、 $0 \le x \le y$ なる非負整数 $(y, x)$ に対して、2進数で繰り上がりがない足し算 $y+x$ や繰り下がりのない引き算 $y-x$ はXORと一致します。以前足し算とXORの比較をこの記事に書きましたが、同様の表を引き算についても書けば同じことが言えます。

そしてもし繰り下がりがあると引き算のほうがその分小さい値になってしまうので、逆に引き算とXORが一致するならば繰り下がりが一切ないということも言えます。

これでようやくビットの条件に言い換えられました。結局 $y\% x = y\oplus x$ となる必要条件は

$y-x$ にビット単位での繰り下がりがない。つまり $(y, x)$ の各桁のビットの組み合わせは、 $(0, 0), (1, 0), (1, 1)$ のいずれかである。
2進数での桁数が同じである。つまり前項目の3パターンの中で、上位桁から見て $(1, 1)$ が登場する前に $(1, 0)$ が登場することはない。

ということになります。また逆に上記の条件を2つとも満たすならば、実際に商が1になり引き算とXORが一致するので $y\% x = y-x = y\oplus x$ が成立します。これで十分条件であることも確かめられます。

※このように条件の言い換えテクニックを駆使すれば数式ベースで導くことができますが、思いつかない場合は小さい数で実験して、条件を満たす組み合わせの2進数表記を書き下してみるのが良いと思います。

桁DPを組む

ということで2進数での桁DPを組みます。 $L \le x \le y \le R$ の範囲内で先ほどの条件を満たす組 $(y, x)$ を数えます。

2変数なので $L, R$ を別々に処理するのが難しく、両端を真面目に処理する必要があります。上限だけを考慮する場合は「上限 $R$ より小さいことが確定したかどうか」をフラグとして持つのが桁DPの常套手段ですが、今回は下限についても同様のフラグを持ちます。

さらに「上位桁から見て、ビットの組み合わせ $(1, 1)$ が登場する前に $(1, 0)$ が登場することはない」という条件も考慮すると、DPの状態は以下のような定義になります。

= 桁目以上のビットの決め方であって、これまでに条件違反が確定するような遷移がなくて、各種フラグについて以下のような状態となっているような場合の数。
- $y$ が上限 $R$ よりも小さいことが確定している( $a=1$ )/いない( $a=0$ )
- $x$ が下限 $L$ よりも大きいことが確定している( $b=1$ )/いない( $b=0$ )
- これまでの桁でビットの組み合わせ $(1, 1)$ が登場している( $c=1$ )/いない( $c=0$ )

桁DPの実装は人によって細かい差異がありますが、この記事では最下位ビットを $0$ 桁目として、上位ビットから順に決めていく方法を取ります。つまり初期状態を $dp\lbrack 60 \rbrack\lbrack 0 \rbrack\lbrack 0 \rbrack\lbrack 0 \rbrack = 1$ として、答えを $dp\lbrack 0 \rbrack\lbrack a \rbrack\lbrack b \rbrack\lbrack c \rbrack$ の総和として求めます。