分数: 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 满足条件:
