UOJ Logo Universal Online Judge

UOJ

#596. 【集训队互测2021】三维立体混元劲

附件下载 统计

要想打好松活弹抖闪电鞭,就得先掌握三维立体混元劲。

马老师是一名高维太极武术大师,根据他在 $k$ 维空间教人打拳的经历,他指出,你作为一名 $k$ 维生物,身上有 $n_1+\dots+n_k$ 处穴位,其中有 $n_j$ 处穴位来自第 $j$ 个维度。要想练好 $k$ 维立体混元劲,必先打通经脉,也就是说这 $n_1+\dots+n_k$ 处穴位通过经脉两两连通。也就是说如果将穴位看成点,穴位之间的经脉看成边,那么需要构成连通图。已知对于两个分别处于 $i,j$ 维度的穴位,打通这两个穴位有 $a_{i,j}$ 种方法。注意处于同一个维度的穴位之间也可以打通,但一个穴位不能和自己打通

请你自行计算一下,有多少种方法可以给你打通经脉。由于方案数很多,你只需要算出同余 $998244353$ 的结果。

输入格式

第一行包含一个正整数 $k$,表示你所处的空间维度。

接下来一行输入 $k$ 个正整数,第 $j$ 个表示 $n_j$,即你在第 $j$ 个维度的穴位数量。

接下来输入 $k$ 行,每行 $k$ 个整数,其中第 $i$ 行第 $j$ 个数表示 $a_{i,j}$,保证 $a_{i,j}=a_{j,i}$。

输出格式

输出一行一个整数,表示打通经脉的方案数,同余 $998244353$ 的结果。

样例一

input

2
2 1
1 2
2 1

output

12

explanation

共有 $2+1=3$ 个节点,其中 $(1,2)$ 间有 $1$ 种方式打通,$(1,3),(2,3)$ 各有 $2$ 种方式打通。

若 $(1,2)$ 间打通,那么接下来有 $(2+1)^2-1=8$ 种方式打通。

若 $(1,2)$ 间未打通,那么 $(1,3),(2,3)$ 必须各自打通,有 $2\times 2 = 4$ 种方式。

总共有 $8+4=12$ 种方式。

样例二

input

2
7 4
1 998244352
998244352 0

output

188336

限制与约定

记 $N=(n_1+1)\times \dots \times(n_k+1)$。

对于 $100\%$ 的数据,保证 $N\le 2.5\times 10^5, 0\le a_{i,j} < 998244353$。

子任务编号 特殊限制 分值
$1$ $N\le 1000$ $10$
$2$ $k=1$ $10$
$3$ $k \le 2$ $15$
$4$ $k\le 3$ $10$
$5$ $n_j=1$ $15$
$6$ $40$

时间限制:$4\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载