CODE FESTIVAL 2016 qual C E 順列辞書 - dokinの競技プログラミング

まずは、部分問題を考えます。
$p_1\ldots p_n$ の中に0が含まれない場合の答えを計算してみます。
これは、 $\sum_{i=1}^N (N-i)! \times |\{j|j > i,p_j < p_i\}|$ であることが確認できます。

そこで、一般の場合は、
各x,yに対し、
$C_{x,y}$ : $|\{j|j > x,p_j < p_x \}|=y$ となる順列の数
とおき、 $\sum_{x,y}^N (N-i)!*y*C_{x,y}$ を計算すればよいです。

これだとO(N^2)ですが、さらに $C_{x,y}*y$ に注目して、
$D_x$ : $j > x,p_j < p_x$ なるjの数を全ての順列について足しあげたもの
とおいて、 $\sum_{x,y} (N-i)!*y * D_x$ を計算すればよいです。

これで勝ったも同然で、 $p_x,p_j$ が0か0でないかで4通りに場合分けし、それぞれきちきち計算すれば $D_x$ は高速に計算できるので、答えが求まります。
実装は場合分けが多いのでやや大変でした・・・

ひと月ほどまえ考えた際には歯が立たなかったのですが、いま考えたらすんなりいったのでよかったです。
まずは、0が含まれない場合を計算して、それらの和を別方向からみて足し上げるのが鍵でした。