AtCoder Grand Contest 028 B - Removing Blocks (600)
解法
解説の1つの解釈として.
解説/解説放送と同じように, iをremoveした時に A_j が足されるかどうかを考える.
ただし,確率ではなくそのような順列の場合の数を数え上げることにする.
事前準備として,n個の順列のうちで
そのうちの要素 x,y (x!=y) に関して x<y が成り立っているものは n!/2 になる.
これをもう少し考えると x_1 < .. < x_k+1 のk個の不等号があるものは n!/(k+1)! になることがわかる.
(n個の場所からx_iの場所k+1個を選ぶ) * (残りのN-k-1個は自由に並べる)
= nC(k+1) * (n-k-1)! = n!/(k+1)!
と考えても良い.
これを使って,上の順列が何通りあるかを数える.
簡単のため, i < j と仮定して
x_0 = i, x_1, ... , x_k, x(k+1) = j とする. (k = j-i-1)
ここで, 求めたい順列を束縛する不等式は i の後にx_1, x_2,.., x(k+1) が出るという条件のみを満たしていれば良いことを考えると
x_0 < ( x_1, x_2, .. , x(k+1) を好きに並べて不等号で繋いだもの ) であることがわかる.
これは, x_1,...,x(k+1) の順番が決まればk+1個の不等号が繋がっているので N!/(k+2)! 個ずつある.
このいずれかを満たす順列(つまり順列の和集合)を求めればよく,これらは全て排反であるため
合計で n!/(k+2)! * (k+1)! = n!/(k+2) = n!/(j-i+1) 個あることがわかる.
ここからは解説と一緒で,
A_j * sum_i{ n!/abs(j-i+1) } のjに関する和が答えになる.
調和級数を事前に計算しておけばO(N)
メモ
確率として典型処理するようにしたほうがいい気もする..
