XOR Combination

2 secs 1024 MB

解説

上のビットから求めて行きます。桁DPを行います。

dp[iビット目][xがa未満確定か][yがb未満確定か] のようなdp配列を作成します。

$X$ の $i$ ビット目を固定した時、 $Y$ の $i$ ビット目も一意に定まります。

$0,1$ どちらも試し、 $A$ の $i$ ビット目が $1$ かつ、試したビットが $0$ の時に $X$ が $A$ 未満が確定します。 $Y$ も同様です。

最後のビットまで見た時、 $dp[0][0][0] + dp[0][0][1] + dp[0][1][0] + dp[0][1][1]$ が答えとなります。

実装ではdpのiビット目の部分は省いています。