二分图完美匹配计数(Matching)

题目描述

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

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

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

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

输入格式

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

$N$ $a_{1,\ 1}$ $\ldots$ $a_{1,\ N}$ $:$ $a_{N,\ 1}$ $\ldots$ $a_{N,\ N}$

输出格式

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

样例输入 #1

3
0 1 1
1 0 1
1 1 1

样例输出 #1

3

样例输入 #2

4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

样例输出 #2

1

样例输入 #3

1
0

样例输出 #3

0

样例输入 #4

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

样例输出 #4

102515160

数据范围

制約

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

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 4

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

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1500。

测试点分布

出处：原题链接