AT_agc049_a.[AGC049A] Erasing Vertices

有一个包含 $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\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 翻译