A6202. 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$ 取模的结果。
对于每一对 $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$
> $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
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$。
## 样例解释 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$ 取模的结果。
- 所有输入均为整数。
- $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$ 取模的结果。