AtCoder ドワンゴからの挑戦状 予選

B問題のみ書きます。

ドワンゴからの挑戦状 予選 B Fusing Slimes

問題

スライムが規則に従い左から右に流れるので、スライムが移動した距離の期待値に\(N-1\)!を掛けたものを求めよ。

解法

こういう問題では、区間に注目するのが典型らしい。(けんちょんさんのブログ)
確かに、O\(N\)で解こうと思うと[xi,xi+1)に注目してO\(N\)が妥当な気がする。

[xi,xi+1)を通るスライムの数をc_iとおく。このとき、i+1の位置にあるスライムより左側のi個のスライムのみ考えればよい。
iの位置にあるスライムが選ばれた場合、選ばれる確率は\frac{1}{i}である。この後はc_{i-1}個のスライムが通るのと、iの位置にあるスライムが通るのを考えて期待値は\frac{1}{i} \(1 + c_{i-1}\)になる。
残りの位置にあるスライムを選ぶとi+1の位置の左側にはi-1個のスライムがあることになるので、期待値は\frac{n-1}{n}c_{i-1}となる。以上により、c_i = c_{i-1} + \frac{1}{i}となり、個数は調和級数になると分かる。
求めるものは、\(N-1\)! \times \sum{1\leq i \leq N-1}(x_{i+1} - x_{i}) \times c_iとなる。

実装

区間ごとの足し合わせで計算量はO\(N\)である。MODでの逆数テーブル、factorialテーブルを前計算して持っておけば区間に対しO\(1\)で求まる。
前計算O\(N\)で全体でO\(N\)になる。

コード

https://atcoder.jp/contests/dwacon6th-prelims/submissions/9431284

感想

競技中はx_j - x_iについて考えていて、O(N^2)の解法が浮かんだのでそこから計算量を落とそうとしていた。区間について考える。覚えておきます。
ModIntほしい。あとModInvもほしい。