5190. AT_dp_o Matching
时间限制：1000 MS 内存限制：256 MB
题目描述
# AT_dp_o Matching ## 题目描述 [problemUrl]: https://atcoder.jp/contests/dp/tasks/dp_o 有 $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}$ $\ldots$ $a_{1, N}$ $:$ $a_{N, 1}$ $\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$ 的余数。