No.462 6日知らずのコンピュータ
解法
まず, が
であるときを考えます
このとき, 〜
桁のビットまで, ビットを立てる順番の場合の数がそのまま場合の数になります. 一度立てたビットは元に戻さないため, これらの数列たちはすべて異なるものになり, 答えは
となります.
のときを考えます.
目的の数列は, それぞれの要素を2進数で表したときのビットが立っている数でソートし, 立っているビットの数をみると , となり, ビットの数にかぶりはありません.
また, ビットの立て方から, この立っているビットの数でソートした数列(とします)の性質として,
が成り立っている必要があります. (ここで
はビットごとの論理和)
言い方を変えると, ある要素より１つ大きな添字を持つものは, ビットを要素としてみたときに左の要素を部分集合として持っている必要があります. これらの性質を与えられたが満たしていないならば, 数列を作ることはできません. また, 立っているビット数が等しいものが存在しないことも必要ですが, (等しいとき, 両方の数を数列内に入れることはできない), これはすでに上の必要条件となっています, これらの制限をクリアできないものは0を出力します.
条件を満たした数列の場合の数は, 各の間のビットの埋め方の積となります.
のハミング距離の階乗を順次かけていくと答えです.
感想
ビットシフトをする際, (1<< N) -1 と書くと, 1がint型として認識され, Nがint型を超えるような値となっていると望み通りの計算結果が得られないことがわかった. 次のように記述するとうまくいく.
(1LL << N) - 1
また, MODのとり忘れに気をつけたい.
