変数ビット目をとします。またはのどちらかなので、が成立します。よって、となります。よって、とすると、より「ビット目が」が成立するので、ここから各ビットについて考えていきます。

ビット目について、

  • ならばです。(よりだから)
  • ならばです。(よりだから)
  • ならばです。(ここは確定しません)
  • ならば解なしです。(と矛盾するから)

また、最初のビットへの繰り上がりは存在しないため、ならば解なしとなります。

これらのことに注意して解を組み立てれば良いです。計算量はとなりますが、今回はなので十分間に合います。

ans.cpp

質問・誤りがある場合


Twitterに連絡ください。ID : @YS55749378