https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_b
数直線上に$N$匹のスライムが並んでおり、各スライムの座標が与えられる。ここで、以下の操作をスライムが1匹になるまで繰り返すことを考える。
スライムの移動距離の期待値に$(N-1)!$を掛けたものを$10^9+7$で割ったあまりを出力せよ。
$N$個のスライムは、$N-1$個の間を持つ。$i$番目のスライムと$i+1$番目のスライムの間を$i$番目の隙間と呼ぶ。各スライムの間を通るスライムの数の期待値を考える。例えば、1番目の隙間を通るスライムの数は、必ず1つである(1番目のスライムのみ)。
$i$番目の隙間を通るスライムの数の期待値を$c_i$と呼ぶ。ここで、$c_{i-1}$がわかっているとき$c_{i}$を考える。$i$番目の隙間の左側には$i$個のスライムがあり、このスライムの中で$i$番目のスライムが最初に選ばれる確率は$1/i$である。この場合には$i$番目のスライムが$i$番目の隙間を追加したあとに$i-1$個のスライムが残るので、$i$番目の隙間を通るスライムの期待値は$1+c_{i-1}$となる。$i$番目のスライムが最初に選ばれなかった場合には、左から$i$個目までのスライムのなかでどこかが融合して2つになるので、期待値は$c_{n-1}$となる。つまり \begin{align*} c_{i}&=\frac{1+c_{i-1}}{i}+\frac{(i-1)c_{i-1}}{i}\\ &=c_{i-1}+\frac1i\\ &=\frac11+\frac12+...+\frac1i \end{align*} となる。よって、$c_i$を前計算して $$\sum_{i=1}^{N} (x_i-x_{i-1}) c_i$$ が答えとなる。
難しかった。本番では部分点をとれたが、スライムの間に注目することができなかった。以下、部分点解法
最初に一番右のスライムだけがあり、左側にスライムを追加していくDPを考える。求めるものは$(N-1)!$通りすべての操作列の距離の総和の総和であるから
$DP[i]=i$番目より右のスライムだけがあるときの、すべての操作列の距離の総和の総和
とする。スライムが$N$個あるとき、ある操作列で一番左端(1番目)のスライムが$i\;(i\geq 2)$番目のスライムにマージされるためには、操作列の中から1〜iのスライムだけを見たときに最後の2つが1, iである必要があるから、そのような操作列の数は $$(N-1)!\frac{(i-2)!}{i!}$$ である。ただし、$i=N$であれば$(N-2)!$である。 これを使ってDPした。