解法
※ と
のXOR演算を、
という記号で表すことにします。
まず注目すべきは という条件です。これは知識として覚えておくと得な性質なのですが、XOR演算は繰り上がりのない足し算と思うことができます。
このことを確かめるために、 のある桁のビットとして考えられるパターンを列挙してみましょう。
|
||
---|---|---|
|
|
|
|
|
|
|
|
繰り上がりが生じる の場合を除いて両者は一致していることが分かります。そして繰り上がりのあるところでは
のほうが大きくなります。
このことから という条件は、ビットで考えた足し算において繰り上がりが1回もない、つまりどの桁のビットも
でないことと同値であると分かります。
そのため の各ビットの選び方は
の3通りの選び方があります。これで
という条件はクリアです。
次に という条件を考えます。ここで、
- ある上限値以下で条件を満たす値の個数を求める問題である
- 上限値
が非常に大きい
- 桁(ここではビット)に関する条件が存在する
という性質があるときには、桁DPで解ける可能性が非常に高いです。
ということでDPを組みましょう。桁DPの基本は、状態を以下のような形で持つことです。
真ん中に入るのは桁にまたがるような条件です。例えば「桁和が の倍数であるもの」を数える場合には、真ん中には「これまでの桁和を
で割った余り」などが入りますね。今回はそのような条件が特にないので不要です。そのため
上から
桁目までを決めて、その桁までが
の3通りから選ばれていて、
が
より小さいことが確定している
/いない
ような選び方の個数
とすることができます。(この記事においては、一番上の桁を1桁目としておきます)
遷移を考えましょう。上の桁から順番に考えていく時には、桁DPの遷移は以下のように考えることができます。
からの遷移(
より小さいことが確定している)
- このとき
桁目の値はどのように選んでもよい。
より小さいことが確定済みなので、
に遷移する。
- このとき
からの遷移(
より小さいことが確定していない)
- このとき
の
桁目の値を
、
の
桁目の値を
として、
のとき、
が
を超えてしまうのでアウト。ここには遷移できない。
のとき、変わらず
に遷移する。
のとき、
が
より小さいことが確定するので
に遷移する。
- このとき
ここで各桁の数字の組み合わせは なので、
となるものは1通りで
となるものは2通りであることに注意してください。
の桁数(文字数)を
として、
が答えになります。