AtCoder Educational DP Contest：O問題（bit DP）

DPコンテストのO問題に引っかかったので，まとめます．

f:id:kuroneko1259:20190801183729p:plain

方針

男女N人ずつのマッチングですが、例えば男性iを昇順に固定した場合、女性N人の順列を試せば全通り考えられます。しかし，O(N!)の時間がかかり間に合わないです。一般に，順列などO(N!)をO(2^N)に落とすテクニックとしてbit DPなるものがあるようなのでそれを使っていきます。

bit DP

N個の要素の順列で条件に合うものを数え上げたりするときに、順列全ての情報を保持する必要がなく，どの要素をつかっているかを保持したので十分だという場合に使えるみたいです。どの要素を使っているかは，N個の要素の部分集合として表せ，bit列を用いることで割と簡単に表現できます。

考え方

例えば，３人の男女のマッチングで３組のペアが何通りできるかを考えます。このとき，どの女性がマッチングに参加しているかをbit列で101のように表現することにします。男は昇順に固定されていることを考えると，この例でいえば女１と女３と，男１，男２のマッチングを考えることになります。また，bit列で表される女M人がマッチングに参加した場合に，M組みのペアがdp[bit]通り考えられるとします．

３人全員がマッチングに参加するとき，bit列は111になります．漸化式を立てたいので、ペアを１組固定することで２人でのマッチングとの関係を考えます。ペアを１つ固定する上で，男は昇順に固定されているので当然男３になりますが、女は３人のうち１人を選ぶことになります。

仮に女１が選ぶとしましょう。このとき女１以外の参加者のbit列は011になります。男３と女１が実際にペアになれるとき、女１を除いた２人のマッチングにこのペアを追加するだけで３人のマッチングが完成することから，男３と女１がペアになる３人のマッチングはdp[011]通りあることになります（女２と女３での２組のマッチングが全くない場合は男３と女１がペアになっても０通りですが，dp[011]=0が成り立っているので問題ないです）。

女１が選ばれたのに男３と女１がペアになれない場合、女２と女３がペアになれたところで３人のマッチングは不可能なので０通りです。

これらをマッチングに参加している女性すべてでやっていくと，以下の漸化式が立てられます。このとき男iと女jがペアになれるとき１，なれないとき０になる関数として ${a[i][j]}$ を定義します。

${dp[111] = dp[011] * a[3][1] + dp[101] * a[3][2] + dp[110] * a[3][3]}$

これを一般化すると，bit列において１の数をi個としたとき（参加している女・男の人数はbit列の１の数に対応），参加しているすべての女と男iについて上記のことをやっていけばよいわけです。

この漸化式を使って動的計画法で実装します。bitは１０進数で ${2^N（1 << N） - 1}$ まで１ずつ足していけばすべてのbit列を網羅できます。

このとき、

1 << i：右からi+1番目の桁だけ１をたてる
bit xor (1 << i)：bitのi+1番目の桁を反転させる

ということに注意すると

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

#define MOD 1000000007LL

ll dp[1<<25];
int a[21][21];

int main() {
  int N; cin >> N;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cin >> a[i][j];
    }
  }
  dp[0] = 1;
  for (int bit = 0; bit < (1<<N); bit++) {
    int pos = __builtin_popcount(bit) - 1;
    
    for (int i = 0; i < N; i++) {
      if ((bit & (1<<i)) && a[pos][i]) {
        dp[bit] += dp[bit ^ (1<<i)];
        dp[bit] %= MOD;
      }
    }
  }
  cout << dp[(1<<N) - 1] << endl;
  return 0;
}