まず Increasing Problem を解きます。「\(f_i(x) = A_1,A_2,\dots,A_i\) を広義単調増加にし、\(A_i = x\) とするために必要な操作回数の最小値」と定義される関数 \(f_i(x)\) を考えます。遷移は以下のように行います。

• \(f_0(x) = 0\)
• \(f_i(x) = \min_{y \le x} f_{i-1}(y) + |x - A_i|\)

この関数 \(f_i(x)\) を slope trick で管理することで \(\mathrm{O}(N\log N)\) で Increasing Problem を解くことが出来ます。ですが、このままでは扱いづらいです。ここで slope trick の内部を考えると以下が Increasing Problem の答えであることが分かります。

• 整数の多重集合 \(X\) に対して \(i=1,2,\dots,N\) の順で以下を行う。ただし、始め \(X\) は空集合とする。
  • \(X\) に \(2\) 個 \(A_i\) を追加する。
  • \(X\) の最大の要素の \(1\) 個を \(v\) とする。答えに \(\max(v-A_i,0)\) を加算する。\(X\) から \(v\) を(1 個のみ)削除する。

ここで、\(1 \le s \le M-1\) に対して以下の問題を解いてその答えの総和を取ることとします。

• 全ての \(M^N\) 通りの数列 \(A\) に対して、\(A\) の要素のうち \(s\) 以下のものを \(0\)、\(s+1\) 以上のものを \(1\) とした数列 \(B\) に対して Increasing Problem を解きその答えの総和を求める。

この結果が元の問題の答えと変わらないことは容易に確認できます。以下、言い換え後の問題を全ての \(s\) に対して解くことを考えます。01 列になった場合の Increasing Problem の答えは、以下のように言い換えられます。

• はじめ座標 \(0\) にいる。以下の操作を \(i=1,2,\dots,N\) の順で以下を行う。
  • \(B_i = 0\) ならば、今いる座標 \(-1\) に移動する。ただし、今座標 \(0\) にいるならば何もしない。
  • \(B_i=1\) ならば、今いる座標 \(+1\) に移動する。
• 全ての操作が終わった時点で、今いる座標 \(-1\) に移動した回数が答えである。

さて、\(i\) 回目に今いる座標 \(-1\) に移動したとしましょう。このとき、座標 \(z\) から \(z-1\) に移動したとします。必ず座標 \(z-1\) から座標 \(z\) に移動した直近のものを \(1\) 個取ることが出来ます。これを \(j\) 回目としましょう。すると、\(j+1\) 回目から \(i-1\) 回目の移動はカタラン数のように \(+1,-1\) を繰り返し累積和の最小値が \(0\) で更に総和が \(0\) となる必要があります。つまり \(k:=j-i-1\) を固定したとき、以下の値を掛け合わせればよいです。(ただし \(k\) は偶数)

• \(i\) の候補 \(N - k - 1\) 個
• \(j+1\) 回目から \(i-1\) 回目までの移動方法 \(C_{\frac{k}{2}} \times {s(M-s)}^{\frac{k}{2}} = \frac{k !}{\frac{k}{2}! \left(\frac{k}{2}+1\right)!}\times {s(M-s)}^{\frac{k}{2}} \)
• \(j-1\) 回目まで、または \(i+1\) 回目以降の \(A\) の値の候補 \(M^{N - k - 2}\)

これを全ての \(k\) に対して \(s(M-s)\) の多項式として足し合わせて、\(1(M-1),2(M-2),\dots,(M-1)1\) で多点評価することで全ての \(s\) に対して言い換え後の問題を解くことが出来ます。計算量は、\(\mathrm{O}(M\log^2 M + N \log N)\) となり十分高速です。また、ここで \(s\) の多項式に置き換えて \(i\) 乗和を \(\frac{e^{(M+1)x}-1}{e^x-1}\) で求めることで \(\mathrm{O}(N\log N)\) で解くことも可能です。