分数: 400 点
问题陈述
我们有一个有向图 N 顶点编号 1 to N.
N 长度的字符串 N 每个, S_1,S_2,\ldots,S_N,表示图中的边。
具体来说, S_{i,j} is 1 如果有来自顶点的边 i 到顶点 j,和 0 否则。
该图没有自环,也没有多边。
直到图表变空,AtCobear将重复以下操作:
- 均匀随机选择一个(未擦除)顶点(独立于之前的选择)。 然后,通过遍历一些边来擦除该顶点以及从所选顶点可到达的所有顶点。 擦除顶点也会擦除与其关联的边。
求操作完成次数的预期值。
约束
- 1 \leq N \leq 100
- S_i 是一个长度为 N 组成
0和1. - S_{i,i}=
0
输入
输入由标准输入按以下格式给出:
N S_1 S_2 \vdots S_N
输出
打印操作完成次数的预期值。 当您的输出与我们的答案的绝对或相对误差最多为 10^{-9}.
示例输入 1
3 010 001 010
示例输出 1
1.66666666666666666667
我们有以下三种情况以相同的概率发生:
-
选择顶点 1 在第一个操作中,擦除顶点 1, 2,和 3。 该图现在是空的,所以我们已经完成了。
-
选择顶点 2 在第一个操作中,擦除顶点 2 和 3。 然后,选择顶点 1 在第二次操作中,擦除顶点 1。 该图现在是空的,所以我们已经完成了。
-
选择顶点 3 在第一个操作中,擦除顶点 2 和 3。 然后,选择顶点 1 在第二次操作中,擦除顶点 1。 该图现在是空的,所以我们已经完成了。
因此,操作完成次数的预期值为 (1+2+2)/3=5/3.
示例输入 2
3 000 000 000
示例输出 2
3.00000000000000000000
总是有三个操作。
示例输入 3
3 011 101 110
示例输出 3
1.00000000000000000000
总会有一个操作。