5/29 PKU

2723 Get Luffy Out

いくつかの部屋を持ち、直線状にドアでつながっている部屋がある。ドアはM個ある。ドアには2つのロックがあり、どちらかを外せばドアを通れる。ロックを外すにはキーが必要である。キーは2N種類あり、Nペアに分かれている。あるキーを使ったら、ペアの片割れは使えなくなる。できるだけ深くまで進むとき、どこまで進めるか。

二分探索×2-SATやるだけ

2861 Cycle with 6 vertices

無向グラフが与えられるので、6頂点からなる異なるサイクルの数を求めよ。回転、反転は同じものとして数える。

サイクルをA-B-C-D-E-F-Aとするとき、A,C,Eを固定して考える。残りの頂点は、「どこか2頂点の間にしか入らないもの(個数をp,q,rとする)」「どこでも入るもの(個数をsとする)」に分類されるが、前者は予め計算しておくことにより直ちに求まる。後者はビット演算により、高速に求まる。
すると、この場合のサイクルの数は、p,q,r,sを使って簡単に計算できる。
最後に、答えを12で割って(modなので単純に割れないことに注意)答えが得られる。