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

科技前沿 • 2026-03-31 07:22 • 阅读 1

大家好，我是讯享网，很高兴认识大家。这里提供最前沿的Ai技术和互联网信息。

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

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

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

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

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

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

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

input

 2 2 1 1 2 2 1

output

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 imes 2 = 4$ 种方式。

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

input

 2 7 4 1   0

output

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

对于 $100%$ 的数据，保证 $Nle 2.5 imes 10^5, 0le a_{i,j} < $。

时间限制：$4 exttt{s}$

空间限制：$512 exttt{MB}$

样例数据下载

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

input

output

explanation

input

output

相关推荐