ARC114 E - Paper Cutting 2 (700)
切られたら終了になる辺の数を求めておく
今回の表現方法では分子分母を持っておけば分数の足し算がそのままできる
$ \frac{A}{B} + \frac{C}{D}を計算したい場合、$ \frac{AD+BC}{BD}にすればよい
求める期待値はそれぞれの辺が切られる回数の期待値の和になる
今回は切られるか切られないかの2択なので切られる確率と同じ
ただし、切られたら終了の辺についてはどれか一つのみが必ず切られるため、全部合わせて期待値は1
ある辺が切られるのは切られたら終了の辺や自身と切られたら終了の辺の間にある辺より先に切られる場合のみ
確率は$ \frac{1}{切られたら終了の辺の数 + 自身と切られたら終了の辺の間にある辺の数 + 1}
全ての辺について計算して足し合わせれば良いので$ O(H+W)