← 返回题目列表

AtCoder · jsc2021_g

G. 生成树

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有一个图表 N 顶点编号 1, 2, \dots, N。最初,它没有边缘。
现在,让我们添加一些无向边 G 因此以下条件适用于任何 添加后的 i, j\,(i ≠ j) 。

  • If A_{i, j} = 1,有一条边直接连接Vertex i 和顶点 j;
  • if A_{i, j} = 0,没有直接连接Vertex的边 i 和顶点 j;
  • if A_{i, j} = -1,两者都可以。

在图表中可以 G 加法后,有多少棵树?
由于计数可能很大,请对它求模 (10^9 + 7).

约束

  • 输入中的所有值都是整数。
  • 2 ≤ N ≤ 300
  • -1 ≤ A_{i, j} = A_{j, i} ≤ 1
  • A_{i, i} = 0

输入

输入由标准输入按以下格式给出:

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

输出

打印计数模数 (10^9 + 7).


示例输入 1

4
0 1 -1 0
1 0 -1 -1
-1 -1 0 0
0 -1 0 0

示例输出 1

2

我们需要顶点之间的边 1 和顶点 2,并且我们不能在 Vertex 之间添加边 1 和顶点 4 或顶点之间 3 和顶点 4.

因此,我们有以下两个有效的图表:


示例输入 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

当我们区分顶点时,有 11^9 树木 11 顶点。