2019-01-06から1日間の記事一覧
問題 問題概要 一部が -1 である [1,N] のpermが与えられる. 各-1に等確率で残りの数が入る時,転倒数の期待値を求めよ. 解法 A = もともとある数, B = -1の場所に入る数 とする. A-A, A-B, B-B の期待値を足せば良い. A-A はBITを使って数え上げる. B-B は b…
問題 問題概要 一部が -1 である [1,N] のpermが与えられる. 各-1に等確率で残りの数が入る時,転倒数の期待値を求めよ. 解法 A = もともとある数, B = -1の場所に入る数 とする. A-A, A-B, B-B の期待値を足せば良い. A-A はBITを使って数え上げる. B-B は b…