#PQJ767x6198. QOJ 767_6198

    ID: 3039 传统题 4000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2020-2021 集训队互测组合数学数学

QOJ 767_6198

标题: 三维立体混元劲 - Problem - QOJ.ac

#6198. 三维立体混元劲

Statistics

The problem was used in the following contests:

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

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

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

输入格式

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

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

接下来输入 k 行,每行 k 个整数,其中第 i 行第 j 个数表示 ai,j,保证 ai,j=aj,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×2=4 种方式。

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

样例二

input

2
7 4
1 998244352
998244352 0

output

188336

限制与约定

记 N=(n1+1)×⋯×(nk+1)。

对于 100% 的数据,保证 N≤2.5×105,0≤ai,j<998244353。

子任务编号 特殊限制 分值 1 N≤1000 10 2 k=1 10 3 k≤2 15 4 k≤3 10 5 nj=1 15 6 无 40