← 返回题目列表

AtCoder · agc049_a

A. 擦除顶点

中文机器翻译题面 查看原题

分数: 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

总会有一个操作。