F - Coincidence Editorial by miscalculation53
公式解説 にある通り、求めるものは以下の条件を満たす整数 \((x, y)\) の組の個数です。
- \(L \leq x\)
- \(y \leq R\)
- \(x\) で立っているビットは \(y\) でも立っている
- \(x\) と \(y\) の MSB の位置が同じ
下のビットから決めていく方針で次の桁 DP をします。
- \(\mathrm{dp}(L, R, \mathrm{flag}) := \) 上の条件を満たす整数 \((x, y)\) の組の個数。ただし、\(\mathrm{flag}\) が \(\mathrm{true}\) のときは \((0, 0)\) を許容し、\(\mathrm{false}\) のときは \((0, 0)\) は許容しない。
直感的には、\(\mathrm{flag}\) は「決めようとしている列が現在条件 4 を満たすかどうか」つまり「このままこれ以降のビットがすべて \(0\) でも条件を満たすかどうか」に対応します。
遷移は次のようになります。
- \(x\) の最下位ビットを \(0\)、\(y\) の最下位ビットを \(0\) にする場合
- \(x = 2x', y = 2y'\) と書けて、値の範囲は \(\left\lceil \frac{L}{2} \right\rceil \leq x'\) かつ \(y' \leq \left\lfloor \frac{R}{2} \right\rfloor\) です。MSB への影響はないので \(\mathrm{flag}\) は直前のものが使われ、\(\mathrm{dp}(L, R, \mathrm{flag}) \ \text{+=} \ \mathrm{dp}(\left\lceil \frac{L}{2} \right\rceil, \left\lfloor \frac{R}{2} \right\rfloor, \mathrm{flag})\) です。
- \(x\) の最下位ビットを \(0\)、\(y\) の最下位ビットを \(1\) にする場合
- \(x = 2x', y = 2y' + 1\) と書けて、値の範囲は \(\left\lceil \frac{L}{2} \right\rceil \leq x'\) かつ \(y' \leq \left\lfloor \frac{R - 1}{2} \right\rfloor\) です。MSB の条件は満たされなくなるので、\(\mathrm{dp}(L, R, \mathrm{flag}) \ \text{+=} \ \mathrm{dp}(\left\lceil \frac{L}{2} \right\rceil, \left\lfloor \frac{R - 1}{2} \right\rfloor, \mathrm{false})\) です。
- \(x\) の最下位ビットを \(1\)、\(y\) の最下位ビットを \(1\) にする場合
- \(x = 2x' + 1, y = 2y' + 1\) と書けて、値の範囲は \(\left\lceil \frac{L - 1}{2} \right\rceil \leq x'\) かつ \(y' \leq \left\lfloor \frac{R - 1}{2} \right\rfloor\) です。MSB の条件は満たされるようになるので、\(\mathrm{dp}(L, R, \mathrm{flag}) \ \text{+=} \ \mathrm{dp}(\left\lceil \frac{L - 1}{2} \right\rceil, \left\lfloor \frac{R - 1}{2} \right\rfloor, \mathrm{true})\) です。
あとはこの DP をメモ化再帰で計算すればよいです。状態数は \(O(\log R)\) 程度で十分高速です。
この DP は本質的に maspy さんの解説 と同じです(\(F(L, R)\) が \(\mathrm{dp}(L, R, \mathrm{false})\) に、\(G(L, R)\) が \(\mathrm{dp}(L, R, \mathrm{true})\) に対応しています)。
posted:
last update: