yukicoder No.698 ペアでチームを作ろう

yukicoderもやりはじめました.
No.698 ペアでチームを作ろう - yukicoder
という制約をみておおっ...と思い, とりあえず全探索の計算量を見積もりました.
まず人いたときの二人組の作り方の場合の数について考察します.
が偶数ということなので, そのときの場合に限り考察します.
人を2人組に分けるときの場合の数は次の漸化式を満たします.


少し説明を入れると, 人いて, 人で二人組を分けるときの数がわかっているとき, 新たにそこに2人A,Bを加えます. このときの2人組の場合の数は, AとA以外の誰かを組ませる場合の数とそれ以外の人々の二人組の組み合わせの積となり, 結果上の式が導かれます.
上の式に従っての場合を計算すると,

となり, 全探索をしても間に合いそうです(ほんとか？).
しかし, 実装においてsetやvectorを使って要素を増やしたり消したりしていると, あっという間にTLEしました. 実際には上の組み合わせの数より多くのループが回っているからだと思われます.
ここで, 全探索において, 同じ計算を何度もしていることに気がつきました. 組み合わせについてbitで管理しておき, 計算結果を保持しておくことで高速化を図りました. 結局, bitDPのようなものができました. bitDPもどきを実装するのは初めてだったので勉強になりました.
#277981 No.698 ペアでチームを作ろう - yukicoder