题解

思路

固定平均数 $m$ 后，条件等价于所有元素的 $x-m$ 之和为零。

做法

把 $m$ 左右两边分别看作距离为 $1,2,\ldots$ 的砝码，就要从两边各选择每种距离 $0$ 到 $K$ 个，并使距离和相等；数值 $m$ 自身有 $K+1$ 种出现次数，最后扣除一次所有出现次数均为零的空集。

预处理 $dp[i][s]$ 表示距离 $1$ 到 $i$ 各选至多 $K$ 个、总和为 $s$ 的方案数。转移是同一模 $i$ 余数类上的长度 $K+1$ 滑动窗口，可在常数时间完成一次状态更新。于是平均数为 $m$ 的答案为 $(K+1)\sum_s dp[m-1][s]dp[N-m][s]-1$。

复杂度

总时间复杂度为 $O(N^3K)$，空间复杂度为 $O(N^3K)$ 的三角形状态总量。