题目描述

有一个包含 $N$ 个顶点、编号为 $1$ 到 $N$ 的有向图。该图的边由 $N$ 个长度为 $N$ 的字符串 $S_1,S_2,\ldots,S_N$ 表示。具体来说，如果存在一条从顶点 $i$ 到顶点 $j$ 的有向边，则 $S_{i,j}=$1，否则 $S_{i,j}=$0。该图中没有自环和重边。

小熊 AtCobear 会重复进行如下操作，直到图为空：

• 从当前尚未被删除的顶点中，等概率随机选择一个顶点（每次选择相互独立）。然后，删除该顶点以及从该顶点出发通过若干条边能够到达的所有顶点。与被删除顶点相连的所有边也会被删除。

请计算完成所有操作所需的操作次数的期望值。

输入格式

输入通过标准输入按以下格式给出：

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

输出操作次数的期望值。如果你的答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

样例 1

输入

3
010
001
010

输出

1.66666666666666666667

样例 2

输入

3
000
000
000

输出

3.00000000000000000000

样例 3

输入

3
011
101
110

输出

1.00000000000000000000

说明/提示

限制条件

• $1\leq N\leq 100$
• $S_i$ 是由 0 和 1 组成的长度为 $N$ 的字符串。
• $S_{i,i}=$0

样例解释 1

有以下 $3$ 种等概率发生的情形：

• 第一次操作选择顶点 $1$，顶点 $1,2,3$ 被删除。图为空，操作结束。
• 第一次操作选择顶点 $2$，顶点 $2,3$ 被删除。第二次操作选择顶点 $1$，顶点 $1$ 被删除。图为空，操作结束。
• 第一次操作选择顶点 $3$，顶点 $2,3$ 被删除。第二次操作选择顶点 $1$，顶点 $1$ 被删除。图为空，操作结束。

因此，操作次数的期望值为 $(1+2+2)/3=5/3$。

样例解释 2

一定会进行 $3$ 次操作。

样例解释 3

一定会进行 $1$ 次操作。

由 ChatGPT 4.1 翻译