AT_jsc2021_g.Spanning Tree

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个包含 $N$ 个顶点的图 $G$ ，顶点编号为 $1, 2, \dots, N$ 。初始时， $G$ 中没有任何边。
接下来你可以向 $G$ 中添加若干无向边。但在所有边添加完毕后，对于任意的 $i, j\ (i \neq j)$ ，必须满足以下条件：

当 $A_{i, j} = 1$ 时，顶点 $i$ 和顶点 $j$ 之间必须直接有一条边。
当 $A_{i, j} = 0$ 时，顶点 $i$ 和顶点 $j$ 之间不能直接有边。
当 $A_{i, j} = -1$ 时，是否有边都可以。

在所有可能的最终图 $G$ 中，有多少个是树？
由于答案可能非常大，请输出答案对 $10^9 + 7$ 取模后的结果。

输入格式

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

$N$
$A_{1, 1}\ A_{1, 2}\ \cdots\ A_{1, N}$
$\vdots$
$A_{N, 1}\ A_{N, 2}\ \cdots\ A_{N, N}$

输出格式

请输出答案对 $10^9 + 7$ 取模后的结果。

输入输出样例

输入#1

输出#1

输入#2
```
3
0 1 1
1 0 1
1 1 0
```
输出#2
```
0
```
输入#3
```
3
0 0 0
0 0 0
0 0 0
```
输出#3
```
0
```

输入#4

11
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0

输出#4

357947677

说明/提示

限制条件

所有输入均为整数。
$2 \leq N \leq 300$
$-1 \leq A_{i, j} = A_{j, i} \leq 1$
$A_{i, i} = 0$

样例解释 1

顶点 $1$ 和顶点 $2$ 之间必须有边，顶点 $1$ 和顶点 $4$ 之间、顶点 $3$ 和顶点 $4$ 之间不能有边。因此，满足条件的情况有以下 $2$ 种。

样例解释 4

当区分顶点时， $11$ 个顶点的树一共有 $11^9$ 种。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页