便利のため，すべてを \(0\)-based index で考えます．各 \(A_i\) を increment すれば同じスコアになります．

descents を直接数える代わりに，以下の問題を解くことを考えます．

• \(K\) (\(1 \leq K \leq N\)) を固定する．\(A_i\) を \(K\) 個の集合 \((y_{0,0},\ldots,y_{0,s_0-1}),\ldots,(y_{K-1,0},\ldots,y_{K-1,s_{K-1}-1})\) に分割する方法を考える．ここで各 \(y_i\) は昇順であるとする．以降これらの \(y_i\) をブロックと呼ぶことにする．すべてのブロックを連結してできる列を \(x\) とし，すべての分割にわたる \(x\) のスコアの総和を求めよ．

各 \(1 \leq K \leq N\) に対して上記の問題が解ければ，そこから元問題の答えを得ることができます．

スコアを以下の形で解釈しなおします．

• 各 \(A_i\) に対し，それより左にあるいずれかの要素に link を張るか，何もしない．何もしない場合，\(A_i\) 倍の重みがかかる．このような要素を終端要素と呼ぶことにする．

ある要素 \(v\) に対し，それから link をたどることでたどり着く終端要素を \(v\) の根と呼ぶことにします． 要素 \(r\) を根とする要素の集合を，\(r\) のグループと呼ぶことにします．

どの要素が終端要素かと，それらのグループをすべて決め打ったとします． 逆に，各要素の含まれるブロック番号や，link の具体的な張り方は固定していません． これらをすべて動かしたときのスコアの総和がいくつになるか考えてみます．

まず，この問題は各グループごとに独立に考えてよいです．

では，\(1\) つの終端要素 \(v\) に注目してみましょう．\(v\) のグループ内にある \(v+1\) 以上の値の個数を \(a\)，\(v-1\) 以下の値の個数を \(b\) とします．

\(v\) をブロック \(k\) に配置したとします． \(v+1\) 以上の値はそれぞれ，ブロック \(k,k+1,\ldots,K-1\) のどれかに割り振ります． \(v-1\) 以下の値はそれぞれ，ブロック \(k+1,\ldots,K-1\) のどれかに割り振ります． よって，グループの要素のブロックへの振り分け方は全部で \((K-k)^a(K-k-1)^b\) 通りあります．そしてそのいずれについても，link の張り方は \((a+b)!\) 通りあります．

これで終端要素とグループ分けを固定した場合のスコアの総和は求まることになりました．

では，終端要素とグループ分けを動かして和をとることを考えましょう．これは，以下のような \(dp\) を考えればよいです．

• \(dp[h][C][D]=\) 上位 \(N-h\) 個に含まれる終端要素をすでに決めており，上位 \(N-h\) 個でまだグループを決定していない要素が \(C\) 個，下位 \(h\) 個でまだグループを決定していない要素が \(D\) 個，である時のスコアの総和．

これを \(h=N,N-1,N-2,\ldots,0\) と動かしながら計算します．

ここで注意すべきは，\(D\) の扱い方です． \(h\) を減少させていくので下位 \(h\) 個の値のうちどれを使っていてどれを使っていないかを保存したくなります． つまり，下位 \(h\) 個の値の部分集合 \(s\) に対し，\(dp[h][C][s]\) を持っておきたいです． しかしここで，\(s\) の情報として重要なのはそのサイズだけであることがわかります．つまり，二つの集合 \(s,t\) が \(|s|=|t|\) を満たすとき，\(dp[h][C][s]=dp[h][C][t]\) が成立します． これはこの数え上げが何をしているかを考えればわかります．

具体的な遷移を考えましょう． 難しいのは，\(A_h\) を終端要素として利用する \(dp[h+1] \to dp[h]\) の遷移です． 上から \(a\) 個，下から \(b\) 個を \(A_h\) のグループに入れるという遷移を考えると，

\[dp[h][C-a][D-b] \mathrel{+}= dp[h+1][C][D+1] \times {C \choose a} \times {h-D+b \choose b} \times (a+b)! \times \left ( \sum_{0 \leq k < K}(K-k)^a (K-k-1)^b \right )\]

となります． これは愚直にやると遅いですが，FFT で高速化することができ，\(O(N^2 \log N)\) 時間で遷移が行えます． よって全体で \(O(N^4 \log N)\) 時間の解法になります．

解答例(C++)