yukicoder No.822 Bitwise AND
問題
$N \le 10^5$ と $K \le 300$ に対し、次を満たす組 $(x, y)$ の数を数えよ:
- $0 \le x \le y$
- $x ~\mathrm{bitand}~ y = N$
- $y - x \le K$
ただし、無限個存在する場合もある。
考察
- $x, y$ はそれぞれ $N ~\mathrm{bitor}~ d$ として得られる
- $O(NK)$ ぐらいで解かせたそうな制約
- ほとんどの場合が無限個になったりしそうな雰囲気ある
- 条件を満たす組が無限個存在するならば、ある $k \le K$ が存在して $y - x = k$ を追加で満たす組が無限個存在する
- $y = x + K$ としたとき変化が起こらないような高すぎる bit を足して $x = N + 2^{100}$ などとはできない
- まず無限に作れるか確認して、有限ならそう大きくないある $k$ に対し $2^k N$ まで見れば解けそう
- 無限に作れるかどうかの判定はやれば分かるだろうが、誤魔化し
- とりあえず投げてみたら AC した
解法
嘘っぽい解法。 有限のときにすべてを尽せるであろう $M$ と、それよりさらに大きい $M’$ を直感によって定める。 $x \le M, M’$ について $O(M’K)$ でそれぞれ全探索し、個数が一致していればそれが答え、そうでなければ無限個存在する。