AT_dp_o 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$ 对。每个男性和每个女性都必须恰好属于一对。

请问有多少种组成 $N$ 对的方法？请输出对 $10^9 + 7$ 取模的结果。

输入格式

输入通过标准输入给出，格式如下：

$N$
$a_{1, 1}\ a_{1, 2}\ \ldots\ a_{1, N}$
$a_{2, 1}\ a_{2, 2}\ \ldots\ a_{2, N}$
$\vdots$
$a_{N, 1}\ a_{N, 2}\ \ldots\ a_{N, N}$

输出格式

输出组成 $N$ 对的方法数，对 $10^9 + 7$ 取模。

输入输出样例 #1

输入 #1

3
0 1 1
1 0 1
1 1 1

输出 #1

3

输入输出样例 #2

输入 #2

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

输出 #2

1

输入输出样例 #3

输入 #3

1
0

输出 #3

0

输入输出样例 #4

输入 #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$。

样例解释 1

组成配对的方法有以下 $3$ 种。用 $(i, j)$ 表示男性 $i$ 和女性 $j$ 的配对。

• $(1, 2),\ (2, 1),\ (3, 3)$
• $(1, 2),\ (2, 3),\ (3, 1)$
• $(1, 3),\ (2, 1),\ (3, 2)$

样例解释 2

组成配对的方法有以下 $1$ 种。

• $(1, 2),\ (2, 4),\ (3, 1),\ (4, 3)$

样例解释 4

不要忘记输出对 $10^9 + 7$ 取模的结果。

由 ChatGPT 4.1 翻译