ARC133-D Range XOR 解説
久しぶりのはてブロです。
解説
ある整数 $k$ があるとき、$2k \oplus (2k + 1) = 1$ なのを利用する。 区間の xor は、端の偶奇で場合分けをして次のように求められる。
- $l$ が偶数、$r$ が偶数のとき
区間の xor は、$r$ と、$(r-l)/2$ 個の $1$ の xor に等しい。
- $l$ が偶数、$r$ が奇数のとき
区間の xor は、$(r-l+1)/2$ 個の $1$ の xor に等しい。
- $l$ が奇数、$r$ が偶数のとき
区間の xor は、$l,r$ と、$(r-l -1)/2$ 個の $1$ の xor に等しい。
- $l$ が奇数、$r$ が奇数のとき
区間の xor は、$l$ と、$(r-l)/2$ 個の $1$ の xor に等しい。
これらの中で、$3$ つ目以外は簡単な割り算と和の公式で通り数を数え上げられる。 $3$ つ目は数え上げが難しいので、次のような桁 DP を組んで数え上げすると良い。
$dp[i][j][k][m]=i$ 桁目よりも上の部分を上位ビットとして、上位ビットの xor が $V$ のそれと一致し、$l$ の上位ビットが $L$ より大きい場合は $j$ が $1$、$r$ の上位ビットが $R$ より小さい場合は $k$ が $1$、$l,r$ の上位ビットが異なる場合は $m $ が $1$ となるような $(l,r)$ の通り数
ただし、これだと $l$ と $r$ の間隔の条件を満たせないので、最下位のビットの値だけずれてしまう可能性がある。ここで、$l$ が奇数で $r$ が偶数であるという条件を考えると、間隔が合う必要十分条件は、$V$ を $4$ で割った余りが $0,3$ のいずれかであることであるので、この場合分けを最初にしておけばよい。
以上で、この問題が解けた。
感想
桁 DP はコンテスト中に書き上げられたが、それ以外のパートをミスしていて通せなかった。
