真是个美难题。
首先不难发现一个序列的贡献被分成了若干段，每一段最后一个位置是最大值，否则不是最大值。而一个段的贡献是最大值减去这个段的第一个数。
首先我们要对这个贡献进行统计就需要寻找统计思路。我们考虑枚举最大值，这样我们发现我们枚举有多少最大值复杂度是对的，这是经典的调和级数。
但是现在仍然不好计算。我们需要关心每个段第一个数的贡献，还要大概知道段是怎么分的，会不会存在只有一个值在一段的情况，还要限制每一个位置的大小。。。这看起来并不好统计。
我们可以考虑拆贡献，对于每个位置计算贡献。在算贡献前我们得先推出总方案数的式子。我们考虑有多少最大值为 \(k\) 的合法序列。显然我们可以考虑插板，但是我们要限制 \(\forall 1\le i<n, a_i\le k\)，我们可以使用容斥解决，我们钦定一些位置超过了 \(k\)，此时我们不妨设：
那么对于最大值为 \(k\) 的合法序列个数即为 \(f(n-1,m-k,k)\)。
对于最大值的位置贡献是好算的，首先对于最后一个位置的贡献显然为 \(k\times f(n-1,m-k,k)\)。然后对于其它位置的贡献也很好算，总和为 \((n-1)k\times f(n-2,m-2k,k)\)。
然后考虑算每一段第一个数的贡献，我们显然不能够枚举第一个数是什么，但是我们知道我们要统计的是所有合法情况的第一个数的和，我们发现除了第 \(n\) 个位置以外前 \(n-1\) 个位置的限制是等价的，那么第一个数的贡献显然就是 \(\frac {m-k}{n-1}\times f(n-1,m-k,k)\)。然后对于 \(\forall 1<i<n\) 的位置的贡献也大差不差，首先要求 \(a_{i-1}=k\)，然后都是相当于是求在所有 \(f(n-2,m-2k,k)\) 种方案中这一个位置的数的和，同样每个位置也是等价的，那么每个位置的贡献就是 \(\frac {m-2k}{n-2}\times f(n-2,m-2k,k)\)，最后有 \(n-2\) 个位置，把分母约掉即可。别忘了 \(a_n\) 也可以产生贡献，而它的贡献及其简单，就是 \(k\times f(n-2,m-2k,k)\)。
我们发现对于每个 \(k\) 只需要求出 \(f(n-1,m-k,k)\) 和 \(f(n-2,m-2k,k)\) 就可以直接算答案了。想做出这道题感觉主要的难点是想到拆贡献以及在算贡献的时候注意到位置的等价使得我们可以利用类似概率的思想去简化式子。代码。