[学習記録]AtCoder EDP O-Matching [Go]

問題

N 人の男性たちと N 人の女性たちがいます。 男性たちには1,2,…,N と番号が振られています。 同様に、女性たちには 1,2,…,N と番号が振られています。

各 i,j (1≤i,j≤N) について、男性 i と女性 j の相性の良し悪しが整数 ai,j​ によって与えられます。 ai,j​=1 ならば男性 i と女性 j は相性が良く、ai,j​=0 ならば相性が悪いです。

太郎君は、相性が良い男女どうしのペアを N 組作ろうとしています。 このとき、各男性および各女性はちょうど 1 つのペアに属さなければなりません。

N 組のペアを作る方法は何通りでしょうか？ 109+7 で割った余りを求めてください。

解法

i 番目の男性 × j 番目の女性でマッチするかを, i,  j  を状態として持ち求めようとすると
「i 番目の男性 × j 番目の女性でマッチ」の状態に遷移する前の場合の数がうまく計算できない。
BitDPを使うことでこれをうまく計算できる
・BitDP 集合をビット列で表し、それを添え字として持つDPのこと
    e.g. { 1, 0, 0, 1 } => dp[1001] = dp[2^3 + 20] = dp[9]
i 番目の男性と j 番目の女性、j 番目の女性のマッチの有無を持つ集合 s を考える。

n := readInt()

sli := make([][]int, n)
for i := 0; i < n; i++ {
	sli[i] = readSli(n)
}

// dp = [マッチした女性の集合をビットで表したもの]その時の場合の数
// n人のデータを持つ必要があるため、1をnビットシフトさせる
// n = 3 のとき、 1<3 = 1000, { 111(３人の集合) } + 1を保持できる
dp := make([]int, 1<<n)
dp[0] = 1

集合 s について、すべてのパターンを見ていく。
何番目の男性かは、そのときにたっているビットの数を数える。
マッチした場合、その時の場合の数をマッチした後の s を持つDPに加える

for s := 0; s < 1<<n; s++ {
    i := bits.OnesCount(uint(s))
	for j := 0; j < n; j++ {
		if sli[i][j] == 0 {
			continue
		}

　　　　// j 番目のビットを立てる = j ビットシフトさせ、 s とのビット論理和をとる
		dp[s|1<<j] += dp[s]
		dp[s|1<<j] %= prime_number
	}
}

s となる場合の数が０の場合、その状態は起きない
　＝　それ以後の状態に影響を与えないのでスキップ。
また、j 番目の女性がすでにマッチ済みの場合もスキップ。

for s := 0; s < 1<<n; s++ {
    // 0 のとき、それ以後の状態に影響を与えない
	if dp[s] == 0 {
		continue
	}

	i := bits.OnesCount(uint(s))
	for j := 0; j < n; j++ {
        // マッチ済みの場合
        // e.g. s = 100101, j=2 のとき
        //   s>>j = 1001, s>>j & 1 = 1
		if s>>j&1 == 1 {
			continue
		}

		if sli[i][j] == 0 {
			continue
		}

		dp[s|1<<j] += dp[s]
		dp[s|1<<j] %= prime_number
	}
}

すべて計算したあと、DPの、すべてのビットが１の添え字のもの
　＝　1 << n -1　が答えになる

// e.g n = 3 のとき
//   1 << n = 1000
//   1 << n -1 = 0111
ans := dp[1<<n-1]

（参考）例題１の、i = 1 までの動き

// 3
// 0 1 1
// 1 0 1
// 1 1 1

// s=0 => i=0,
//  １行目が0 1 1なので、
//    0 マッチしない
//    1 => s[010], dp[010] +=1
//    1 => s[001], dp[001] +=1
// s=1 => i=1,
//  ２行目が1 0 1なので
//    1 => s[101], dp[101] += dp[001]
//    0 => マッチしない
//    1 => 既にマッチ済み
// s=2 => i=1 = 010
//  ２行目が1 0 1なので
//    1 => s[110], dp[110] += dp[001]
//    0 => マッチしない
//    1 => s[011], dp[011] += dp[001]

コード（AC)

n := readInt()

	sli := make([][]int, n)
	for i := 0; i < n; i++ {
		sli[i] = readSli(n)
	}

	// dp = [マッチした女性の集合をビットで表したもの]その時の場合の数
	dp := make([]int, 1<<n)
	dp[0] = 1

	for s := 0; s < 1<<n; s++ {
		if dp[s] == 0 {
			continue
		}

		i := bits.OnesCount(uint(s))
		for j := 0; j < n; j++ {
			if s>>j&1 == 1 {
				continue
			}

			if sli[i][j] == 0 {
				continue
			}

			dp[s|1<<j] += dp[s]
			dp[s|1<<j] %= prime_number
		}
	}

	ans := dp[1<<n-1]
	return ans