atcoder#DPO. Matching

Matching

题目描述

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

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

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

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

输入格式

入力は以下の形式で標準入力から与えられる。

N N a1, 1 a_{1,\ 1} \ldots a1, N a_{1,\ N} : : aN, 1 a_{N,\ 1} \ldots aN, N a_{N,\ N}

输出格式

N N 組のペアを作る方法は何通りか? 109 + 7 10^9\ +\ 7 で割った余りを出力せよ。

题目大意

给定二分图,两个集合都有 NN 个点,ai,j=1a_{i,j}=1 表示第一个集合第 ii 个点与第二个集合第 jj 个点连边。

求二分图完备匹配数,答案对 109+710^9+7 取模。

3
0 1 1
1 0 1
1 1 1
3
4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
1
1
0
0
21
0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1
1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0
0 0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 0 0 1 1
0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0
1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1
0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0
0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1
0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1
0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1
0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0
0 0 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1
0 1 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 1
1 1 1 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 1
0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1
1 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1
0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1
0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0
1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0
1 0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 0 0 0
102515160

提示

制約

  • 入力はすべて整数である。
  • 1  N  21 1\ \leq\ N\ \leq\ 21
  • ai, j a_{i,\ j} 0 0 または 1 1 である。

Sample Explanation 1

ペアを作る方法は次の 3 3 通りです。 男性 i i と女性 j j のペアを (i, j) (i,\ j) で表します。 - (1, 2), (2, 1), (3, 3) (1,\ 2),\ (2,\ 1),\ (3,\ 3) - (1, 2), (2, 3), (3, 1) (1,\ 2),\ (2,\ 3),\ (3,\ 1) - (1, 3), (2, 1), (3, 2) (1,\ 3),\ (2,\ 1),\ (3,\ 2)

Sample Explanation 2

ペアを作る方法は次の 1 1 通りです。 - (1, 2), (2, 4), (3, 1), (4, 3) (1,\ 2),\ (2,\ 4),\ (3,\ 1),\ (4,\ 3)

Sample Explanation 4

答えを 109 + 7 10^9\ +\ 7 で割った余りを出力することを忘れずに。