問題

$N \le 10^5$ と $K \le 300$ に対し、次を満たす組 $(x, y)$ の数を数えよ:

  • $0 \le x \le y$
  • $x ~\mathrm{bitand}~ y = N$
  • $y - x \le K$

ただし、無限個存在する場合もある。

考察

  1. $x, y$ はそれぞれ $N ~\mathrm{bitor}~ d$ として得られる
  2. $O(NK)$ ぐらいで解かせたそうな制約
  3. ほとんどの場合が無限個になったりしそうな雰囲気ある
  4. 条件を満たす組が無限個存在するならば、ある $k \le K$ が存在して $y - x = k$ を追加で満たす組が無限個存在する
  5. $y = x + K$ としたとき変化が起こらないような高すぎる bit を足して $x = N + 2^{100}$ などとはできない
  6. まず無限に作れるか確認して、有限ならそう大きくないある $k$ に対し $2^k N$ まで見れば解けそう
  7. 無限に作れるかどうかの判定はやれば分かるだろうが、誤魔化し
  8. とりあえず投げてみたら AC した

解法

嘘っぽい解法。 有限のときにすべてを尽せるであろう $M$ と、それよりさらに大きい $M’$ を直感によって定める。 $x \le M, M’$ について $O(M’K)$ でそれぞれ全探索し、個数が一致していればそれが答え、そうでなければ無限個存在する。

リンク