← 返回题单
题单练习 状态压缩DP
← 上一题 下一题 →

A6202 | Matching

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

有 $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
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
C++ 编辑器
输入
输出