← 返回题目列表

AtCoder · arc197_d

D. 祖先关系

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

分数: 700 点

问题陈述

你被给予 N\times N 矩阵 A = (A_{i,j}) (1\le i,j\le N)其条目是 0 or 1.

查找,取模 998244353,树木数量 G on N 顶点编号 1 to N 满足以下条件。

  • A_{i,j}=1 当且仅当至少满足以下条件之一:
    • 当 G 以顶点为根 1,顶点 j 是顶点的祖先 i。也就是顶点 j 位于独特的道路上 G 顶点之间 1 和 i.
    • 当 G 以顶点为根 1,顶点 i 是顶点的祖先 j。也就是顶点 i 位于独特的道路上 G 顶点之间 1 和 j.

这里,路径的端点被认为是在该路径上。请注意 G 是一棵树,保证任意两个顶点之间的路径的唯一性。

有 T 测试用例;逐一解决。

约束

  • 1\leq T\leq 10^5
  • 2\leq N\leq 400
  • A_{i,j}\in \lbrace 0,1\rbrace (1\leq i,j\leq N)
  • A_{i,i}=1 (1\leq i\leq N)
  • A_{i,j}=A_{j,i} (1\leq i,j\leq N)
  • 总和 N^2 所有测试用例最多 400^2.

输入

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

T
\text{case}_1
\vdots
\text{case}_T

每个案例均按以下格式给出:

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

输出

打印 T 行。的 i- 第行应包含数字,模数 998244353,树木 G 满足条件 i- 第一个测试用例。


示例输入 1

5
3
1 1 1
1 1 0
1 0 1
3
1 1 1
1 1 1
1 1 1
3
1 0 0
0 1 0
0 0 1
3
1 0 1
0 1 1
1 1 1
7
1 1 1 1 1 1 1
1 1 0 1 0 1 1
1 0 1 1 1 1 0
1 1 1 1 1 1 1
1 0 1 1 1 1 0
1 1 1 1 1 1 1
1 1 0 1 0 1 1

示例输出 1

1
2
0
0
8

在第一个测试用例中,以下一棵树 G 满足条件:

在第二个测试用例中,以下两棵树 G 满足条件: