#AT15. Matching
Matching
[O] Matching(dp_o)
来源: AtCoder Educational DP Contest - Problem O 原题时限:2 秒 / 内存:1024 MB
题目描述
有 位男士和 位女士,均编号为 。
对于每对 (),男士 与女士 的契合度由整数 给出:若 表示二人可以配对,若 表示不能配对。
太郎想组成 对,每对由一位男士和一位可以与之配对的女士组成,且每位男士、每位女士都恰好属于一对。
求太郎组成 对的不同方案数,对 取模。
输入格式
输入由标准输入按以下格式给出:
N
a_{1,1} a_{1,2} \ldots a_{1,N}
:
a_{N,1} a_{N,2} \ldots a_{N,N}
输出格式
输出方案数对 取模的结果。
数据范围
- 输入中的所有值均为整数。
- 为 或 。
样例 1
输入:
3
0 1 1
1 0 1
1 1 1
输出:
3
样例 2
输入:
4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
输出:
1
样例 3
输入:
1
0
输出:
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
输出:
102515160