E. Max History | Educational Codeforces #38

すべての順列を見ていくのは明らかに無理なので、a[j]ごとに計算していく。
つまり、f[a] = f[a] + a[M(もとの配列の添字はj)] となるような順列を数える。
その数えをg(j)としておく。g(j)さえ求まれば解は
Σa[j]g(j)

a[j]より大きい値の数えをx, a[j]以上値の数えをyと置く。
a[j] < a[i] となるような数a[i]がなければa[j]を加算されないはず。
a[j]が加算されるためにはx > 0でなければならない。なので x=0ならば明らかにg(j) = 0
さて、ある順列でa[j]が加算される必要十分条件は
a[j]がa[j]以上の値の中で最も左にあり、かつa[j]より大きい値が存在すること
である。

x > 0を仮定すると、
まず、a[j]以上の値のうちa[j]を1個除いたものの並べ方は
(y-1)! 通り
その一通りに対して
a[j]未満の値を含めた並べ方は
n!/y! 通り
ちゃんと説明すると、
a[j]以上の値だけの添字が
i1,i2,...,iy のように並んでいるとする。
これを固定すると順列のなかでは
i1, i2, ..., iy
=> o, o, ..., o
のように同じものとみて問題ない。
要するに
添字の順が逆転できないのと
添字を区別しないことで
並べ方の数えが等しい。
n個の添字のうちy個が同じであるときの並べ方を考えれば
n!/y!
となる。
以上から
x>0のときg(j) = (y-1)!*n!/y!