题目描述

$1$ から $N$ までの番号のついた $N$ 頂点からなる有向グラフがあります． このグラフの辺は，$N$ 個の長さ $N$ の文字列 $S_1,S_2,\ldots,S_N$ によって表されます． 具体的には，頂点 $i$ から頂点 $j$ に向かう辺が存在する場合は $S_{i,j}=$1 で， そうでない場合は $S_{i,j}=$0 です． このグラフに自己ループや多重辺はありません．

クマの AtCobear くんが，以下の操作をグラフが空になるまで繰り返します．

• (まだ削除されていない) グラフの頂点を一様ランダムに $1$ つ選ぶ（このランダムな選択は，今までの選択とは独立である）． そして，その頂点，およびその頂点からいくつかの辺をたどることで到達可能なすべての頂点を，削除する． 削除された頂点に接続する辺も，すべて削除される．

操作回数の期待値を求めてください．

输入格式

入力は以下の形式で標準入力から与えられる．

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

输出格式

操作回数の期待値を出力せよ． 絶対誤差または相対誤差が $10^{-9}$ 以下ならば，正解と判定される．

题目大意

给定一个点数为 $n(1\le n\le100)$ 的有向图（边通过邻接矩阵给出，$a_{i,j}=1$ 代表有一条边为 $i\rightarrow j$，无重边和自环），和一个操作：

• 等概率随机选定一个还未删除的点 $x$，删除 $x$ 以及图中 $x$ 能通过某些路径到达的点（指向这些点的边也会被删除）。如果图中没有任何未被删除的点，则结束操作，否则重复此操作。

求期望做多少次操作（与标准答案的误差不超过 $10^{-9}$）。

3
010
001
010

1.66666666666666666667

3
000
000
000

3.00000000000000000000

3
011
101
110

1.00000000000000000000

提示

制約

• $1\ \leq\ N\ \leq\ 100$
• $S_i$ は 0,1 からなる長さ $N$ の文字列．
• $S_{i,i}=$0

Sample Explanation 1

以下の $3$ つのシナリオが等確率で起こります． - 最初の操作で頂点 $1$ を選び，頂点 $1,2,3$ が削除される． グラフが空になったので操作を終了する． - 最初の操作で頂点 $2$ を選び，頂点 $2,3$ が削除される． 次の操作で，頂点 $1$ を選び，頂点 $1$ が削除される． グラフが空になったので操作を終了する． - 最初の操作で頂点 $3$ を選び，頂点 $2,3$ が削除される． 次の操作で，頂点 $1$ を選び，頂点 $1$ が削除される． グラフが空になったので操作を終了する． よって操作回数の期待値は，$(1+2+2)/3=5/3$ になります．

Sample Explanation 2

必ず $3$ 回の操作を行います．

Sample Explanation 3

必ず $1$ 回の操作を行います．