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 翻译