解法
スライム\(i,j \ (i < j)\) を結合した新しいスライムは，スライム\(j\) とみなす．このとき，スライム\(i\) を選んで結合したと呼ぶ． 区間\(I_{i} := [x_{i}, x_{i+1})\) を通過する回数の期待値を各\(i\) に対して求めれば，期待値の線形性から答えが求まる．
区間\(I_{i}\) に対して，スライム\(j \ (j \leq i)\) が通過する回数の期待値を求める．
- \(j = i\)のとき，期待値は 1.
- \(j = i-1\)のとき，スライム\(i\) の後に スライム\(i-1\) が選ばれればよいので，期待値は \(\frac{1}{2}\).
- \(j = i-2\)のとき，スライム\(i\) とスライム\(i-1\) の後に スライム\(i-2\) が選ばれればよいので，期待値は \(\frac{1}{3}\).
- \(\vdots\)
- \(j = 0\)のとき， 期待値は \(\frac{1}{i+1}\).
よって，\(I_{i}\) を通過する回数の期待値は，期待値の線形性から $$ s_{i} := \sum_{k \in [1,i+1] \frac{1}{k}}. $$
実装
\(s_{i}\) を累積和として求めながら問題の答えを求めれば\(O(N)\).
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n;
cin >> n;
vll a(n); rep(i,n) { cin >> a[i]; }
mint ans;
mint s;
rep(i,n-1){
s += mint(1) / mint(i+1);
ans += s * mint(a[i+1] - a[i]);
}
rep1(i,n-1) ans *= i;
cout << ans.val() << endl;
return 0;
}
