DPの漸化式について
これところが、配列の添え字は整数でなければならないので、整数を集合に対応させる方法が必要になります。
集合を整数で表す方法
集合は、もしi
番目の要素が含まれるならi
ビットDP目が立った整数として書い表現することができます。集合に対する操作もビット演算で表現できます。
以下は集合演算の例です。(以下、n
, m
を(集合を表す)整数とします)
空集合 ...
0
n
とm
の和集合 ...n | m
n
とm
の積集合 ...n & m
n
にi
番目の要素が含まれるか ...(n & (1 << (i-1))) != 0)
積集合の応用です。
1 << (i-1)
はi
ビット目だけが立つ、すなわちi
番目の要素のみを含む集合を表すので、これと元の集合との積を取って空集合にならないことを確認すればよいです。1~bまでの要素をすべて含む集合 ...
(1 << b) - 1
1 << b
でb+1ビット目のみが立ちます。これから1を引くことで下位bビット全てが1になります。
ビットDPについて
さて、集合を整数で表せたので、配列の添え字として使うことが、できるようになりました。これが解説で言及されているビットDPです。コードのでは以下の部分でしたにあたります。
集合は、もしぬいぐるみj
が含まれるならj
ビット目が立った整数として表現されています。例えば0
が表すのは集合は空集合です。
また集合に対する操作はビット演算で表現できることに注意してください。(和集合は|
で、積集合は&
で、ある要素が含まれるかは積集合を応用して&
で、といった具合です。)