この解説では、\(N,M \le 10^5\) の解法を解説します。\(N,M \le 2000\) の解法を理解しているものとして解説を進めます。

\(\max_{1 \le i < j \le N} A_j - A_i\) が負になるものについては今の時点で \(\mathrm{O}(M)\) で解けているため無視します。

\(0 \le K \le M-1\) を満たす \(K\) に対し、\(\max_{1 \le i < j \le N} A_j - A_i\) が \(K\) 以下であるものの個数の総和を求められれば良いです。

上記をまとめると、\(\displaystyle \sum_{K=0}^{M-1} \sum_{L=1}^{N+1} (K+1)^{N+1-L} \times \binom{M-K-1}{L-1} \times \binom{N}{L-1}\) となり、整理すると \(\displaystyle \sum_{K=1}^{M} \sum_{L=0}^{N} K^{N-L} \times \binom{M-K}{L} \times \binom{N}{L}\) となります。

ここで、この式を \(K\) を変数に持つ多項式と解釈します。\(\displaystyle f_L(x) = \frac{\displaystyle x^{N-L} \times \binom{N}{L} \times \prod_{i=0}^{L-1} (M-x-i)}{L!}\) と定義すると、求めるべき値は \(\displaystyle \sum_{L=0}^{N} \sum_{K=1}^{M} f_L(K)\) となります。

\(\displaystyle G_L(x) = \frac{F_L(x)}{F_{L-1}(x)}\) と定義した時、\(\displaystyle \sum_{L=0}^{N} f_L(x) = f_0(x) \times \left(\sum_{i=0}^{N} \prod_{j=1}^{i} G_j(x)\right)\) であり、\(\displaystyle f_0(x) = x^N,g_L(x) = \frac{(M-x-L+1)}{Lx} \times \frac{\binom{N}{L}}{\binom{N}{L-1}}\) であるため、二分木のように計算することにより \(\mathrm{O}(N\log^2 N)\) で \(N\) 次の多項式 \(U(x),V(x)\) を用いて \(\displaystyle \sum_{L=0}^{N} f_L(x) = \frac{U(x)}{V(x)}\) と 表すことができました。

そして、\(K=1,2,...,M\) に対し \(U(x),V(x)\) をそれぞれ多点評価することにより \(\displaystyle \sum_{L=0}^{N} f(K)\) を求めることができました。

上記より、本問題を \(\mathrm{O}(N\log^2 N + M\log^2 M)\) で解くことができます。