/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
1 から N までの番号のついた N 頂点からなる有向グラフがあります．
このグラフの辺は，N 個の長さ N の文字列 S_1,S_2,\ldots,S_N によって表されます．
具体的には，頂点 i から頂点 j に向かう辺が存在する場合は S_{i,j}=1 で，
そうでない場合は S_{i,j}=0 です．
このグラフに自己ループや多重辺はありません．
クマの AtCobear くんが，以下の操作をグラフが空になるまで繰り返します．
- (まだ削除されていない) グラフの頂点を一様ランダムに 1 つ選ぶ（このランダムな選択は，今までの選択とは独立である）． そして，その頂点，およびその頂点からいくつかの辺をたどることで到達可能なすべての頂点を，削除する． 削除された頂点に接続する辺も，すべて削除される．
操作回数の期待値を求めてください．
制約
- 1 \leq N \leq 100
- S_i は
0,1からなる長さ N の文字列． - S_{i,i}=
0
入力
入力は以下の形式で標準入力から与えられる．
N S_1 S_2 \vdots S_N
出力
操作回数の期待値を出力せよ． 絶対誤差または相対誤差が 10^{-9} 以下ならば，正解と判定される．
入力例 1
3 010 001 010
出力例 1
1.66666666666666666667
以下の 3 つのシナリオが等確率で起こります．
-
最初の操作で頂点 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
3 011 101 110
出力例 3
1.00000000000000000000
必ず 1 回の操作を行います．
Score : 400 points
Problem Statement
We have a directed graph with N vertices numbered 1 to N.
N strings of length N each, S_1,S_2,\ldots,S_N, represent the edges in the graph.
Specifically, S_{i,j} is 1 if there is an edge from Vertex i to Vertex j, and 0 otherwise.
The graph has no self-loops and no multi-edges.
Until the graph becomes empty, AtCobear will repeat the following operation:
- Choose one (unerased) vertex uniformly at random (independently from the previous choices). Then, erase that vertex and all vertices that are reachable from the chosen vertex by traversing some edges. Erasing a vertex will also erase the edges incident to it.
Find the expected value of the number of times the operation is done.
Constraints
- 1 \leq N \leq 100
- S_i is a string of length N consisting of
0and1. - S_{i,i}=
0
Input
Input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print the expected value of the number of times the operation is done. Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-9}.
Sample Input 1
3 010 001 010
Sample Output 1
1.66666666666666666667
We have the following three scenarios happening with equal probability:
-
Choose Vertex 1 in the first operation, erasing Vertex 1, 2, and 3. The graph is now empty, so we are done.
-
Choose Vertex 2 in the first operation, erasing Vertex 2 and 3. Then, choose Vertex 1 in the second operation, erasing Vertex 1. The graph is now empty, so we are done.
-
Choose Vertex 3 in the first operation, erasing Vertex 2 and 3. Then, choose Vertex 1 in the second operation, erasing Vertex 1. The graph is now empty, so we are done.
Thus, the expected value of the number of times the operation is done is (1+2+2)/3=5/3.
Sample Input 2
3 000 000 000
Sample Output 2
3.00000000000000000000
There will always be three operations.
Sample Input 3
3 011 101 110
Sample Output 3
1.00000000000000000000
There will always be one operation.